纯C++二叉树相关操作实例代码分析(C++,开发技术)

二叉树的概念

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 。

二叉树的相关术语

①节点：包含一个数据元素及若干指向子树分支的信息 。

②节点的度：一个节点拥有子树的数目称为节点的度 。

③叶子节点：也称为终端节点，没有子树的节点或者度为零的节点 。

④分支节点：也称为非终端节点，度不为零的节点称为非终端节点 。

⑤树的度：树中所有节点的度的最大值 。

⑥节点的层次：从根节点开始，假设根节点为第1层，根节点的子节点为第2层，依此类推，如果某一个节点位于第L层，则其子节点位于第L+1层 。

⑦树的深度：也称为树的高度，树中所有节点的层次最大值称为树的深度 。

相关操作菜单

//菜单voidmenu(){cout<<"\t\t\t******************************************************************"<<endl;cout<<"\t\t\t****************1.输入-1退出程序*******************"<<endl;cout<<"\t\t\t****************2.输入1初始化二叉树*******************"<<endl;cout<<"\t\t\t****************3.输入2对二叉树先序遍历*******************"<<endl;cout<<"\t\t\t****************4.输入3对二叉树中序遍历*******************"<<endl;cout<<"\t\t\t****************5.输入4对二叉树后序遍历*******************"<<endl;cout<<"\t\t\t****************6.输入5对二叉树层次遍历*******************"<<endl;cout<<"\t\t\t****************7.输入6二叉树深度*******************"<<endl;cout<<"\t\t\t****************8.输入7二叉树叶子结点数*******************"<<endl;cout<<"\t\t\t****************9.输入8二叉树的结点数*******************"<<endl;cout<<"\t\t\t******************************************************************"<<endl;}

二叉树的构造

//构造二叉树typedefstructBinode{//数据域chardata;//定义左孩子和右孩子structBinode*lchid,*rchid;}Binode,*StrBinode;

创建二叉树

//先序遍历创建二叉树voidcreatBinode(StrBinode&T){cin>>ch;if(ch=='#'){//如果输入是#的话就说明根结点就是叶子结点//就没必要再去进行开辟一个二叉树空间T=NULL;}else{T=newBinode;T->data=ch;creatBinode(T->lchid);creatBinode(T->rchid);}}

先序遍历二叉树

//先序遍历二叉树voidvisitBinode(StrBinode&T){if(T!=NULL){cout<<T->data<<"";visitBinode(T->lchid);visitBinode(T->rchid);}if(T==NULL){cout<<"#"<<"";}}

中序遍历二叉树

//中序遍历二叉树voidMidvisitBinode(StrBinode&T){if(T!=NULL){visitBinode(T->lchid);cout<<T->data<<"";visitBinode(T->rchid);}if(T==NULL){cout<<"#"<<"";}}

后序遍历二叉树

//后序遍历二叉树voidBackvisitBinode(StrBinode&T){if(T!=NULL){visitBinode(T->lchid);visitBinode(T->rchid);cout<<T->data<<"";}if(T==NULL){cout<<"#"<<"";}}

层次遍历二叉树

//二叉树的层次遍历voidLevelorder(StrBinode&HT){StrBinodeT;T=newBinode;//创建一个队列ququeue<StrBinode>qu;//将根结点的指针压入队列qu.push(HT);//当队列不为空的时候就继续进行循环while(!qu.empty()){//让T里面存放队列中第一个元素的值T=qu.front();//C++自带的队列出队的话是删除值不返回值qu.pop();//访问出队元素的值cout<<T->data<<"";//当该节点左孩子不为空的时候就让左孩子入队if(T->lchid!=NULL){qu.push(T->lchid);}//当该节点右孩子不为空的时候就让左孩子入队if(T->rchid!=NULL){qu.push(T->rchid);}}}

二叉树的深度

//二叉树的深度intdeep(StrBinode&T){if(T==NULL){return0;}else{intm=deep(T->lchid);intn=deep(T->rchid);if(m>n){return(m+1);}else{return(n+1);}}}

二叉树的叶子结点数

//求二叉树的叶子结点intleaf(StrBinode&T){//如果是空树if(T==NULL){//返回0return0;}//如果是叶子结点if(T->lchid==NULL&&T->rchid==NULL){//返回1return1;}returnleaf(T->lchid)+leaf(T->rchid);}

二叉树的结点数

//求二叉树的结点数intNodecount(StrBinode&T){//如果是根结点没有数据if(T==NULL){return0;}else{returnNodecount(T->lchid)+Nodecount(T->rchid)+1;}}

整体代码

