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

《数据结构与算法问题分析及源代码之二叉树》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

3、n初始化CreateBTNode(BTNode*&b,char*str)返回data域为x的结点指针FindNode(BTNode*b,ElemTypex)返回*p结点的左孩子结点指针LchildNode(BTNode*p)返回*p结点的右孩子结点指针RchildNode(BTNode*p)求二叉树b的深度BTNodeDepth(BTNode*b)以括号标示法输出二叉树DispBTNode(BTNode*b)求二叉树b的结点个数Nodes(BTNode*b)求二叉树b的叶子结点个数LeafNodes(BTNode*b)6源程序typedefstructnode{chardata;structn

4、ode*lchild;structnode*rchild;}*Bitree;Bitreebt;voidCreateBitree(Bitree&bt,char*str){BitreeSt[100],p=NULL;//100个结点的二叉树inttop=-1,k,j=0;charch;bt=NULL;ch=str[j];while(ch!=''){switch(ch){case'(':top++;St[top]=p;k=1;break;case')':top--;break;case',':k=2;break;default:p=(structnode*)malloc(sizeof(struct

5、node));p->data=ch;p->lchild=p->rchild=NULL;if(bt==NULL)//是根结点bt=p;else//是叶子结点{switch(k){case1:St[top]->lchild=p;break;case2:St[top]->rchild=p;break;}}}j++;ch=str[j];}}voidDispBTNode(Bitreebt){Bitreep;if(bt==NULL)return;else{printf("%c",bt->data);if(bt->lchild!=NULL

6、

7、bt->rchild!=NULL){printf("(");Dis

8、pBTNode(bt->lchild);if(bt->rchild!=NULL)printf(",");DispBTNode(bt->rchild);printf(")");}}}intBtNodeDepth(Bitreebt){intlh,rh;if(bt==NULL)return0;else{lh=BtNodeDepth(bt->lchild);rh=BtNodeDepth(bt->rchild);return(lh>rh?lh:rh)+1;}}intNodeNum(Bitreebt){intln,rn;if(bt==NULL)return0;else{ln=NodeNum(bt->lch

9、ild);rn=NodeNum(bt->rchild);returnln+rn+1;}}intLeafNodeNum(Bitreebt){intln,rn;if(bt==NULL)return0;elseif(bt->lchild==NULL&&bt->rchild==NULL)return1;else{ln=LeafNodeNum(bt->lchild);rn=LeafNodeNum(bt->r