题目

写一个算法求一棵二叉树的深度，二叉树以二叉链表为存储结构

求二叉树深度的函数

//求二叉树深度
int getDepth(BTNode *T)
{int LD,RD;//左右子树的深度if(T==NULL){return 0;//设定空树的深度为0}else{//采用后根遍历LD=getDepth(T->lchild);//求左子树的深度RD=getDepth(T->rchild);//求有紫苏的深度return (LD>RD?LD:RD)+1;//三目运算符,返回左右子树中较大的那个，然后加一，这是因为二叉树的根没有计算}
}

#源码

这里用的测试二叉树如下图

#完整测试程序

#include<iostream>
using namespace std;//二叉树链表结点
typedef struct BTNode{struct BTNode *lchild;struct BTNode *rchild;char data;	//默认数据类型char，若有不同，更改即可
}BTNode;//构造二叉树
BTNode *createbinarytree()	//利用递归思想构造二叉树
{char element;cin>>element;	//输入二叉树的根节点的data值BTNode *T;if(element!='s')	//设置终止条件,s代表stop{T=(BTNode*)malloc(sizeof(BTNode));T->data=element;cout<<"please input the left child node of "<<element<<endl;T->lchild=createbinarytree();cout<<"please input the right child node of "<<element<<endl;T->rchild=createbinarytree();}else{T=NULL;}return T;
}//求二叉树深度
int getDepth(BTNode *T)
{int LD,RD;//左右子树的深度if(T==NULL){return 0;//设定空树的深度为0}else{//采用后根遍历LD=getDepth(T->lchild);//求左子树的深度RD=getDepth(T->rchild);//求有紫苏的深度return (LD>RD?LD:RD)+1;//三目运算符,返回左右子树中较大的那个，然后加一，这是因为二叉树的根没有计算}
}int main()
{BTNode *T;T=createbinarytree();cout<<"the depth of this tree is "<<getDepth(T)<<endl;return 0;
}

测试结果