求二叉树的高度

C++做要详细具体步骤并且有运行结果的

DestroyofLight · 2018-4-30 02:34:20

楼上是遍历

假如树的定义是
struct Type{
int data;
Type *l;
Type *r;
};
那么我写的这个函数就能返回高度
int getHight(Type *root){
if(root->l==NULL && root->r==NULL)
  return 1;
else{
  int a = 0,b = 0;
  if(root->r!=NULL)
a = getHeight(root->r)+1;
  if(root->l!=NULL)
b = getHeight(root->l)+1;
  return (a>b)?a:b;
}
}

luckydmz · 2018-4-30 02:34:19

你没有给二叉树的数据结构，没办法给出算法

qswb · 2018-4-30 02:34:18

用深搜

叶子的问题 · 2018-4-30 02:34:17

#include
#include

#define MAX 10001

// 树节点
typedef struct node
{
char k;
struct node *lchild;
struct node *rchild;
} Node;

int max(int m, int n)
{
if (m > n)
      return m;
else
      return n;
}

// 获取二叉树的高度
int TreeHeight(Node *root)
{
if (root == NULL)
      return 0;
else
      return 1 + max(TreeHeight(root->lchild), TreeHeight(root->rchild));
}

// 建立二叉树
Node *BuildTree(char *tree)
{
Node *root, *newnode, *stack[MAX];
int i = 0, top = -1, flag = 0;
root = newnode = NULL;
while(tree != '\0')
{
      switch(tree)
      {
         case '(':
            top ++;
            stack[top] = newnode;
            flag = 0;
            break;
         case ')':
            top --;
            break;
         case ',':
            flag = 1;
            break;
         default:
            newnode = (Node *)malloc(sizeof(Node));
            newnode->k = tree;
            newnode->lchild = newnode->rchild = NULL;
            if (root == NULL)
                  root = newnode;
            else {
                  if (!flag)
                     stack[top]->lchild = newnode;
                  else
                     stack[top]->rchild = newnode;
            }
            break;
      }
      i++;
}
return root;
}

// 释放二叉树
void DestroyTree(Node *root)
{
if (root == NULL)
      return ;
else {
      DestroyTree(root->lchild);
      DestroyTree(root->rchild);
      free(root);
}
}

int main()
{
char tree[MAX];
Node *root = NULL;
printf("Input B Tree  = ");
scanf("%s", tree);
root = BuildTree(tree);
printf("Tree Height = %d\n", TreeHeight(root));
DestroyTree(root);
return 0;
}
绝对可以运行!

求二叉树的高度

4 个回复