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

同上，希望高手解答。

热心网友 · 2018-4-30 02:07:47

求2叉树深度
输入：123$$4$$56$$7$$
输出：1234567
depth:3
#include
#include

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));
}

热心网友 · 2018-4-30 02:07:48

给你一个完整的例子吧。学习一下#include
#include
#include
#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");
}

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

2 个回复