先一层一层的遍历二叉树 用一个辅助的数据结构队列
队列! 注意 这个很重要
队尾放节点 队头取出节点
比如:根节点放入队列 (开始只有这个一个节点在队列中)
然后呢 从队头取出这个根节点 然后打散 把他的左右孩子放入对尾(这时候有2个节点 也就是二叉树的第二层)
之后从队伍里取出这2个节点 打散 之后队伍里应该是 二叉树第三层的4个节点
。。。。。
这样就把二叉树层次遍历了
因为有些节点没有孩子节点 也就是叶子
这个队列中的节点 逐渐会越来越少
最后一个取出队列的节点 的深度也就是二叉树的高度
所以求二叉树的高度 就用这种层进性遍历 每次把节点放入队列中时 也把他的深度 和节点的指针一起放入 取出一个节点 打散的时候 注意他的子节点的度是他父节点的+1 就ok
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;
}
首先分析二叉树的深度(高度)和它的左、右子树深度之间的关系。从二叉树深度的定义可知,二叉树的深度应为其左、右子树深度的最大值加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;
}
队列! 注意 这个很重要
队尾放节点 队头取出节点
比如:根节点放入队列 (开始只有这个一个节点在队列中)
然后呢 从队头取出这个根节点 然后打散 把他的左右孩子放入对尾(这时候有2个节点 也就是二叉树的第二层)
之后从队伍里取出这2个节点 打散 之后队伍里应该是 二叉树第三层的4个节点
。。。。。
这样就把二叉树层次遍历了
因为有些节点没有孩子节点 也就是叶子
这个队列中的节点 逐渐会越来越少
最后一个取出队列的节点 的深度也就是二叉树的高度
所以求二叉树的高度 就用这种层进性遍历 每次把节点放入队列中时 也把他的深度 和节点的指针一起放入 取出一个节点 打散的时候 注意他的子节点的度是他父节点的+1 就ok
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;
}
首先分析二叉树的深度(高度)和它的左、右子树深度之间的关系。从二叉树深度的定义可知,二叉树的深度应为其左、右子树深度的最大值加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;
}
#include<stdio.h> #include<stdlib.h> typedef struct BiTree{ int data; struct BiTree *Lchild; struct BiTree *Rchild; }BiTree_Node,*BiTree_Link; BiTree_Link creat_BiTree(); int count; int zount; void xtravel_BiTree(BiTree_Link); void ztravel_BiTree(BiTree_Link); void htravel_BiTree(BiTree_Link); int Ycount_BiTree(BiTree_Link); int Zcount_BiTree(BiTree_Link); void BiTree_detph(BiTree_Link); void BiTree_root(BiTree_Link); int main() { BiTree_Link T; int n; printf("\n"); do { printf("**********二叉树*********\n"); printf("\n"); printf("1、构建二叉树\n"); printf("2、先序遍历二叉树\n"); printf("3、中序遍历二叉树\n"); printf("4、后序遍历二叉树\n"); printf("5、二叉树的叶子结点数\n"); printf("6、二叉树的结点数\n"); printf("7、二叉树的根\n"); printf("8、退出程序\n"); printf("\n"); printf("*************************\n"); printf("请输入要选择的操作n="); scanf("%d",&n); switch(n){ case 1: T=creat_BiTree();break; case 2: xtravel_BiTree(T);break; case 3: ztravel_BiTree(T);break; case 4: htravel_BiTree(T);break; case 5: Ycount_BiTree(T); printf("叶子结点数:%d\n",count); break; case 6: Zcount_BiTree(T); printf("结点总数:%d\n",zount); break; case 7: BiTree_root(T);break; } }while(n<8); return 0; } BiTree_Link creat_BiTree() { BiTree_Link T; int n; scanf("%d",&n); if(n==0) { T=NULL; } else { T=(BiTree_Link)malloc(sizeof(BiTree_Node)); if(NULL==T) { printf("Error!!!"); exit(1); } T->data=n; printf("输入%d的左结点:",T->data); T->Lchild=creat_BiTree(); printf("输入%d的右结点:",T->data); T->Rchild=creat_BiTree(); } return T; } void xtravel_BiTree(BiTree_Link T) { if(T!=NULL) { printf("%d ",T->data); xtravel_BiTree(T->Lchild); xtravel_BiTree(T->Rchild); } } void ztravel_BiTree(BiTree_Link T) { if(T!=NULL) { ztravel_BiTree(T->Lchild); printf("%d ",T->data); ztravel_BiTree(T->Rchild); } } void htravel_BiTree(BiTree_Link T) { if(T!=NULL) { htravel_BiTree(T->Lchild); htravel_BiTree(T->Rchild); printf("%d ",T->data); } } int Ycount_BiTree(BiTree_Link T) { if(T!=NULL) { if((T->Lchild==NULL)&&(T->Rchild==NULL)) count++; else { Ycount_BiTree(T->Lchild); Ycount_BiTree(T->Rchild); } } return count; } int Zcount_BiTree(BiTree_Link T) { if(T!=NULL) { zount++; Zcount_BiTree(T->Lchild); Zcount_BiTree(T->Rchild); } return zount; } void BiTree_root(BiTree_Link T) { if(T!=NULL) { printf("树根是:%d ",T->data); } } /*输入文件自己建立*/ #include <stdio.h> #include <string.h> #include <stdlib.h> #define max 100 int x; char ans[max]; typedef struct Tree { char val; struct Tree* pl; struct Tree* pr; }*T; T createtree( T p ) { char ch; scanf( "%c", &ch ); if( ch == '#' ) p = NULL; else { p = (T)malloc( sizeof(struct Tree) ); p->pl = createtree( p ); p->val = ch; p->pr = createtree( p ); } return p; } void view( T p ) { if( p != NULL ) { printf( "%c", p->val ); view( p->pl ); view( p->pr ); } else return ; } void bfs( T root ) { T q[max]; x = 0; T u; int front, rear; rear = front = 0; q[front++] = root; while( front > rear ) { u = q[rear++]; ans[x++] = u->val; if( u->pl != NULL ) q[front++] = u->pl; if( u->pr != NULL ) q[front++] = u->pr; } } int main() { int i; freopen( "in", "r", stdin ); T root = NULL; root = createtree( root ); printf( "文件输入: 12##3## "); printf( "\n\ndfs:\n" ); view( root ); printf( "\n\nbfs:\n" ); bfs( root ); for( i = 0; i < x; i++ ) printf( "%c", ans[i] ); return 0; }