求二叉树的高度

Question

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

Answer 1

公式:V0=(V2)
+2(
V3)+3
(V4)....(k-1)(Vk)+1
所有的树都满足这个公式，其中v0...vk代表
度为0...K的节点个数。
所有计算度与节点个数的问题无论是几叉树的都必须用这个式子，我建议楼主哥哥记住!
叶子节点就是度为0的节点V0，其他的分支节点度都为m那么就只存在度为0和度为m的节点
代入上面公式:
V0=(m-1)Vm+1
又因为:
Vm+V0=n
//因为树总共n个节点
解这个方程组，就得
V0=((m-1)n+1)/m
用计算机计算
，你可以将它理解成一个层序遍历的过程，使用队列来遍历:
存储结构是
typedef
struct
Node
{
int
data;
struct
node
*FirstChild;
struct
node
*NextBrother;
}*Tree;
static
int
leafnum;
//全局函数用于计数叶子节点
void
BFSCount(Tree
t)
{
int
i=0;
SeqQueue
*Q;
TreeNode
*p;
InitQueue(Q);
if(t==NULL)
return;
EnterQueue(Q,t);
While(!Empty(Q))
{
DeleteQueue(Q,p);
//出队
然后判断这个节点
if(p->FirstChild==NULL)
leafnum++;
//如果这个节点一个孩子也没有，则是叶子，计数+1
else{
p=t->FirstChild;
//否则开始将它第一个孩子继续进入队
EnterQueue(Q,p);
while(i<=m)
//把第一个孩子的下一个兄弟依次入队
{
p=p->NextBrother;
EnterQueue(Q,p);
}
}
}
}

Answer 2

什么叫二叉树的度？带你了解它的特点

Answer 3

高度为h的二叉树上只有度为0和度为2的结点。则此二叉树中所含的结点数至少为除了root层每层只有两个节点，如果root层为0层，那么结果为B，如果root层为1层，那么结果为C！
其实有时候这种选择题模棱两可，你知道解题原理就行了！考试的时候要看你考试的要求作答就没问题了！

Answer 4

#include <stdio.h>
#include <stdlib.h>

#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[i] != '\0')
{
switch(tree[i])
{
case '(':
top ++;
stack[top] = newnode;
flag = 0;
break;
case ')':
top --;
break;
case ',':
flag = 1;
break;
default:
newnode = (Node *)malloc(sizeof(Node));
newnode->k = tree[i];
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;
}
绝对可以运行!本回答被提问者采纳

Answer 5

楼上是遍历

假如树的定义是
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;
}
}