纯C++代码详解二叉树相关操作

大家好今天给大家带来的是二叉树的相关操作希望能够给大家带来帮助。二叉树的概念二叉树Binary tree是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式即使是一般的树也能简单地转换为二叉树而且二叉树的存储结构及其算法都较为简单因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树且有左右之分 。二叉树的相关术语①节点包含一个数据元素及若干指向子树分支的信息 。②节点的度一个节点拥有子树的数目称为节点的度 。③叶子节点也称为终端节点没有子树的节点或者度为零的节点 。④分支节点也称为非终端节点度不为零的节点称为非终端节点 。⑤树的度树中所有节点的度的最大值 。⑥节点的层次从根节点开始假设根节点为第1层根节点的子节点为第2层依此类推如果某一个节点位于第L层则其子节点位于第L1层 。⑦树的深度也称为树的高度树中所有节点的层次最大值称为树的深度 。相关操作菜单123456789101112131415//菜单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;}二叉树的构造12345678//构造二叉树typedefstructBinode{//数据域chardata;//定义左孩子和右孩子structBinode*lchid, *rchid;}Binode, *StrBinode;创建二叉树123456789101112131415161718//先序遍历创建二叉树voidcreatBinode(StrBinodeT){cin ch;if(ch #){//如果输入是#的话就说明根结点就是叶子结点//就没必要再去进行开辟一个二叉树空间T NULL;}else{T newBinode;T-data ch;creatBinode(T-lchid);creatBinode(T-rchid);}}先序遍历二叉树1234567891011121314//先序遍历二叉树voidvisitBinode(StrBinodeT){if(T!NULL){cout T-data ;visitBinode(T-lchid);visitBinode(T-rchid);}if(TNULL){cout # ;}}中序遍历二叉树1234567891011121314//中序遍历二叉树voidMidvisitBinode(StrBinodeT){if(T ! NULL){visitBinode(T-lchid);cout T-data ;visitBinode(T-rchid);}if(T NULL){cout # ;}}后序遍历二叉树1234567891011121314//后序遍历二叉树voidBackvisitBinode(StrBinodeT){if(T ! NULL){visitBinode(T-lchid);visitBinode(T-rchid);cout T-data ;}if(T NULL){cout # ;}}层次遍历二叉树12345678910111213141516171819202122232425262728293031//二叉树的层次遍历voidLevelorder(StrBinodeHT){StrBinode T;T newBinode;//创建一个队列ququeueStrBinode 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);}}}二叉树的深度123456789101112131415161718192021//二叉树的深度intdeep(StrBinodeT){if(T NULL){return0;}else{intm deep(T-lchid);intn deep(T-rchid);if(m n){return(m 1);}else{return(n 1);}}}二叉树的叶子结点数1234567891011121314151617//求二叉树的叶子结点intleaf(StrBinodeT){//如果是空树if(T NULL){//返回0return0;}//如果是叶子结点if(T-lchid NULL T-rchid NULL){//返回1return1;}returnleaf(T-lchid) leaf(T-rchid);}二叉树的结点数12345678910111213//求二叉树的结点数intNodecount(StrBinodeT){//如果是根结点没有数据if(T NULL){return0;}else{returnNodecount(T-lchid) Nodecount(T-rchid) 1;}}整体代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242#includeiostream#includequeueusingnamespacestd;charch 0;//构造二叉树typedefstructBinode{//数据域chardata;//定义左孩子和右孩子structBinode*lchid, *rchid;}Binode, *StrBinode;//先序遍历创建二叉树voidcreatBinode(StrBinodeT){cin ch;if(ch #){//如果输入是#的话就说明根结点就是叶子结点//就没必要再去进行开辟一个二叉树空间T NULL;}else{T newBinode;T-data ch;creatBinode(T-lchid);creatBinode(T-rchid);}}//先序遍历二叉树voidvisitBinode(StrBinodeT){if(T!NULL){cout T-data ;visitBinode(T-lchid);visitBinode(T-rchid);}if(TNULL){cout # ;}}//中序遍历二叉树voidMidvisitBinode(StrBinodeT){if(T ! NULL){visitBinode(T-lchid);cout T-data ;visitBinode(T-rchid);}if(T NULL){cout # ;}}//后序遍历二叉树voidBackvisitBinode(StrBinodeT){if(T ! NULL){visitBinode(T-lchid);visitBinode(T-rchid);cout T-data ;}if(T NULL){cout # ;}}//二叉树的层次遍历voidLevelorder(StrBinodeHT){StrBinode T;T newBinode;//创建一个队列ququeueStrBinode 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(StrBinodeT){if(T NULL){return0;}else{intm deep(T-lchid);intn deep(T-rchid);if(m n){return(m 1);}else{return(n 1);}}}//求二叉树的叶子结点intleaf(StrBinodeT){//如果是空树if(T NULL){//返回0return0;}//如果是叶子结点if(T-lchid NULL T-rchid NULL){//返回1return1;}returnleaf(T-lchid) leaf(T-rchid);}//求二叉树的结点数intNodecount(StrBinodeT){//如果是根结点没有数据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;StrBinode T;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;}结果展示以上就是纯C代码详解二叉树相关操作的详细内容