求二叉树结点的深度

求二叉树结点的深度 实验三:求二叉树结点的深度 学生姓名: 班级:@12 学号: 完成时间:2015.06.25 本人郑重声明:本实验的程序代码编写与调试、实验的撰写均由本人独立完成，如被发现抄袭或与其他同学作业雷同，同意取消该实验成绩～ 声明人: 2015.06.25 【实验内容】 I. 以三元组形式输入任意二叉树(以大写字母示结 点) ，求以任意一选定结点为子树的深度。 II. 如，在输入示范题中的二叉树之后，程序显示: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 P's 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; /*求树的结点的深度-作业部分*/ cout<<"please select a node:"<>ch; cout<<"The depth is :"<lchild==NULL&&node->rchild==NULL) return 1; int l=depth(node->lchild); int r=depth(node->rchild); return (l>r)?l+1:r+1; } 【运行结果】