二叉树相关操作代码实现（先序、中序、后序遍历，递归及非递归算法实现，深度，结点数，叶子结点数等代码实现）

女爷i 2022-05-03 11:57 50阅读 0赞

## **二叉树相关操作的实现（先序、中序、后序遍历，递归及非递归算法实现，深度，结点数，叶子结点数等代码实现）** ##

### **以下是源代码：** ###

#include<stdio.h>
    #include<malloc.h>
    #include<stack>
    #include<iostream>
    using namespace std;
    #define MAX 20
    typedef struct BTNode{       /*节点结构声明*/
    	char data ;               /*节点数据*/
    	struct BTNode *lchild;
    	struct BTNode *rchild ;  /*指针*/
    }*BiTree;
    
    void createBiTree(BiTree &t){ /* 先序遍历创建二叉树*/
    	char s;
    	BiTree q;
    	//printf("\nplease input data:(exit for #)");
    	s=getchar();
    	if(s=='#'){t=NULL; return;}
    	q=(BiTree)malloc(sizeof(struct BTNode));
    	if(q==NULL){cout<<"Memory alloc failure!"; exit(0);}
    	q->data=s;
    	t=q;
    	createBiTree(q->lchild); /*递归建立左子树*/
    	createBiTree(q->rchild); /*递归建立右子树*/
    }
    
    void PreOrder(BiTree p){  /* 先序遍历二叉树*/
        if (p) {
           	cout<<p->data;
           	PreOrder( p->lchild ) ;
           	PreOrder( p->rchild) ;
        }
    }
    void InOrder(BiTree p){  /* 中序遍历二叉树*/
        if(p) {
     	 InOrder( p->lchild ) ;
       	 cout<<p->data;
       	 InOrder( p->rchild) ;
        }
    }
    void PostOrder(BiTree p){  /* 后序遍历二叉树*/
       if (p) {
        	PostOrder( p->lchild ) ;
           	PostOrder( p->rchild) ;
           	cout<<p->data;
        }
    }
    
    void Preorder_n(BiTree p){ /*先序遍历的非递归算法*/
        BiTree stack[MAX],q;
        int top=0,i;
        for(i=0;i<MAX;i++) stack[i]=NULL;/*初始化栈*/
        q=p;
        while(q){
            cout<<q->data;
            if(q->rchild) stack[top++]=q->rchild;
            if(q->lchild) q=q->lchild;
            else
                if(top>0) q=stack[--top];
                else q=NULL;
        }
    }
    
    void Inorder_n(BiTree t)   // 中序遍历的非递归
    {
        if(!t)
            return ;
        BiTree curr = t;    // 指向当前要检查的节点
        stack<BiTree> s;
    	while(curr != NULL || !s.empty())
    	{
    		while(curr != NULL)
    		{
    			s.push(curr);
    			curr = curr->lchild;
    		}//while
    		if(!s.empty())
    		{
    			curr = s.top();
    			s.pop();
    			cout<<curr->data<<"  ";
    			curr = curr->rchild;
    		}
    	}
    }
    
    void Postorder_n(BiTree t)  // 后序遍历的非递归
    {
        stack<BiTree> S;
        BiTree curr = t ;           // 指向当前要检查的节点
        BiTree previsited = NULL;    // 指向前一个被访问的节点
        while(curr != NULL || !S.empty())  // 栈空时结束
        {
            while(curr != NULL)            // 一直向左走直到为空
            {
                S.push(curr);
                curr = curr->lchild;
            }
            curr = S.top();
            // 当前节点的右孩子如果为空或者已经被访问，则访问当前节点
            if(curr->rchild == NULL || curr->rchild == previsited)
            {
                cout<<curr->data<<"  ";
                previsited = curr;
                S.pop();
                curr = NULL;
            }
            else
                curr = curr->rchild;      // 否则访问右孩子
        }
    }
    
    void Copy(BiTree t,BiTree &Newt)
    {
    	if(t==NULL)
    	{
    		Newt=NULL;
    		return;
    	}
    	else{
    	//Newt=new BiTree;
    	Newt=(BiTree)malloc(sizeof(struct BTNode));
    	Newt-> data=t-> data;
    	Copy(t->lchild,Newt->lchild);
    	Copy(t->rchild,Newt->rchild);
    	}
    }
    
    void LevelOrder(BiTree t)     //非递归层次遍历二叉树
    {
        BiTree queue[MAX];//定义队列有十个空间
        if (t==NULL)
            return;
        int front,rear;
        front=rear=0;
        queue[rear++]=t;
        while(front!=rear)//如果队尾指针不等于对头指针时
        {
            cout<<queue[front]->data<<"  ";  //输出遍历结果
            if(queue[front]->lchild!=NULL)  //将队首结点的左孩子指针入队列
            {
                queue[rear]=queue[front]->lchild;
                rear++;    //队尾指针后移一位
            }
            if(queue[front]->rchild!=NULL)
            {
                queue[rear]=queue[front]->rchild;    //将队首结点的右孩子指针入队列
                rear++;   //队尾指针后移一位
            }
            front++;    //对头指针后移一位
        }
    }
    
    void release(BiTree t){ /*释放二叉树空间*/
      	if(t){
        	release(t->lchild);
        	release(t->rchild);
        	free(t);
      	}
    }
    
    int Depth(BiTree t)     //计算二叉树的深度
    {
        int m,n;
        if(t==NULL)   return 0;
        else
        {
            m=Depth(t->lchild);
            n=Depth(t->rchild);
            if(m>n) return(m+1);
            else return(n+1);
        }
    }
    
    int NodeCount(BiTree t)     //统计二叉树中结点的个数
    {
        if(t==NULL) return 0;
        else  return NodeCount(t->lchild)+NodeCount(t->rchild)+1;
    }
    
    int NodeCount_leaf(BiTree t)     //统计二叉树中叶子结点的个数
    {
        int l,r;
        if(t==NULL) return 0;
        else  if(t->lchild==NULL&&t->rchild==NULL)
            return 1;
        else
        {
            l=NodeCount_leaf(t->lchild);
            r=NodeCount_leaf(t->rchild);
            return (l+r);
        }
    }
    
    int main(){
        BiTree t;
        BiTree Newt;
        printf("创建二叉树：\n");
        createBiTree(t);
        cout<<"***  ***  ***  ***  ***  ***\n";
    	cout<<"请选择：\n";
    	cout<<"1.先序遍历二叉树 \n";
    	cout<<"2.中序遍历二叉树 \n";
    	cout<<"3.后序遍历二叉树 \n";
    	cout<<"4.先序遍历二叉树(非递归算法) \n";
    	cout<<"5.中序遍历二叉树(非递归算法) \n";
    	cout<<"6.后序遍历二叉树(非递归算法) \n";
    	cout<<"7.层次遍历二叉树(非递归算法) \n";
    	cout<<"8.复制二叉树 \n";
    	cout<<"9.计算二叉树的深度 \n";
    	cout<<"10.统计二叉树中结点的个数 \n";
    	cout<<"11.统计二叉树中叶子结点的个数 \n";
    	cout<<"***  ***  ***  ***  ***  ***\n";
    	int a;
    	cin>>a;
    	cout<<endl;
    	switch(a)
    	{
    		case 1:PreOrder(t);break;
    		case 2:InOrder(t);break;
    		case 3:PostOrder(t);break;
    		case 4:Preorder_n(t);break;
    		case 5:Inorder_n(t);break;
    		case 6:Postorder_n(t);break;
    		case 7:LevelOrder(t);break;
    		case 8:Copy(t,Newt);break;
    		case 9:cout<<Depth(t);break;
    		case 10:cout<<NodeCount(t);break;
    		case 11:cout<<NodeCount_leaf(t);break;
    		default:cout<<"ERROR!"<<endl;
    	}
        release(t);
        return 0;
    }