数据结构之二叉树（C++）

ゝ一纸荒年。 2023-02-21 12:44 12阅读 0赞

### 二叉树 ###

操作：先序创建二叉树，先序遍历，.中序遍历，后序遍历，统计树的节点个数，统计叶子节点个数，统计树深度。  
![二叉树][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70]

#include<iostream>
    #include<cstdlib>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    //定义二叉树类型 
    typedef struct bitnode{ 
    	char data;
    	struct bitnode *lchild,*rchild;
    }BiTNode,*BiTree;
    
    //先序创建二叉树
    void CreateBiTree(BiTree &T)
    { 
        char ch;
       scanf("%c",&ch);
        if(ch=='#') T=NULL;
        else{ 
            T=new BiTNode;
            T->data=ch;
            CreateBiTree(T->lchild);
            CreateBiTree(T->rchild);
        }
    }
    
    //访问根节点
    void Visit(BiTree bt){ 
    	printf("%c ",bt->data);
    } 
    
    //先序
    void PreOrder(BiTree bt){ 
    	if(bt==NULL) return;
    	Visit(bt);   //访问根节点！！！ 
    	PreOrder(bt->lchild);//遍历左子树 
    	PreOrder(bt->rchild);//遍历右子树 
    } 
    
    //中序 
    void InOrder(BiTree bt){ 
    	if(bt==NULL) return; 
    	InOrder(bt->lchild);//遍历左子树 
    	Visit(bt);   //访问根节点！！！
    	InOrder(bt->rchild);//遍历右子树 
    } 
    
    //后序
    void PostOrder(BiTree bt){ 
    	if(bt==NULL) return;
    	PostOrder(bt->lchild);//遍历左子树 
    	PostOrder(bt->rchild);//遍历右子树 
    	Visit(bt);   //访问根节点！！！
    } 
    
    //查找值为x的元素
    BiTree Search(BiTree bt,int x) { 
    	BiTree p;
    	if(bt){ 
    		if(bt->data==x) return bt;
    		if(bt->lchild) p=Search(bt->lchild,x);
    		if(p) return p;
    		if(bt->rchild) p=Search(bt->rchild,x);
    		if(p) return p;
    	}
    	return NULL;
    }
    
    //统计节点个数
    int CoutLeaf1(BiTree bt){ 
    	if(bt==NULL)  return 0;
    	if(bt->lchild==NULL&&bt->rchild==NULL) return 1;
    	return (CoutLeaf1(bt->lchild)+CoutLeaf1(bt->rchild)+1);
    } 
    
    //统计叶子节点个数
    int CoutLeaf2(BiTree bt){ 
    	if(bt==NULL)  return 0;
    	if(bt->lchild==NULL&&bt->rchild==NULL) return 1;
    	return (CoutLeaf2(bt->lchild)+CoutLeaf2(bt->rchild));
    } 
    
    //树的深度
    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 main(){ 
    	BiTree T;
    	cout<<"请先按照先序遍历创建二叉树（以#代表NULL）："<<endl;
    	CreateBiTree(T);  //先序创建二叉树
    	printf("输入操作步骤序号：\n1.先序遍历\n2.中序遍历\n3.后序遍历\n4.统计树的节点个数\n5.统计叶子节点个数\n6.统计树深度\n0.退出程序\n");
    	ERTY:
    		int f,x;
    		scanf("%d",&f);
    		if(f==1) { 
    			cout<<"先序遍历结果：";PreOrder(T);cout<<endl;
    		}
    		else if(f==2) { 
    			cout<<"中序遍历结果：";InOrder(T); cout<<endl;
    		}
    		else if(f==3) { 
    			cout<<"后序遍历结果：";PostOrder(T);  cout<<endl;
    		}
    		else if(f==4) cout<<"树的节点个数为："<<CoutLeaf1(T)<<"个"<<endl;
    		else if(f==5) cout<<"叶子节点个数为："<<CoutLeaf2(T)<<"个"<<endl;
    		else if(f==6) cout<<"树的层数为："<<Depth(T)<<"层"<<endl;
    		else if(f==0) goto ASDF;
    		goto ERTY;
    		ASDF:cout<<"程序结束！！！欢迎下次使用~ "<<endl;
    	return 0;
    }

结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200630190642478.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200630191038518.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw==,size_16,color_FFFFFF,t_70#pic_center