以二叉链表为存储结构,写出求二叉树高度和宽度的算法
主方法调用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);//遍历右子树
}
}
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);
}
}
树的高度：对非空二叉树，其深度等于左子树的最大深度加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);}}。
扩展资料
方法：
求二叉树的高度的算法基于对二叉树的三种遍历，可以用后序遍历的算法加上记录现在的高度和已知的最高的叶子的高度，当找到一个比已知高度还要高的叶子，刷新最高高度。
最后遍历下来就是树的高度，至于后序遍历的算法，是一本数据结构或者算法的书中都有介绍和参考代码
原题：
以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法。所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。
标准答案：
①求树的高度
思想：对非空二叉树，其深度等于左子树的最大深度加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)
{
int
front=-1,rear=-1;/*
队列初始化*／
int flag=0,count=0,p;
/* p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值。*／if(T!=Null)
{
rear++;
q[rear]=T;
flag=1;
p=rear;
}
while(front<p)
{
front++;
T=q[front];
if(T->lchild!=Null)
{
rear++;
q[rear]=T->lchild;
count++;
}
if(T->rchild!=Null)
{
rear++;
q[rear]=T->rchild;
count++;
}
if(front==p)
/* 当前层已遍历完毕*/
{
if(flag<count)
flag=count;
count=0;
p=rear; /* p指向下一层最右边的结点*/
}
}
/* endwhile*/
return(flag);
}
递归，用一个一维数组维护各层的节点数信息。层序遍历 类似BFS 借助一个队列。
以二叉链表为存储结构,写出求二叉树高度和宽度的算法
答：以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法。所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。标准答案：①求树的高度 思想：对非空二叉树，其深度等于左子树的最大深度加1。Int Depth(BinTree T){ int dep1,dep2;if(T==Null)return(0);else { dep1=Dept...
以二叉链表为存储结构,分别写出求二叉树结点总数及叶子总数的算法...
答：【答案】：(1)计算结点总数 int CountNode(BinTree*root){ intnum1,num2;if(root==Null)return(0);else if(root-＞lchild==Null＆＆rooot-＞rchild==Null)return(1);else { num 1=CountNode(root-＞lchild);num 2=CountNode(root-＞rchild);return(num1+num2+!);} } (2)计算叶子总数...
已知二叉树采用链表存储结构,根结点指针为T,请写出计算二叉树中度为2...
答：采用深度或者广度遍历就可以，分别采用栈或者队列结构。对于访问到的每个节点，如果度为2，就是所求的。比如用栈的话 push(ST,root)while(not empty(ST)){ node=pop(ST)if(node->left)push(ST,node->left)if(node->right)push(ST,node->right)} 上面的伪代码实际上就是图的深度遍历，二叉树...
以二叉链表为存储结构,分别写出求二叉树结点总数及叶总数的算法。(数据...
答：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);...
以二叉链表为存储结构。分别写出在二叉树中查找值为X的结点及求X所在的...
答：typedef struct BiTree{ int data;BiTree *lchild;BiTree *rchild;}BiTree;BiTree* CreateTree(int n){ BiTree *t;if (n <= 0 || n> NUM_NODE) return NULL;if (!(t = (BiTree*)malloc(sizeof(BiTree)))return NULL;t->data = n;printf("%d ", t->data);t->lchild = Cre...
以二叉链表作存储结构,试编写求二叉树高度的算法
答：以二叉链表作存储结构,试编写求二叉树高度的算法,谢谢了 素素Beauty88 | 浏览1587 次 |举报 我有更好的答案推荐于2017-12-16 16:48:21 最佳答案 主方法调用RootFirst(&root,0);即可,g_nMax 即为最终的树的高度。int g_nMax = 0;voild RootFirst(TreeNode *p,int nLevel){ if (null == p->left...
已知一棵二叉树是以二叉链表的形式存储的求出以T为根的子树的结点个数...
答：已知一棵二叉树是以二叉链表的形式存储的,其结点结构说明如下:structnode{intdata;structnode*left;structnode*right;};要求写出2个具有下面功能的算法:①、求出以T为根的子树的结... 已知一棵二叉树是以二叉链表的形式存储的,其结点结构说明如下:struct node{int data;struct node * left;struct node * right...
假设二叉树采用二叉链表作为存储结构,试编写一个算法:求任意一个指定结...
答：构造变量count记录当前层访问到的节点数，nextcount记录当前层的总个数；每当访问过一层层数depth++；此种方法同时可以求最大宽度，访问第几层的第几个节点，求带权路径长度WPL，是一种通用方法！int TreeDepth(TreeNode* pRoot){queueq;q.push(pRoot);if(pRoot==NULL)return 0;TreeNode* p；int...
假设二叉树以二叉链表作为存储结构,试设计一个计算二叉树叶子结点树的...
答：1、首先要定义两个类：结点类和二叉树类。2、二叉树类的组成：建立树的函数、遍历函数、删除函数。求结点数函数。3、采用递归的思想，遇到标识符表示该结点为空，否则开辟空间创建新结点，同时调用递归开辟左结点和右结点。4、前序遍历函数。5、删除函数的思路：如果当前结点不为空，采用递归访问左结点...
采用二叉链表作为存储结构,完成二叉树的建立,前序、中序和后序遍历的...
答：//后序遍历二叉树 void lasTraverse(BiTree T){ if(T==NULL){return;} lasTraverse(T->Lchild);lasTraverse(T->Rchild);printf("%d ",T->data);} //求二叉树的深度 int TreeDeep(BiTree T){ int deep=0;if(T){ int leftdeep=TreeDeep(T->Lchild);int rightdeep=TreeDeep(T->...