#include<iostream>#include<queue>usingnamespacestd;charch=0;//构造二叉树typedefstructBinode{//数据域chardata;//定义左孩子和右孩子structBinode*lchid,*rchid;}Binode,*StrBinode;//先序遍历创建二叉树voidcreatBinode(StrBinode&T){cin>>ch;if(ch=='#'){//如果输入是#的话就说明根结点就是叶子结点//就没必要再去进行开辟一个二叉树空间T=NULL;}else{T=newBinode;T->data=ch;creatBinode(T->lchid);creatBinode(T->rchid);}}//先序遍历二叉树voidvisitBinode(StrBinode&T){if(T!=NULL){cout<<T->data<<"";visitBinode(T->lchid);visitBinode(T->rchid);}if(T==NULL){cout<<"#"<<"";}}//中序遍历二叉树voidMidvisitBinode(StrBinode&T){if(T!=NULL){visitBinode(T->lchid);cout<<T->data<<"";visitBinode(T->rchid);}if(T==NULL){cout<<"#"<<"";}}//后序遍历二叉树voidBackvisitBinode(StrBinode&T){if(T!=NULL){visitBinode(T->lchid);visitBinode(T->rchid);cout<<T->data<<"";}if(T==NULL){cout<<"#"<<"";}}//二叉树的层次遍历voidLevelorder(StrBinode&HT){StrBinodeT;T=newBinode;//创建一个队列ququeue<StrBinode>qu;//将根结点的指针压入队列qu.push(HT);//当队列不为空的时候就继续进行循环while(!qu.empty()){//让T里面存放队列中第一个元素的值T=qu.front();//C++自带的队列出队的话是删除值不返回值qu.pop();//访问出队元素的值cout<<T->data<<"";//当该节点左孩子不为空的时候就让左孩子入队if(T->lchid!=NULL){qu.push(T->lchid);}//当该节点右孩子不为空的时候就让左孩子入队if(T->rchid!=NULL){qu.push(T->rchid);}}}//二叉树的深度intdeep(StrBinode&T){if(T==NULL){return0;}else{intm=deep(T->lchid);intn=deep(T->rchid);if(m>n){return(m+1);}else{return(n+1);}}}//求二叉树的叶子结点intleaf(StrBinode&T){//如果是空树if(T==NULL){//返回0return0;}//如果是叶子结点if(T->lchid==NULL&&T->rchid==NULL){//返回1return1;}returnleaf(T->lchid)+leaf(T->rchid);}//求二叉树的结点数intNodecount(StrBinode&T){//如果是根结点没有数据if(T==NULL){return0;}else{returnNodecount(T->lchid)+Nodecount(T->rchid)+1;}}//菜单voidmenu(){cout<<"\t\t\t******************************************************************"<<endl;cout<<"\t\t\t****************1.输入-1退出程序*******************"<<endl;cout<<"\t\t\t****************2.输入1初始化二叉树*******************"<<endl;cout<<"\t\t\t****************3.输入2对二叉树先序遍历*******************"<<endl;cout<<"\t\t\t****************4.输入3对二叉树中序遍历*******************"<<endl;cout<<"\t\t\t****************5.输入4对二叉树后序遍历*******************"<<endl;cout<<"\t\t\t****************6.输入5对二叉树层次遍历*******************"<<endl;cout<<"\t\t\t****************7.输入6二叉树深度*******************"<<endl;cout<<"\t\t\t****************8.输入7二叉树叶子结点数*******************"<<endl;cout<<"\t\t\t****************9.输入8二叉树的结点数*******************"<<endl;cout<<"\t\t\t******************************************************************"<<endl;}intmain(){intn=0;StrBinodeT;menu();while(cin>>n){if(n<0){break;}switch(n){case1://初始化二叉树cout<<"请输入值对二叉树进行初始化"<<endl;creatBinode(T);cout<<"初始化完成"<<endl;break;case2://先序遍历cout<<"先序遍历的结果为"<<endl;visitBinode(T);cout<<"先序遍历结束"<<endl;break;case3://中序遍历cout<<"中序遍历的结果为"<<endl;MidvisitBinode(T);cout<<"中序遍历结束"<<endl;break;case4://后序遍历cout<<"后序遍历的结果为"<<endl;BackvisitBinode(T);cout<<"后序遍历结束"<<endl;break;case5://层次遍历cout<<"层次遍历的结果为"<<endl;Levelorder(T);cout<<"层次遍历结束"<<endl;break;case6:cout<<"二叉树的深度为：";cout<<deep(T)<<endl;break;case7:cout<<"二叉树的叶子结点数为：";cout<<leaf(T)<<endl;break;case8:cout<<"二叉树的结点数为；";cout<<Nodecount(T)<<endl;break;default:cout<<"您的输入有误，请重新输入"<<endl;break;}}return0;}

结果展示