博客

二叉树的基本操作

/*树的存储类型*/
typedef struct Node
{
    char data;
    struct Node *lchild,*rchild;
}*BiTree,BiTNode;

/*先序创建二叉树*/ 
void CreateBiTree(BiTree &T)
{
    char ch;
    cin>>ch;
    if(ch=='#') T=NULL;
    else{
        T=new BiTNode;
        T->data=ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}
/*中序遍历*/ 
void InOrder(BiTree T)
{
    if(T)
    {
        InOrder(T->lchild);
        cout<<T->data;
        InOrder(T->rchild);
    }
}
/*先序遍历*/ 
void PreOrder(BiTree T)
{
    if(T)
    {
        cout<<T->data;
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
/*后序遍历*/ 
void PostOrder(BiTree T)
{
    if(T)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        cout<<T->data;
    }
}

/*二叉树的复制*/ 
void Copy(BiTree T,BiTree &NT)
{
    if(T==NULL){
        NT=NULL;
        return;
    }
	else
    {
        NT=new BiTNode;
        NT->data=T->data;
        Copy(T->lchild,NT->lchild);
        Copy(T->rchild,NT->rchild);
    }
}
/*树的宽度与深度的非递归算法*/ 
void Depth_Width(BiTree T){
	BiTree Q[100];            //相当于循环队列
    int front=-1,rear=-1;    //队头队尾都为-1 
    int last=0,high=0,Max=0;  //last是每一层最右边的那个结点（最开始的0相当于rear+1-----头节点入队）；high数的高度，Max为最大宽度 
	int w=0;    //w用来记录每一层的宽度 
	if(T==NULL)
	cout<<"NULL";  //出口 
	/*理解成人的繁殖，最开始是一个人开始繁殖下一代（自己出队之后将他的他的孩子入队），然而他的下一代想要繁殖，则必须上一代全部完成繁殖才能开始，
	也就是说当front到了这一代的最后一个人。这样就可以计算出每一代人的个数，也可以知道有多少代人*/ 
	 
	else{		
       Q[++rear]=T;     //入队 
       BiTree P;        
       while(front<rear){    //当队列不为空 
       	P=Q[++front];  w++;    //出队且宽度加一。这个地方注意一出队就会将该结点的孩子入队 
       	if(P->lchild)  Q[++rear]=P->lchild;  //左孩子入队 
       	if(P->rchild)  Q[++rear]=P->rchild;  //右孩子入队  
       	if(front==last){         //一个队列的对头和这一层最右边的结点序号相等，即一层结束；同时也意味着这一层的下一层也已经全部入队。 
       		high++;              //高度加一 
       		last=rear;           //更新最右结点序号，即下一层的最右结点序号 
       		if(w>Max) Max=w; w=0; //比较该层宽度与最大值，将w重置开始计算下一层的宽度 
       		
		   }
	   }
   }
   cout<<"树的高度为:"<<high<<"  "<<"树的宽度为:"<<Max;
} 
/*树的深度*/ 
int Depth(BiTree T)
{
    if(T==NULL)
        return 0;
    else
    {
        int m=Depth(T->lchild);  //左递归 
        int n=Depth(T->rchild);  //右递归 
        if(m>n) return (m+1);   //垂直往下找所以不为空就加一 
        else return (n+1);
    }
}
/*树的宽度*/ 
int LevelWidth(BiTree root,int level)
{
	if(!root)return 0;
	else
	{
		if(level==1)   return 1;  //递归终止条件 （高度为1，宽度为1） 
		level=LevelWidth(root->lchild,level-1)+LevelWidth(root->rchild,level-1);  //递归到叶子结点返回1，依次退回 
	}
	return level;
} 

int Width(BiTree root)
{
	int width,i;
	int w[20];
	for(i=0;i<20;i++)  w[i]=0;  
	if(root==NULL)
	   width=0;//空树 
	else
	{
		for(i=0;i<=Depth(root);i++)  //树的高度Depth(root) 
	    	w[i]=LevelWidth(root,i+1);
	}
	i=0;
	while(w[i])
	{
		if(w[i]>width)width=w[i];
		i++;
	}
	return width;
}

/*统计二叉树中结点的个数*/ 
int Node_Count(BiTree T)
{
    if(T==NULL) return 0;
    else return Node_Count(T->lchild)+Node_Count(T->rchild)+1;
}

/*统计二叉树中叶子结点的个数*/ 
int Tree_leaf_Count(BiTree T)
{
    if(!T) return 0;
    if(!T->lchild &&!T->rchild){        //如果二叉树左子树和右子树皆为空,说明该二叉树根节点为叶子节点.
        return 1;
    }else{
        return Tree_leaf_Count(T->lchild)+Tree_leaf_Count(T->rchild);
    }
}

/*统计二叉树的度为1的结点个数*/ 
int Count(BiTree T)
{
    if(!T) return 0;
    if((!T->lchild)&&(T->rchild)||(T->lchild)&&(!T->rchild))  //左右孩子有一个为空 
        return 1+Count(T->lchild)+Count(T->rchild);
    else
        return Count(T->lchild)+Count(T->rchild);
}

/*二叉树中从每个叶子结点到根结点的路径*/ 
/*本题的算法思想是通过从根节点往下遍历一直找到叶子节点为止
将中间访问的结点存入到一个数组中，然后记录好它的长度，最后
遍历到叶子节点的时候就可以将数组中的数据全部输出*/
void Total_Path(BiTree T, char path[], int len){
	
    int i;
    if(T){	
  	    path[len]=T->data; //将当前结点放入路径中
    
	    if(T->lchild==NULL&&T->rchild==NULL){      //叶子结点
	    
        for(i=len;i>=0;i--)   //将路径输出 
            cout<<path[i]<<" " ;
        cout<<endl; 
        }
	    else{
            Total_Path(T->lchild,path,len+1);//递归左子树
            Total_Path(T->rchild,path,len+1);//递归右子树
        }
    }
}

/*构造函数，使用递归算法进行左右结点转换*/ 
void Change_Tree(BiTree &T)
{
    BiTree t;
    if(T!=NULL){              //判断T是否为空，非空进行转换，否则不转换
        t=T->lchild;
        T->lchild=T->rchild;//直接交换节点地址
        T->rchild=t;
        Change_Tree(T->lchild);
        Change_Tree(T->rchild);
    }
}

/*二叉树的双序遍历*/ 
void Db_Traverse(BiTree T)
{
    if(T)
    {
        cout<<T->data;
        Db_Traverse(T->lchild);
        cout<<T->data;//访问两遍
        Db_Traverse(T->rchild);
    }
}

/*求结点x在二叉树中的双亲结点*/ 
void Parent(BiTree T,char x){
	if(T){
		if((T->lchild)&&T->lchild->data==x){    //左孩子不为空 ，判断左孩子与x是否相等 
			cout<<"存在"<<x<<"的双亲结点为:"<<T->data;return;
		} 
		if((T->rchild)&&T->rchild->data==x){   //右孩子不为空 ，判断右孩子与x是否相等 
			cout<<"存在"<<x<<"的双亲结点为:"<<T->data;return;
		} 
		else{
			Parent(T->lchild,x);
			Parent(T->rchild,x);
		}
	} 
}

欢迎留言，共同学习