链式存储二叉树求高度
主方法调用RootFirst(&root,0);即可，g_nMax 即为最终的树的高度。
int g_nMax = 0;
voild RootFirst(TreeNode *p,int nLevel)
{
if (null == p->left && null == p->right) //当前为叶子节点
{
if (g_nMax < nLevel)
{
g_nMax = nLevel;
return;
}
}
if(null != p->left )
{
RootFirst(p->left,nLevel+1);//遍历左子树
}
if(null != p->right)
{
RootFirst(p->right,nLevel+1);//遍历右子树
}
}
❷ C程序，求二叉树的树高
#include "stdio.h"
#include "malloc.h"
#include "math.h"
#include "string.h"
#define MAX 100
void exit(int);
/*--------------------*/
int count; /* 记录二叉树中的二度结点的个数 */
int flag; /* 标明二叉树是否为AVL树 */
/*--------------------*/
typedef struct node{
char d;
struct node *lchild,*rchild;
}TNode;
/*-----通过中序序列和后序序列建树-----*/
void MkTree(char in[],int is,int ie,char post[],int posts,int poste,TNode **r)
{
int i;
if(is>ie || posts>poste)
*r=NULL;
else{
*r=malloc(sizeof(TNode));
(*r)->d=post[poste];
for(i=is;i<=ie;i++)
if(post[poste]==in){
MkTree(in,is,i-1,post,posts,posts+i-is-1,&(*r)->lchild);
MkTree(in,i+1,ie,post,posts+i-is,poste-1,&(*r)->rchild);
break;
}
if(i>ie){
printf("error:input contains an error!\n");
exit(9);
}
}
}
/*-----前序遍历二叉树-----*/
void preorder(TNode *r)
{
if(r){
printf("%c",r->d);
preorder(r->lchild);
preorder(r->rchild);
}
}
/*-----求二叉树中二度结点的个数-----*/
void BNode(TNode *r)
{
if(r){
if(r->lchild&&r->rchild)
count++;
BNode(r->lchild);
BNode(r->rchild);
}
}
/*-----求二叉树中叶子的个数-----*/
int leaf(TNode *r)
{
if(r==NULL)
return 0;
else
if(r->lchild==NULL && r->rchild==NULL)
return 1;
else
return leaf(r->lchild) + leaf(r->rchild);
}
/*-----求二叉树中叶子的高度-----*/
int Height(TNode *r)
{
int h1,h2;
if(r==NULL)
return 0;
else{
h1=Height(r->lchild);
h2=Height(r->rchild);
if(abs(h1-h2)>1)
flag=1;
return 1+(h1>h2?h1:h2);
}
}
void main()
{
TNode *r;
int height;
char post[MAX],in[MAX];
printf("Input inorder and postorder :\n");
gets(in);
gets(post);
MkTree(in,0,strlen(in)-1,post,0,strlen(post)-1,&r);
printf("The preorder is as follows:\n");
preorder(r);
printf("\nThere are %dletters in the tree.\n",leaf(r));
count=0;
BNode(r);
printf("\nThere are %d binarynode in the tree.\n",count);
flag=0;
height=Height(r);
printf("\nThe height of the tree is %d\n",height);
if(flag==1)
printf("\nThis bintree is not an AVL!\n");
else
printf("\nThis bintree is an AVL!\n");
}
❸ 设一棵二叉树以二叉链表为存储结构，结点结构为（lchild,data,rchild），设计一个算法求二叉树的高度
typedef struct node
{
char data
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));
}
❹ 以二叉链表为存储结构,写程序求出二叉树的高度，宽度,结点总数,叶子结点总数
int CountNode (BTNode *t) //节点总数 { int num; if (t == NULL) num = 0; else num = 1 + CountNode (t->lch) + CountNode (t->rch); return (num); } void CountLeaf (BTNode *t) //叶子节点总数 { if (t != NULL) { if (t->lch == NULL && t->rch == NULL) count ++; // 全局变量 CountLeaf (t->lch); CountLeaf (t->rch); } }
❺ 以二叉树链表作为二叉树的存储结构，怎么编写算法计算返回二叉树的高度
编写方法如下：
❻ 假设二叉树采用链式方法存储,编写一个计算一棵二叉树t的高度的函数
#include "stdio.h"
#include "stdlib.h"
int BiTreeDepth(BiTree T)
{ int h1,h2,h;
if (T==NULL)
return 0;
else
{ h1=BiTreeDepth(T->lchild);
h2=BiTreeDepth(T->rchild);
if (h1>h2)
h=h1+1;
else
h=h2+1;
}
return h;
}
❼ 怎么计算二叉树高度
分析二叉树的深度（高度）和它的左、右子树深度之间的关系。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。
int Depth (BiTree T ){ // 返回二叉树的深度
if ( !T ) depthval = 0;
else {
depthLeft = Depth( T->lchild );
depthRight= Depth( T->rchild );
depthval = 1 + (depthLeft > depthRight ?
depthLeft : depthRight);
}
return depthval;
}
(7)链式存储二叉树求高度扩展阅读：
一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子结点，至多有2k-1个结点。
二叉树的深度是从根节点开始（其深度为1）自顶向下逐层累加的；而二叉树高度是从叶节点开始（其高度为1）自底向上逐层累加的。虽然树的深度和高度一样，但是具体到树的某个节点，其深度和高度是不一样的。
❽ 假设以二叉链表作为二叉树的存储结构，试编写一个求树的高度的算法
#include<iostream.h>
#include<malloc.h>
#define FALSE 0
#define TRUE 1
#define OK 1
#define maxsize 100
typedef int status;
typedef int elemtype;
typedef struct binode
{
elemtype data;
struct binode *lchild,*rchild;
}binode,*bitree;
status treecreated=FALSE;
int leafcount=0;
status createbitree(bitree *t);
status preordertraverse(bitree t);
int height(bitree t);
void swap(bitree *t);
void leafcounts(bitree t);
void main()
{
int choice=0;
status leave=FALSE,flag;
binode *bt;
cout<<"===========二叉树演示程序==============="<<endl;
do
{
cout<<"1：创建一个二叉树，按先序遍历结果输入，空用0表示 "<<endl;
cout<<"2：先序遍历二叉树，递归方式遍历二叉树 "<<endl;
cout<<"3：求叶子数"<<endl;
cout<<"4：计算二叉树的高度"<<endl;
cout<<"5: 树进行左右翻转"<<endl;
cout<<"0：退出"<<endl;
cout<<"-------请输入你的选择:"<<endl;
cin>>choice;
switch(choice)
{
case 1:
if(treecreated)
{
cout<<"sorry,the tree has been already created!"<<endl;
break;
};
cout<<"请输入代表树的数字："<<endl;
flag=createbitree(&bt);
if(flag==OK)
{
cout<<"你已经建立了一棵树了！"<<endl;
treecreated=TRUE;
}
break;
case 2:
if(!treecreated)
{
cout<<"sorry,you must create a tree for further steps!"<<endl;
break;
}
cout<<"先序遍历顺序:"<<endl;
preordertraverse(bt);
cout<<endl;
break;
case 3:
if(!treecreated)
{
cout<<"sorry,you must create a tree for further steps!"<<endl;
break;
}
leafcounts(bt);
cout<<"树的叶子数:"<<leafcount<<endl;
cout<<endl;
break;
case 4:
int h;
h=height(bt);
cout<<"树的高度:"<<h<<endl;
break;
case 5:
swap(&bt);
cout<<"树已经翻转！！！"<<endl;
break;
case 0:
leave=TRUE;
break;
}
}while(!leave);
cout<<" 谢谢 再见了！！！"<<endl;
}
//递归方法实现创建
status createbitree(bitree *t)
{
int ch=0;
cin>>ch;
if(ch==0) //输入如果是0表示是空
(*t)=NULL;
else
{
(*t)=(bitree)malloc(sizeof(binode)); //申请空间
(*t)->data=ch; //把数据传给他
createbitree(&(*t)->lchild); //左孩子重新进入创建函数
createbitree(&(*t)->rchild); //右孩子重新进入创建函数
}
return OK;
}
//递归方法实现先序遍历
status preordertraverse(bitree t)
{
if(t)
{
cout<<t->data<<" "; //先把头结点输出
preordertraverse(t->lchild); //然后是左结点
preordertraverse(t->rchild); //然后是右结点
return OK;
}
else
return OK;
}
int height(bitree t)
{
int hl,hr;
if(t==NULL)
return 0;
hl=height(t->lchild)+1; //最下面的左孩子加一
hr=height(t->rchild)+1; //最下面的右孩子加一
return (hl>hr?hl:hr); //比较谁大就取谁
}
void swap(bitree *t) //进行左右翻转
{
bitree p;
if(*t!=NULL)
{
p=(*t)->lchild; //p为中间变量
(*t)->lchild=(*t)->rchild;
(*t)->rchild=p;
swap(&(*t)->lchild);
swap(&(*t)->rchild);
}
}
void leafcounts(bitree t) //求叶子数
{
if(t) //如果不为空
{
if(t->lchild==NULL && t->rchild==NULL)//左右孩子都为空 表明是叶子
leafcount++;
leafcounts(t->lchild);
leafcounts(t->rchild);
}
}
❾ 以二叉树链表作为二叉树的存储结构，编写算法计算返回二叉树的高度
楼主看样子是才学数据结构吧...我以前学过，忘很多了，看这么高的分，我就顺便复习一下吧；
首先理解一下什么是高度：高度其实也叫深度，我通俗点说就是 比如根节点 是第一层，根节点的左右孩子为第二层，然后根节点的左右孩子各自的孩子为第三层.....那么二叉树的高度就是这棵树最大的层数。这么说不知道楼主明白了没有，举例就是：如果只有一个根节点，那么高度就是1，如果有一个根节点再加上根节点的两个孩子，或者其中一个孩子，那么高度就是2；
那根据这样 如果用递归的思想，我想算法就比较好写了，就是统计一下根节点的左右孩子的高对呗，看哪个的高度更大那二叉树高度就是那个呗。下面我粘贴出网上的两个算法（我没去运行试过，错了别怪我）顺便解释一下：
#include<stdio.h>
#include<stdlib.h> //头文件就不用说了吧
typedef struct Node{
char data;
struct Node* lchild;
struct Node* rchild;
}Node,*Tree; //二叉树的定义也不用多说吧那个data的数据类型char可以任意换是吧
int max(int m, int n)
{
if (m > n)
return m;
else
return n;
} //这个我想能够看明白 求两个数最大值，为什么要求最大值上面也说了
int TreeHeight(Node *root)
{
if (root == NULL)
return 0; //如果根节点都没有 那高度肯定就是0了 是吧
else
return 1 + max(TreeHeight(root->lchild), TreeHeight(root->rchild));
} //否则递归计算他的左右孩子的高度然后在加上根节点的层数1 对吧
int height(Node *t) //第二个算法（其实和第一个一样）
{
if(t==NULL)
return 0;
else
{
int m=height(t->lchild);
int n=height(t->rchild); //递归计算该节点的左右孩子的高度
return(m>n)?m+1:n+1; //只不过这里没有用到上面求最大值的那个函数，楼主应该学过C
} //吧，这就是个逗号表达式，判断？A：B 判断满足就返回A不满
} //足就返回B 那这句换还是一样就是求m和n的最大值然后加1返 回
大概就这么个意思，如果程序没通过，楼主可以试着按这个想法稍微改改。
分能给我么？
❿ 以二叉链表为存储结构,写出求二叉树高度和宽度的算法
树的高度：对非空二叉树，其深度等于左子树的最大深度加1。
Int Depth(BinTree *T){int dep1,dep2;
if(T==Null) return(0);
else{dep1=Depth(T->lchild);
dep2=Depth(T->rchild);
if(dep1>dep2) return(dep1+1);
else return(dep2+1);}
树的宽度：按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。
int Width(BinTree *T){intfront=-1,rear=-1;
/*队列初始化*／int flag=0,count=0,p;
/* pint CountNode (BTNode *t)
//节点总数{int num;if (t == NULL)num = 0;
elsenum = 1 + CountNode (t->lch) + CountNode (t->rch);
return (num);}void CountLeaf (BTNode *t)
//叶子节点总数{if (t != NULL){if (t->lch == NULL && t->rch == NULL)count ++;
// 全局变量CountLeaf (t->lch);CountLeaf (t->rch);}}。
(10)链式存储二叉树求高度扩展阅读
方法：
求二叉树的高度的算法基于对二叉树的三种遍历，可以用后序遍历的算法加上记录现在的高度和已知的最高的叶子的高度，当找到一个比已知高度还要高的叶子，刷新最高高度。
最后遍历下来就是树的高度，至于后序遍历的算法，是一本数据结构或者算法的书中都有介绍和参考代码