2022年数据结构与算法问题分析及源代码之二叉树 .pdf
二叉树1 题目编写一个程序， 实现二叉树的各种运算，并在此基础上设计一个主程序完成如下功能（b为如图示的一棵二叉树）：输出二叉树b; 输出 H节点的左、右孩子结点值; 输出二叉树b 的深度 ; 输出二叉树b 的结点个数 ; 输出二叉树b 的叶子结点个数。2 目标熟悉二叉树的定义及其基本操作的实现3 设计思想二叉树的每个结点都有指向其左右孩子的指针，对二叉树的表示可以有很多方法，这里采用中序的带括号表示法，以字符串形式读入输出。建立存储结构的时候，从根结点开始，赋值定义其左右指针，由于二叉树的每个结点操作类似，因此可以采用递归的方法。4 算法描述（1）输入建立二叉树：读入字符串，根据括号表示法的规则，a（ b,c ）的括号中左右元素表示结点的左右子树结点，若结点是树（括号中还有括号），则再调用改操作，直至结点全部读入。（2）输出二叉树：从根结点开始，打印根结点数据，如果结点的左右孩子指针不为空，就打印左括号，并按先左后右的次序调用此操作，最后输出右括号完成括号表示。（3）输出二叉树的深度：从根结点开始，如果左或右孩子不是树的话返回深度加一，否则继续调用此操作，直到完全返回( 返回深度是左、右深度中的最大值) 。（4）输出二叉树叶子结点数：从根结点开始，用ln 和 r n 分别表示结点左右叶子结点数，函数返回叶子结点数之和，递归调用该函数，直到左右指针指空。（5）输出二叉树结点数：结点数即是叶子数加一。5 程序结构图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 6 源程序typedefstruct node char data; struct node *lchild; struct node *rchild; *Bitree; Bitree bt; void CreateBitree(Bitree &bt,char *str) Bitree St100,p=NULL;/100 个结点的二叉树int top=-1,k,j=0; char ch; bt=NULL; ch=strj; while (ch!= 0) switch (ch) case (:top+;Sttop=p;k=1;break ; case ):top-;break ; case ,:k=2; break ; default:p = (struct node*)malloc(sizeof (struct node); p-data=ch;p-lchild=p-rchild=NULL; if (bt=NULL) / 是根结点 bt=p; else / 是叶子结点主程序 main初始化 CreateBTNode(BTNode *&b , char *str)返回 data 域为 x 的结点指针FindNode(BTNode *b , ElemType x)返回 *p 结点的左孩子结点指针LchildNode(BTNode *p)返回 *p 结点的右孩子结点指针RchildNode(BTNode *p) 求二叉树b 的深度 BTNodeDepth(BTNode *b) 以括号标示法输出二叉树DispBTNode(BTNode *b) 求二叉树b 的结点个数Nodes(BTNode *b) 求二叉树b 的叶子结点个数LeafNodes(BTNode *b) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - switch (k) case 1:Sttop-lchild=p;break ; case 2:Sttop-rchild=p;break ; j+; ch=strj; void DispBTNode(Bitree bt) Bitree p; if (bt=NULL) return ; else printf(%c,bt-data); if (bt-lchild!=NULL|bt-rchild!=NULL) printf( ); DispBTNode(bt-lchild); if (bt-rchild!=NULL) printf(, ); DispBTNode(bt-rchild); printf() ); int BtNodeDepth(Bitree bt) int lh,rh; if (bt=NULL) return 0; else lh=BtNodeDepth(bt-lchild); rh=BtNodeDepth(bt-rchild); return (lhrh?lh:rh)+1; int NodeNum(Bitree bt) int ln,rn; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - if (bt=NULL) return 0; else ln=NodeNum(bt-lchild); rn=NodeNum(bt-rchild); return ln+rn+1; int LeafNodeNum(Bitree bt) int ln,rn; if (bt=NULL) return 0; elseif (bt-lchild=NULL&bt-rchild=NULL) return 1; else ln=LeafNodeNum(bt-lchild); rn=LeafNodeNum(bt-rchild); return ln+rn; #include #include#includebintree.h void main() int m,length; Bitree p; char e; char choice; printf(请选择 ( 输入退出 )n1 创建二叉树 bn2 打印二叉树 b( 中续括号表示法)n3 二叉树 b的长度 n4 二叉树 b的结点数 n5 二叉树 b的叶子数 n ); while (choice!=0 ) / system(cls); scanf(%c ,&choice); switch (choice) case 1 : CreateBitree(bt,A(B(D,E(H(J,K(L,M(,N),),C(F,G(,I); break ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - case 2 : DispBTNode(bt); printf(n ); break ; case 3 : printf( 二叉树 b的长度为 :%dn ,BtNodeDepth(bt); break ; case 4 : printf( 二叉树结点数为:%dn ,NodeNum(bt); break ; case 5 : printf( 二叉树叶子结点数为:%dn ,LeafNodeNum(bt); break ; case 0 : return; getchar(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -
