求二叉树高度非递归算法（C语言）

int BiTreeDepthHierarchy(BiThrTree T) //非递归类层次遍历求二叉树深度

{

int depth=0,hp,tp,lc; //hp为已访问的结点数，tp历史入队的结点总数，lc为每层最后一个结点标记

LinkQueue Q;

BiThrNode p;

if(T)

{

p=T;

hp=0;tp=1;lc=1;

InitQueue(Q);

EnQueue(Q,p);

while(!QueueEmpty(Q))

{

DeQueue(Q,p);

hp++; //hp为已访问的结点数

if(p->lchild)

{

EnQueue(Q,p->lchild);

tp++; //tp记录历史入队的结点总数

}

if(p->rchild)

{

EnQueue(Q,p->rchild);

tp++;

}

if(hp==lc) //当hp=lc时，表明本层结点均已访问完

{

depth++;

lc=tp; //lc=tp，更新下层的末结点标记

}

}

}

return depth;

}

#include <stdioh>//头文件

#include <stdlibh>

#include <malloch>

typedef struct BiTNode

{

char data;

struct BiTNode lchild,rchild;

}

BiTNode,BiTree;//定义结点类型

BiTree CreateBiTree()//创建树

{

char p;BiTree T;

scanf("%c",&p);

if(p==' ')

T=NULL;

else

{

T=(BiTNode )malloc(sizeof(BiTNode));//为结点开辟空间

T->data=p;

T->lchild=CreateBiTree();

T->rchild=CreateBiTree();

}

return (T);

}

void PreOrder(BiTree T)//先序

{

if(T!=NULL)

{

printf("%c",T->data);

PreOrder(T->lchild);

PreOrder(T->rchild);

}

}

void InOrder(BiTree T)//中序

{

if(T!=NULL)

{

InOrder(T->lchild);

printf("%c",T->data);

InOrder(T->rchild);

}

}

void PostOrder(BiTree T)//后序

{

if(T!=NULL)

{

PostOrder(T->lchild);

PostOrder(T->rchild);

printf("%c",T->data);

}

}

int Depth(BiTree T)/ 深度 /

{

if(T==NULL)

return(0);

else

return 1+(Depth(T->lchild)>Depth(T->rchild) Depth(T->lchild):Depth(T->rchild));

}

void main()//主函数

{

BiTree Ta;

Ta=CreateBiTree();

printf("先序遍历:");

printf("\n");

PreOrder(Ta);

printf("\n");

printf("中序遍历:");

printf("\n");

InOrder(Ta);

printf("\n");

printf("后序遍历:");

printf("\n");

PostOrder(Ta);

printf("\n");

printf("深度为：%d",Depth(Ta));

}

根据你给的树，你输入如下：

ABDEGJCFHKLIM

（其中代表空格，输入时代表空格）

有问题联系！

#include <iostreamh>

typedef struct BiTNode

{

char data;

int bit;

struct BiTNode lchild,rchild,parent;

}BiTNode;

void InitBT(BiTNode &t)//1、初始化，不带头结点

{

t=NULL;

}

/void InitBT(BiTNode t)//初始化，带头结点

{

t=new BiTNode;

t->lchild=t->rchild=t->parent=NULL;

}/

int EmptyBT(BiTNode t)//判断队空

{

if(t==0)

return 1;

else

return 0;

}

BiTNode creatBT(BiTNode t,int b)//2、创建二叉树

{

BiTNode p;

char ch;

cin>>ch;

if(ch=='#')return 0;

else

{

p=new BiTNode;

p->data=ch;

p->parent=t;

p->bit=b;

t=p;

t->lchild=creatBT(t,0);

t->rchild=creatBT(t,1);

}

return t;

}

void preorder(BiTNode t)//3、先序遍历

{

if(!EmptyBT(t))

{

cout<<t->data;

preorder(t->lchild);

preorder(t->rchild);

}

}

void inorder(BiTNode t)//中序遍历

{

if(!EmptyBT(t))

{

inorder(t->lchild);

cout<<t->data;

inorder(t->rchild);

}

}

void postorder(BiTNode t)//后序遍历

{

if(!EmptyBT(t))

{

postorder(t->lchild);

postorder(t->rchild);

cout<<t->data;

}

}

void coutBT(BiTNode t,int &m,int &n,int &i)//4、计算二叉树中叶子结点、度为2的结点和度为1的结点的个数

{

if(!EmptyBT(t))

{

if((t->lchild==0) && (t->rchild==0))

m++;//叶子结点

else if((t->lchild!=0) && (t->rchild!=0))

i++;//度为2的结点

else

n++;//度为1的结点

coutBT(t->lchild,m,n,i);

coutBT(t->rchild,m,n,i);

}

}

void coutNode(BiTNode t,int &k)//5、求二叉树中结点个数

