Question

以二叉链表作存储结构，编写二叉树深度的递归算法（c++语言）

同上，希望高手解答。

Answer 1

给你一个完整的例子吧。学习一下#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAX(a,b) (a>b?a:b)typedef char TElemType;
typedef int Status;//二叉树的二叉链表存储结构
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;//先序遍历生成二叉树
Status CreatBiTree(BiTree &T){
TElemType ch,temp;
printf("输入一个元素: ");
scanf("%c",&ch);
temp=getchar(); //结束回车
if(ch==' ') T=NULL; //输入空格表示结点为空树
else{
if(!(T=(BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data=ch; //生成根结点
CreatBiTree(T->lchild); //构造左子树
CreatBiTree(T->rchild); //构造右子树
}
return OK;
}//打印元素
Status PrintElem(TElemType e){
printf("%c ",e);
return OK;
}//先序遍历二叉树
Status PreOrderTraverse(BiTree T,Status (* Visit)(TElemType e)){
if(T){ //二叉树不为空时
if(Visit(T->data)) //访问根结点
if(PreOrderTraverse(T->lchild,Visit)) //先序遍历左子树
if(PreOrderTraverse(T->rchild,Visit)) return OK; //先序遍历右子树
return ERROR;
}
else return OK;
}//中序遍历二叉树
Status InOrderTraverse(BiTree T,Status (* Visit)(TElemType e)){
if(T){
if(InOrderTraverse(T->lchild,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->rchild,Visit)) return OK;
else return ERROR;
}
return OK;
}//后序遍历二叉树
Status PostOrderTraverse(BiTree T,Status (* Visit)(TElemType e)){
if(T){
if(PostOrderTraverse(T->lchild,Visit))
if(PostOrderTraverse(T->rchild,Visit))
if(Visit(T->data)) return OK;
else return ERROR;
}
return OK;
}//求二叉树的深度
int BiTreeDepth(BiTree T){
if(!T) return 0; //二叉树为空树时
int Dl=0,Dr=0;
if(T->lchild) Dl=BiTreeDepth(T->lchild); //求左子树深度
if(T->rchild) Dr=BiTreeDepth(T->rchild); //求右子树深度
return MAX(Dl,Dr)+1;
} //主函数
void main()
{
BiTree T;
Status (* Visit)(TElemType);
Visit=PrintElem;
CreatBiTree(T);
printf("\n先序遍历:");
PreOrderTraverse(T,Visit);
printf("\n中序遍历:");
InOrderTraverse(T,Visit);
printf("\n后序遍历:");
PostOrderTraverse(T,Visit);
printf("\n二叉树深度为%d",BiTreeDepth(T));
printf("\n程序结束.\n");
}

Answer 2

求2叉树深度
输入：123$$4$$56$$7$$
输出：1234567
depth:3
#include <stdio.h>
#include <stdlib.h>

typedef struct btree {
btree* lhs;
btree* rhs;
char val;
} *node, btree;

node btree_create()
{
char c;
node t = (node)malloc(sizeof(btree));
t->lhs = t->rhs = NULL;
c = getchar();
if(c != '$') {
t->val = c;
t->lhs = btree_create();
t->rhs = btree_create();
} else
return NULL;
return t;
}

void btree_traversal(node h)
{
if(h) {
putchar(h->val);
btree_traversal(h->lhs);
btree_traversal(h->rhs);
}
}

int btree_depth(node h)
{
int l, r;
if(h) {
l = btree_depth(h->lhs) + 1;
r = btree_depth(h->rhs) + 1;
return l > r ? l : r;
}
return 0;
}

int main(void)
{
node head = btree_create();
btree_traversal(head);
printf("\ndepth:%d\n", btree_depth(head));
}