求树高算法
⑴ 如何用非递归算法求二叉树的高度
if（T＝＝null）
return0；
intfront＝－1，
rear＝－1；
／／front出队指针
rear入队指针intlast＝0，
level＝0；
／／last每一层的最右指针
（front＝＝last时候一层遍历结束level＋＋）BiTreeQ［Maxsize］；
／／模拟队列Q［＋＋rear］＝T；
BiTreep；
while(front<rear){
p＝Q［＋＋front］；／／开始出队
因为front要赶到lash
实现level＋＋
if(p->lchild)
Q[++rear] = p->lchild;
if(p->rchild)
Q[++rear] = p->rchild;
if（front＝＝last）｛
level＋＋；
last＝rear；／／last指向下层节点｝
｝
(1)求树高算法扩展阅读
非递归算法思想：
（1）设置一个栈S存放所经过的根结点（指针）信息；初始化S；
（2）第一次访问到根结点并不访问，而是入栈；
（3）中序遍历它的左子树，左子树遍历结束后，第二次遇到根结点，就将根结点（指针）退栈，并且访问根结点；然后中序遍历它的右子树。
（4）当需要退栈时，如果栈为空则结束。
⑵ 求二叉树高度的原理、算法是什么，越详细越好，C语言，谢谢
首先分析二叉树的深度（高度）和它的左、右子树深度之间的关系。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加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;
}
⑶ 以二叉链表为存储结构,写出求二叉树高度和宽度的算法
树的高度：对非空二叉树，其深度等于左子树的最大深度加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);}}。
(3)求树高算法扩展阅读
方法：
求二叉树的高度的算法基于对二叉树的三种遍历，可以用后序遍历的算法加上记录现在的高度和已知的最高的叶子的高度，当找到一个比已知高度还要高的叶子，刷新最高高度。
最后遍历下来就是树的高度，至于后序遍历的算法，是一本数据结构或者算法的书中都有介绍和参考代码
⑷ 设树采用孩子兄弟表示法存放，用类C语言设计算法计算树的高度。
采用递归求解，先求左子树的高度和右子树的高度，然后整棵树的高度就是两颗子树高度的最大值+1。假定叶子节点高度为0。代码如下：
structnode{
intval;
structnode*left;
structnode*right;
};
intheight(structnode*root)
{
inth,lh,rh;
if(root==NULL)
return-1;//这里返回-1表示叶子节点的高度为0，若规定叶子节点的高度为1，这里返回0即可
lh=height(root->left);
rh=height(root->right);
if(lh>rh)
h=lh+1;
else
h=rh+1;
returnh;
}
⑸ 二叉树的深度算法怎么算啊
二叉树的深度算法：
一、递归实现基本思想：
为了求得树的深度，可以先求左右子树的深度，取二者较大者加1即是树的深度，递归返回的条件是若节点为空，返回0
算法：
1
int
FindTreeDeep(BinTree
BT){
2
int
deep=0;
3
if(BT){
4
int
lchilddeep=FindTreeDeep(BT->lchild);
5
int
rchilddeep=FindTreeDeep(BT->rchild);
6
deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;
7
}
8
return
deep;
9
}
二、非递归实现基本思想：
受后续遍历二叉树思想的启发，想到可以利用后续遍历的方法来求二叉树的深度，在每一次输出的地方替换成算栈S的大小，遍历结束后最大的栈S长度即是栈的深度。
算法的执行步骤如下：
（1）当树非空时，将指针p指向根节点，p为当前节点指针。
（2）将p压入栈S中，0压入栈tag中，并令p执行其左孩子。
（3）重复步骤（2），直到p为空。
（4）如果tag栈中的栈顶元素为1，跳至步骤（6）。从右子树返回
（5）如果tag栈中的栈顶元素为0，跳至步骤（7）。从左子树返回
（6）比较treedeep与栈的深度，取较大的赋给treedeep，对栈S和栈tag出栈操作，p指向NULL，并跳至步骤（8）。
（7）将p指向栈S栈顶元素的右孩子，弹出栈tag，并把1压入栈tag。（另外一种方法，直接修改栈tag栈顶的值为1也可以）
（8）循环（2）~（7），直到栈为空并且p为空
（9）返回treedeep，结束遍历
1
int
TreeDeep(BinTree
BT
){
2
int
treedeep=0;
3
stack
S;
4
stack
tag;
5
BinTree
p=BT;
6
while(p!=NULL||!isEmpty(S)){
7
while(p!=NULL){
8
push(S,p);
9
push(tag,0);
10
p=p->lchild;
11
}
12
if(Top(tag)==1){
13
deeptree=deeptree>S.length?deeptree:S.length;
14
pop(S);
15
pop(tag);
16
p=NULL;
17
}else{
18
p=Top(S);
19
p=p->rchild;
20
pop(tag);
21
push(tag,1);
22
}
23
}
24
return
deeptree;
25
}
⑹ 设计算法统计二叉树高度
#include<stdio.h>
#include<malloc.h>
typedef struct binode{
int data;
struct binode *lchild,*rchild;
}binode,*bitree;
typedef struct{
bitree elem[100];
int top;
}stack;
bitree creat_bt(){ //按扩展前序建二叉树
bitree t;int x;
scanf("%d",&x);
if (x==0) t=NULL;
else { t=(bitree)malloc(sizeof(binode));
t->data=x;
t->lchild=creat_bt();
t->rchild=creat_bt();
}
return t;
}
void exchange(bitree t) //左、右子树交换
{bitree p;
if(t!=NULL)
{ p=t->lchild;t->lchild=t->rchild;
t->rchild=p;
exchange(t->lchild);
exchange(t->rchild);
}
}
void inorder(bitree bt) //递归的中序遍历
{ if (bt){
inorder(bt->lchild);
printf("% d",bt->data);
inorder(bt->rchild);
}
}
main()
{bitree root;
printf("\n");
printf("建二叉树，输入元素：");
root=creat_bt(); /*create tree of useing preorder*/
printf("交换前的中序序列是：");
inorder(root);
exchange(root);
printf("\n交换后的中序序列是：");
inorder(root);
printf("\n");
}
⑺ 二叉树求高度，用栈模拟递归.怎么实现
计算二叉树的高度可以采用几种不同的算法。 算法一：采用后序遍历二叉树，结点最大栈长即为二叉树的高度； 算法二：层次遍历二叉树，最大层次即为二叉树的高度； 算法三：采用递归算法，求二叉树的高度。
⑻ 怎么计算二叉树高度
分析二叉树的深度（高度）和它的左、右子树深度之间的关系。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加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;
}
(8)求树高算法扩展阅读：
一棵深度为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);
}
}
⑽ 以二叉链表作存储结构,试编写求二叉树高度的算法
主方法调用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);//遍历右子树
}
}