{

if(!EmptyBT(t))

{

k++;

coutNode(t->lchild,k);

coutNode(t->rchild,k);

}

}

int BTdepth(BiTNode t)//6、求二叉树的深度

{

int i,j;

if(EmptyBT(t))

return 0;

else

{

i=BTdepth(t->lchild);

j=BTdepth(t->rchild);

return (i>ji:j)+1;

}

}

int Xdepth(BiTNode t,char x)//7、查找x的层数

{

int num1,num2,n;

if(t==NULL)

return 0;

else{

if(t->data==x)

return 1;

num1=Xdepth(t->lchild,x);

num2=Xdepth(t->rchild,x);

n=num1+num2;

if(num1!=0||num2!=0)

n++;

return n;

}

}

static int flag;

void SearchChild(BiTNode t,int k)//8、查找第k个结点的左右孩子

{

if(!EmptyBT(t))

{

if(k==0)

{

cout<<"位置不能为0!"<<endl;

return;

}

else

{

flag++;

if(flag==k)

{

if(t->lchild==0)

cout<<"无左孩子! ";

else

cout<<"左孩子为："<<(t->lchild->data)<<" ";

if(t->rchild==0)

cout<<"无右孩子!"<<endl;

else

cout<<"右孩子为："<<(t->rchild->data)<<endl;

}

else

{

SearchChild(t->lchild,k);

SearchChild(t->rchild,k);

}

}

}

}

int Xancestor(BiTNode t,char x)//9、查找x结点祖先

{

int n,num1,num2;

if(t==NULL)

return 0;

else

{

if(t->data==x)

return 1;

num1=Xancestor(t->lchild,x);

num2=Xancestor(t->rchild,x);

n=num1+num2;

if(n!=0)

{

n++;

cout<<t->data<<" "<<endl;

}

}

}

void BTNodePath(BiTNode t)//10、输出所有叶子结点路径

{

if(!EmptyBT(t))

{

if((t->lchild==0) && (t->rchild==0))

{

cout<<t->data<<"的路径为：";

for(BiTNode p=t;p!=0;p=p->parent)

cout<<p->data;

cout<<endl;

}

else

{

BTNodePath(t->lchild);

BTNodePath(t->rchild);

}

}

}

void BTNodebit(BiTNode t)//11、输出所有叶子结点编码

{

if(!EmptyBT(t))

{

if((t->lchild==0) && (t->rchild==0))

{

cout<<t->data<<"的编码为：";

for(BiTNode p=t;p->parent!=0;p=p->parent)

cout<<p->bit;

cout<<endl;

}

else

{

BTNodebit(t->lchild);

BTNodebit(t->rchild);

}

}

}

void main()

{

BiTNode t;

int m,n,i,d,q,k;

char x;

cout<<"1、初始化"<<endl;

InitBT(t);

cout<<"2、创建二叉树"<<endl;

t=creatBT(t,0);

cout<<"31、先序遍历"<<endl;

preorder(t);

cout<<endl;

cout<<"32、中序遍历"<<endl;

inorder(t);

cout<<endl;

cout<<"33、后序遍历"<<endl;

postorder(t);

cout<<endl;

m=n=i=0;

cout<<"4、计算叶子结点，度为1的结点和度为2的结点的个数"<<endl;

coutBT(t,m,n,i);

cout<<"叶子结点个数为："<<m<<endl;

cout<<"度为1的结点个数为："<<n<<endl;

cout<<"度为2的结点个数为："<<i<<endl;

q=0;

cout<<"5、计算结点个数"<<endl;

coutNode(t,q);

cout<<"结点个数为："<<q<<endl;

d=0;

cout<<"6、计算深度"<<endl;

d=BTdepth(t);

cout<<"深度为："<<d<<endl;

cout<<"7、求x的层数"<<endl;

cout<<"输入x：";

cin>>x;

if(Xdepth(t,x)==0)

cout<<"x不存在！"<<endl;

else

cout<<Xdepth(t,x)<<endl;

cout<<"8、输入要查找孩子的结点在先序遍历中的位置k（不等于0）：";

cin>>k;

SearchChild(t,k);

if(k>flag)

cout<<"位置超出长度!"<<endl;

cout<<"9、查询结点的所有祖先，请输入结点x：";

cin>>x;

int num;

num=Xancestor(t,x);

if(num==0)

cout<<"结点不存在！"<<endl;

if(num==1)

cout<<"根结点无祖先！"<<endl;

cout<<"10、输出所有叶子结点路径（叶→根）："<<endl;

BTNodePath(t);

cout<<"11、输出所有叶子结点编码（叶→根）："<<endl;

BTNodebit(t);

}

以上就是关于求二叉树高度非递归算法（C语言）全部的内容，包括:求二叉树高度非递归算法（C语言）、用C实现二叉树的建立，先序、中序、后序历遍，深度算法。紧急！！、二叉树的基本 *** 作 C语言版的等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！