二叉树问题证明？谢谢高手指教！
可怜的娃，我们都用遍历顺序自动生成树。
#include
#include
#define MAX 50
#define MAS 20
#define CHAR 1
#if CHAR
typedef char TElemType;
TElemType Nil=' ';
#define form "%c"
#else
typedef int TElemType;
TElemType Nil=0;
#define form "%d"
#endif
typedef struct node
{TElemType data;
struct node *left;
struct node *right;
struct node *parent;
}BiTNode,*BiTree;
BiTNode *InitBiTree(BiTNode *bt)
{
bt=NULL;
return bt;
}
BiTNode *CreateBiTree(BiTNode *bt)
{TElemType ch;
scanf(form,&ch);
if(ch==Nil) bt=NULL;
else
{bt=(BiTNode *)malloc(sizeof(BiTNode));
if(!bt) exit(0);
bt->data=ch; bt->parent=NULL;
bt->left=CreateBiTree(bt->left);
if(bt->left) bt->left->parent=bt;
bt->right=CreateBiTree(bt->right);
if(bt->right) bt->right->parent=bt;
}
return bt;
}
void PrintTree(BiTNode *bt,int i)
{ if(bt!=NULL)
{PrintTree(bt->right,i+5);
#if CHAR
if(bt->data!=Nil)
printf("%*c
",i,bt->data);
#else
if(bt->data!=Nil)
printf("%*d
",i,bt->data);
#endif
PrintTree(bt->left,i+5);
i=i-5;
}
}
void Prorder1(BiTNode *bt,void(*visit)(TElemType))/*先序遍历*/
{if(bt!=NULL)
{visit(bt->data);
Prorder1(bt->left,visit);
Prorder1(bt->right,visit);
}
}
void Prorder2(BiTNode *bt,void(*visit)(TElemType))/*中序遍历*/
{BiTNode *p,*stack[MAS];
int top;
top=0; p=bt;
while(top!=0||p!=NULL)
{while(p!=NULL)
{stack[top]=p; top++;
p=p->left;
}
if(top!=0)
{p=stack[top-1];
top--;
visit(p->data);
p=p->right;
}
}
}
void Prorder3(BiTNode *bt,void(*visit)(TElemType))/*后序遍历*/
{BiTNode *p,*stack[MAS];
int top;
top=0;
stack[top]=bt; top++;
while(top>0)
{p=stack[top-1]; top--;
while(p!=NULL)
{visit(p->data);
stack[top]=p->right;
top++;
p=p->left;
}
}
}
void visit(TElemType e)
{printf(form" ",e);
}
int SumLefts(BiTNode *bt,int sum)
{
if (bt!=NULL)
{
if (bt->left==NULL && bt->right==NULL)
{
printf("%4c",bt->data); sum++;
}
sum=SumLefts(bt->left,sum);
sum=SumLefts(bt->right,sum);
}
return(sum);
}
int SumTree(BiTNode *bt)
{static int sum=0;
if(bt!=NULL)
{printf("%4c",bt->data);
sum++;
sum=SumTree(bt->left);
sum=SumTree(bt->right);
}
return(sum);
}
BiTNode *Findchar(BiTNode *bt,char ch) /*二叉树查找结点*/
{BiTNode *p; /*利用函数名返回结果*/
if(bt!=NULL)
{if(bt->data==ch) p=bt;
p=Findchar(bt->left,ch);
p=Findchar(bt->right,ch);
}
if(p!=NULL) return(p);
else return(NULL);
}
main()
{ int j,i,a,sum=0;
BiTree bt;
bt=InitBiTree(bt);
#if CHAR
printf("请先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树)
");
#else
printf("请先序输入二叉树(如:1 2 0 0 0表示1为根结点,2为左子树的二叉树)
");
#endif
bt=CreateBiTree(bt);
printf("输入建立的二叉树!!!
");
PrintTree(bt,5);
do{
printf("------------------------------------------------------------");
printf("
主菜单");
printf("
1 二叉树先序遍历");
printf("
2 二叉树中序遍历");
printf("
3 二叉树后序遍历");
printf("
4 二叉树叶子结点数");
printf("
5 二叉树结点数");
printf("
6 二叉树查找x结点");
printf("
0 退出");
printf("
----------------------------------------------------------");
printf("
");
printf("输入你要选择的数据:");
scanf("%d",&i);
switch(i)
{case 1: printf("先序遍历结果为:");
Prorder1(bt,visit);
break;
case 2: printf("后序遍历结果为:");
Prorder2(bt,visit);
break;
case 3: printf("中序遍历结果为:");
Prorder3(bt,visit);
break;
case 4: j=SumLefts(bt,sum);
printf("树的叶子结点数为%d:",j);
break;
case 5: j=SumTree(bt);
printf("树的结点数为%d:",j);
break;
case 6: printf("输入要查找的结点字符x:");
scanf("%c",&a); scanf("%*c");
j=Findchar(bt,a);
printf("要查找的结点的指针为%d:",j);
break;
case 0: exit(0);
}
printf("
");
getch();
}while(i>0||i<8);
}
希望对你有帮助
将后序序列依次入栈：pn最先入栈，接着用p（n-1）压栈如此直至p1入栈。按照岀栈规则：先入后出，后入先出。p1先出栈，接下来是p2。判断p2是否为父节点，不是就将下一个结点岀栈。再判断是否为父节点，是就将之前结点重新入栈。这样我们就得到了一个孩子结点和父节点接下来再判断此时栈中最顶端的结点是否为孩子结点，如果不是就继续前面的判断循环。如此循环直至栈为空。
以上仅为理论参考，实际编程时要进一步考虑孩子结点是左结点还是右结点。希望对楼主能有所帮助。
后序遍历时利用栈来实现，即依次将根节点，右孩子，左孩子入栈；然后再依次出栈即得到序列
1,2，。。。，n ；中序遍历又可以用后序遍历的结果来实现，即先弹出栈顶，在弹出下个元素i，如果元素i的左孩子不为栈顶进入另一个栈T，则接着弹下个元素，再继续判断，知道弹出元素为栈顶时输出，再对T进行操作，和第一个栈的操作一致。
试证明一棵完全二叉树必有奇数个结点.
答：【答案】：分析 本题可根据完全二叉树的特点、树、图中边、结点的关系，经综合考虑得出结论．证明 方法一：设完全二叉树T有n个结点，m条边．依定义，T中每个分枝点都关联两条边，所以m必为偶数．又因为T是树，有n=m+1，故n为奇数．因此，完全二叉树必有奇数个结点．方法二：设完全二叉树T有n...
给定完全二叉树G=(V,E),试证明:|E|=2(n-1),其中n是树叶结点数目._百度...
答：【答案】：证明 G的结点数为|V|，边数为|E|，i个分枝结点，n个叶结点，根据定理有i=n-1．又|V|=i+n=2n-1，由于G是树，所以又有：|E|=|V|-1=2n-1-1=2(n-1)．本题所用定理是对于完全m叉树，其树叶数为n，分枝点数为i，则有 (m-1)i=m-1．由于本题是完全二叉树，m=2，...
二叉树问题证明?谢谢高手指教!
答：思路是：后序遍历原则是：左右父；中序遍历原则是左父右。所以我们将后序遍历序列入栈后再按中序遍历原则从栈中得到结点。将后序序列依次入栈：pn最先入栈，接着用p（n-1）压栈如此直至p1入栈。按照岀栈规则：先入后出，后入先出。p1先出栈，接下来是p2。判断p2是否为父节点，不是就将下一...
证明:在完全二叉树中,边的总数等于2(nt-1),式中nt是树叶数.
答：【答案】：分支点数i=nt-1，结点数v=i+nt=2nt-1，v=e+1，所以边数e=v-1=2(nt-1)．
证明具有n个结点的二叉树,其深度至少为[log2n]+1,求详细证明?
答：证明：设所求完全二叉树的深度为k,根据完全二叉树的定义和性质2可知，k-1层满二叉树的结点个数为n时，有 2k－1－1<n≤2k-1；即 2k－1≤n<2k；对不等式取对数，有 k－1≤log2n<k；由于k是整数，所以具有n个结点的二叉树,其深度至少为[log2n]+1。
如何证明二叉树有无穷个分支?
答：证明：假设度为1的结点个数为n1，结点总数为n，B为二叉树中的分支数。因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为：n=n0+n1+n2 （1）再查看一下分支数。在二叉树中，除根结点之外，每个结点都有一个从上向下的分支指向，所以，总的结点个数n与分支数B之间的关系为：n=B+1。...
证明有n个结点的完全二叉树,叶结点个数为(n+1) 2.
答：【答案】：证明 设叶结点数目为x．分枝结点数目为n1，则有n=n1+x，另一方面从边计算，有，n-1=2·n1，所以n1=x-1，n=n1+x=(x-1)+x=2·x-1，x=(n+1)/2．
计算机二级关于二叉树的问题。懂的进,急求解答。
答：由二叉树的性质可知：n0=n2+1，则n= n0+n1+n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=（n+1）/2或n0=n/2，就可根据完全二叉树的结点总数计算出叶子结点数。 所以叶子结点数相同 ...
证明二叉树的第i层上至多有2的i-1次方个结点
答：第1层1个，为2^(1-1)二叉树每个结点至多2个孩子，因此 第二层最多2 *1 = 2^(2-1)第三层最多2*2= 2^(3-1)...第i层上至多有2的i-1次方个结点
证明具有n个结点的二叉树,其深度至少为[log2n]+1,求详细证明?
答：故n<=2^(k+1)-1时命题成立。证毕。（首先最好能先从直观上理解：完全二叉树中：第1层有1个结点；第2层有2个结点；第3层有4个结点；……第k层有2^(k-1)个结点；（前k层共有(2^k)-1个结点，故前面深度刚好是「log2（2^k-1)」+1=k-1+1=k）第k+1层是剩余的结点。）...
