数据结构与算法问题分析及源代码之二叉树.doc

《数据结构与算法问题分析及源代码之二叉树.doc》由会员分享，可在线阅读，更多相关《数据结构与算法问题分析及源代码之二叉树.doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、二叉树1 题目 编写一个程序，实现二叉树的各种运算，并在此基础上设计一个主程序完成如下功能（b为如图示的一棵二叉树）：输出二叉树b;输出H节点的左、 右孩子结点值;输出二叉树b的深度;输出二叉树b的结点个数;输出二叉树b的叶子结点个数。2 目标熟悉二叉树的定义及其基本操作的实现3 设计思想二叉树的每个结点都有指向其左右孩子的指针，对二叉树的表示可以有很多方法，这里采用中序的带括号表示法，以字符串形式读入输出。建立存储结构的时候，从根结点开始，赋值定义其左右指针，由于二叉树的每个结点操作类似，因此可以采用递归的方法。4 算法描述（1） 输入建立二叉树：读入字符串，根据括号表示法的规则，a（b,c

2、）的括号中左右元素表示结点的左右子树结点，若结点是树（括号中还有括号），则再调用改操作，直至结点全部读入。（2） 输出二叉树：从根结点开始，打印根结点数据，如果结点的左右孩子指针不为空，就打印左括号，并按先左后右的次序调用此操作，最后输出右括号完成括号表示。（3） 输出二叉树的深度：从根结点开始，如果左或右孩子不是树的话返回深度加一，否则继续调用此操作，直到完全返回(返回深度是左、右深度中的最大值)。（4） 输出二叉树叶子结点数：从根结点开始，用ln和r n分别表示结点左右叶子结点数，函数返回叶子结点数之和，递归调用该函数，直到左右指针指空。（5） 输出二叉树结点数：结点数即是叶子数加一。5

3、程序结构图主程序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)6 源程序typedef

4、struct nodechar 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 =

5、(struct node*)malloc(sizeof(struct node); p-data=ch;p-lchild=p-rchild=NULL; if (bt=NULL)/是根结点 bt=p; else/是叶子结点 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

6、!=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;elselh=BtNodeDepth(bt-lchild);rh=BtNodeDepth(bt-rchild);return (lhrh?lh:rh)+1;int NodeNum(Bitree bt)int ln,rn;if(bt=NULL)return 0;elseln=No

7、deNum(bt-lchild);rn=NodeNum(bt-rchild);return ln+rn+1;int LeafNodeNum(Bitree bt)int ln,rn;if(bt=NULL)return 0;else if(bt-lchild=NULL&bt-rchild=NULL)return 1;elseln=LeafNodeNum(bt-lchild);rn=LeafNodeNum(bt-rchild);return ln+rn;#include #include #include bintree.hvoid main() int m,length; Bitree p; ch

8、ar 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;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();