有关 二叉树的几个问题
程序在win-tc和tc2.0下调试通过：
#include
#include
#include
struct tree
{
char info;
struct tree *left;
struct tree *right;
};
struct tree *root; /*树的第一个结点*/
struct tree *construct(struct tree *root, struct tree *r, char info);
void print(struct tree *r, int l);
int main(void)
{
char s[80];
root = NULL;
do
{
printf("Please input a character:");
gets(s);
root = construct(root,root,*s);
}while(*s);
print(root,0);
getch();
return 0;
}
struct tree *construct(
struct tree *root,
struct tree *r,
char info)
{
if(!r)
{
r = (struct tree *)malloc(sizeof(struct tree));
if(!r)
{
printf("内存分配失败！");
exit(0);
}
r->left = NULL;
r->right = NULL;
r->info = info;
if(!root)
return r;
if(info info)
root->left = r;
else
root->right = r;
return r; /*是return r;还是return root;*/
}
if(info info)
construct(r,r->left,info);
else
construct(r,r->right,info);
return root;
}
void print(struct tree *r, int l)
{
int i;
if(!r)
return;
print(r->left,l+1);
for(i = 0;i < l;++i)
printf(" ");
printf("%c
",r->info);
print(r->right,l+1);
}
上面的是采用中序遍历，采用前序遍历和后序遍历的函数如下：
void scan(struct tree root)(前序遍历)
{
if(!root)return;
if(root->info);
执行相应操作;
scan(root->left);
scan(root->right);
}
void scan(struct tree root)(后序遍历)
{
if(!root)return;
scan(root->left);
scan(root->right);
if(root->info);
执行相应操作;
}
应该是B吧
第一题:n0=n2+1
n0=5
n2=4
n1=25-5-4=16
第二题:
n2=23
n1=24
n1=0;
说明是满二叉树
log2(47+1)=log2(48) 向上取整就是 6
第一问：由公式n0=n2+1 （其中n0代表度为0的叶子节点的个数，n2代表度为2的叶子节点的个数）可得，n2为4。所以度为1的节点个数为：25-5-4=16
第二问：树的深度为24（可确定为正则二叉树）
解题过程：由公式n0=n2+1 可得n0=24 可得该二叉树没有度为1的节点，满足正则二叉树的特点（正则二叉树的特点：没有度为1的节点）
可参考严蔚敏的《数据结构》 清华大学出版社
戚龚奇米：[答案] 第一题: n0=n2+1 n0=5 n2=4 n1=25-5-4=16 第二题: n2=23 n1=24 n1=0; 说明是满二叉树 log2(47+1)=log2(48) 向上取整就是 6
罗山县13570319819： 二叉树相关知识 - ？
戚龚奇米： 二叉树 (binary tree) 是另一种树型结构,它的特点是每个结点至多只有二棵子 树 (即二叉树中不存在度大于 2的结点 ),并且,二叉树的子树有左右之分,其次序不能任意颠倒 . 二叉树是一种数据结构 :Binary_tree=(D,R)其中: D是具有...
罗山县13570319819： 二叉树 问题 - ？
戚龚奇米： 二叉树中,度为2的节点数n2等于度为0的节点数(叶子节点)n0减1, 即n2=n0-1 是公式总节点数=n0+n1+n2n2=70-1=69总节点数=70+80+69
罗山县13570319819： 有关二叉树的简单问题...3.已知一棵度为k的树中有n1个度为1的结点,n2个度为2的结点,……nk个度为k的结点,问该树中有多少个叶子结点. - ？
戚龚奇米：[答案] 设该树中的叶子数为n0个.该树中的总结点数为n个,则有: n=n0+n1+n2+…+nK (1) n-1=0*n0+1*n1+2*n2+…+K*nK (2) 联立(1)(2)方程组可得: 叶子数为:n0=1+0*n1+1*n2+2*n3+...+(K-1)*nK 好好思考一下吧.
罗山县13570319819： 关于二叉树的问题“在任意一颗二叉树中,度为0的结点(及叶子结点)总是比度为2的结点多一个” - ？
戚龚奇米：[答案] 设一个二叉树中的节点总数为n,a为二叉树中度为1的节点数,b为度为2的节点数,c为度为0的节点数.二叉树所有节点的度小于等于2,所以总的节点数为n=a+b+c,这个知道吧?再看二叉树的分支数.除了根节点外,其余节点都有都有一个分支进入,...
罗山县13570319819： C语言,二叉树的问题 - ？
戚龚奇米： 1.219 二叉树的几点只有 0 1 2 三种度数2度节点 数等于0度节点(即叶子节点)减1n=n0+n1+n2=70+80+69=219 2.250 满二叉树下 节点数(n)与深度(m)的关系是 n=1+2+4+……+2^(m-1)=(2^m)-1因为完全二叉树 的节点数n 2^(m-1)-1<n<=2^m-1 所以 m=9 深度为9 满二叉树的叶子是 256 节点一共是511 完全二叉树节点少了11 256-11 =245 因为两个叶子 有一个父亲 11/2 =5 本来的父亲没了孩子 成为叶子 245+5=250
罗山县13570319819： 有关二叉树的简单问题... - ？
戚龚奇米： 设该树中的叶子数为n0个.该树中的总结点数为n个,则有:n=n0+n1+n2+…+nK (1)n-1=0*n0+1*n1+2*n2+…+K*nK (2)联立(1)(2)方程组可得:叶子数为:n0=1+0*n1+1*n2+2*n3+...+(K-1)*nK 好好思考一下吧.
罗山县13570319819： 一道关于二叉树的选择题 - ？
戚龚奇米： 记住二叉树一个最关键的特点:子树是分左右的(左子树,右子树):套进去,A不对,C也不对,D,并不是每个节点都有右子树,叶子节点没有子树
罗山县13570319819： 关于二叉树的问题由4个结点可以构造出多少种不同的二叉树,和完全二叉树?帮我看下这题,我记得是有公式的 - ？
戚龚奇米：[答案] 公式:B[n]=C[n,2n]*1/(n+1) 其中C〔n,2n〕 n为上,2n为下 将4代入得:B〔n〕=14
罗山县13570319819： 一些关于二叉树的问题？
戚龚奇米： 如果判断一棵树的形状,必须有两种遍历: 也就是说有了前序,中序,可以得到后序. 如果只知道一种遍历是不能得到剩下两种遍历的. 有两种遍历的情况下,推出树的形状,还是比较简单的.
