求二叉树的结点的深度.docVIP

实验三：求二叉树结点的深度 学生姓名： 班级：@12 学号： 完成时间：2015.06.25 本人郑重声明：本实验的程序代码编写与调试、实验报告的撰写均由本人独立完成，如被发现抄袭或与其他同学作业雷同，同意取消该实验成绩！ 声明人： 2015.06.25 【实验内容】 以三元组形式输入任意二叉树（以大写字母表示结点） ，求以任意一选定结点为子树的深度。 如，在输入示范题中的二叉树之后，程序显示：Please select a node: 输入 ‘B’，回车后，程序显示 ‘3’。 【编程思路】 首先，主函数构造一个空二叉树，提示输入节点信息。接着输入根节点，作为二叉树的头。然后按三元组格式依次输入父节点和其子节点以及其子节点位置（L或R），若为L，则子节点添加为父节点的左儿子；若为R，则子节点添加为父节点的右儿子。如此继续添加，直到输入end停止。 然后，程序通过层序遍历输出二叉树的大概结构图。层序遍历用到了队列的数据结构。队列用来暂存二叉树中的结点的信息。出队时同一深度的结点依次一齐出队。最后，输入特定节点，通过前序遍历求出节点深度。 【程序代码】 1主函数 int main() { BiTree T; TElemType e1; InitBiTree(T); printf(构造空二叉树后,树空否？%d(1:是0:否), 树的深度=%d\n,BiTreeEmpty(T),BiTreeDepth(T)); e1 = Root(T); if(e1 != Nil) #ifdef CHAR printf(二叉树的根为: %c\n,e1); #endif #ifdef INT printf(二叉树的根为: %d\n,e1); #endif else printf(树空，无根\n); //三元组构建二叉树 string x; printf(输入格式说明：三元组（P,C,L/R）方式输入,P:parent, C: child, L/R: C is Ps left child / right child, 输入 end 结束输入\n); printf(eg. the root: input ^AL, its left child is B: input ABL, its right child is C: input ACR!\n); GetUserWord(x); while(x!=end) { AddNode(T, x[0], x[1], x[2]); GetUserWord(x); } if(pow(2.,BiTreeDepth(T)-1)80) PrintTree(T); else PrintTreeLevel(T); char ch; /*求树的结点的深度-作业部分*/ coutplease select a node：endl; cinch; coutThe depth is :endl; coutdepth( FindNode(ch,T))endl; } 2求结点深度的函数 int depth(BiTNode* node) //求指定结点位置的深度-作业部分 { if(node-lchild==NULLnode-rchild==NULL) return 1; int l=depth(node-lchild); int r=depth(node-rchild); return (lr)?l+1:r+1; } 【运行结果】