erchashu.txt

是一份比较全面的有关于

二叉树具有以下重要性质： 
性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。 
证明：用数学归纳法证明： 
归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根结点，所以命题成立。 
归纳假设：假设对所有的j(1≤j<i)命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。 
归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2×2i-2=2i-1个结点，故命题成立。 

性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。 
证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为： 
20+21+…+2k-1=2k-1 
故命题正确。 

性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。 
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和： 
n=no+n1+n2 (式子1) 
另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是： 
nl+2n2 
树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为： 
n=n1+2n2+1 (式子2) 
由式子1和式子2得到： 
no=n2+1 

满二叉树和完全二叉树是二叉树的两种特殊情形。 
1、满二叉树(FullBinaryTree) 
一棵深度为k且有2k-1个结点的二又树称为满二叉树。 
满二叉树的特点： 
（1） 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。 
（2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。 
【例】图(a)是一个深度为4的满二叉树。 



2、完全二叉树(Complete BinaryTree) 
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。 
特点： 
（1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。 
（2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。 
（3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。 
【例】如图(c)中，结点F没有左孩子而有右孩子L，故它不是一棵完全二叉树。 
【例】图(b)是一棵完全二叉树。 

性质4 具有n个结点的完全二叉树的深度为 

证明：设所求完全二叉树的深度为k。由完全二叉树定义可得： 
深度为k得完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。 
由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数： 
n>2k-1-1。 
另一方面，由性质2可得： 
n≤2k-1， 
即：2k-1-l<n≤2k-1 
由此可推出：2k-1≤n<2k，取对数后有： 
k-1≤lgn<k 
又因k-1和k是相邻的两个整数，故有 
, 
由此即得： 

注意： 
的证明【参见参考书目】 
回答者：杰清 - 经理 五级 1-16 09:35 
前序遍历 
void preorder(btree *p) 
{ 
if(p!=NULL) 
{ printf("%d",p->data); 
preorder(p->left); 
preorder(p->right); 
} 
} 

中序遍历 
void inorder(btree *p) 
{ 
if(p!=NULL) 
{ inorder(p->left); 
printf("%d",p->data); 
inorder(p->right); 
} 
} 
后序遍历 
void postorder(btree *p) 
{ 
if(p!=NULL) 
{ postorder(p->left); 
postorder(p->right); 
printf("%d",p->data); 
} 
} 


#include <stdio.h> 
#include <iostream> 
#include <queue> 
#include <stack> 
#include <malloc.h> 
#define SIZE 100 

using namespace std; 

typedef struct BiTNode //定义二叉树节点结构 
{ 
char data; //数据域 
struct BiTNode *lchild,*rchild; //左右孩子指针域 
}BiTNode,*BiTree; 

int visit(BiTree t); 
void CreateBiTree(BiTree &T); //生成一个二叉树 
void PreOrder(BiTree); //递归先序遍历二叉树 
void InOrder(BiTree); //递归中序遍历二叉树 
void PostOrder(BiTree); //递归后序遍历二叉树 
void InOrderTraverse(BiTree T); //非递归中序遍历二叉树 
void PreOrder_Nonrecursive(BiTree T);//非递归先序遍历二叉树 
void LeverTraverse(BiTree T);//非递归层序遍历二叉树 


//主函数 
void main() 
{ 
BiTree T; 
char j; 
int flag=1; 
//---------------------程序解说----------------------- 
printf("本程序实现二叉树的操作。\n"); 
printf("叶子结点以空格表示。\n"); 
printf("可以进行建立二叉树，递归先序、中序、后序遍历，非递归先序、中序遍历及非递归层序遍历等操作。\n"); 
//---------------------------------------------------- 
printf("\n"); 
printf("请建立二叉树。\n"); 
printf("建树将以三个空格后回车结束。\n"); 
printf("例如:1 2 3 4 5 6 (回车)\n"); CreateBiTree(T); //初始化队列 
getchar(); 
while(flag) 
{ 
printf("\n"); 
printf("请选择: \n"); 
printf("1.递归先序遍历\n"); 
printf("2.递归中序遍历\n"); 
printf("3.递归后序遍历\n"); 
printf("4.非递归中序遍历\n"); 
printf("5.非递归先序遍历\n"); 
printf("6.非递归层序遍历\n"); 
printf("0.退出程序\n"); 
scanf(" %c",&j); 
switch(j) 
{ 
case '1':if(T) 
{ 
printf("递归先序遍历二叉树:"); 
PreOrder(T); 
printf("\n"); 
} 
else printf("二叉树为空!\n"); 
break; 
case '2':if(T) 
{ 
printf("递归中序遍历二叉树:"); 
InOrder(T); 
printf("\n"); 
} 
else printf("二叉树为空!\n"); 
break; 
case '3':if(T) 
{ 
printf("递归后序遍历二叉树:"); 
PostOrder(T); 
printf("\n"); 
} 
else printf("二叉树为空!\n"); 
break; 
case '4':if(T) 
{ 
printf("非递归中序遍历二叉树:"); 
InOrderTraverse(T); 
printf("\n"); 
} 
else printf("二叉树为空!\n"); 
break; 
case '5':if(T) 
{ 
printf("非递归先序遍历二叉树:"); 
PreOrder_Nonrecursive(T); 
printf("\n"); 
} 
else printf("二叉树为空!\n"); 
break; 
case '6':if(T) 
{ 
printf("非递归层序遍历二叉树:"); 
LeverTraverse(T); 
printf("\n"); 
} 
else printf("二叉树为空!\n"); 
break; 
default:flag=0;printf("程序运行结束，按任意键退出!\n"); 
} 
} 

} 

//建立二叉树 
void CreateBiTree(BiTree &T) 
{ 
char ch; 
scanf("%c",&ch); //读入一个字符 
if(ch==' ') T=NULL; 
else 
{ 
T=(BiTNode *)malloc(sizeof(BiTNode)); //生成一个新结点 
T->data=ch; 
CreateBiTree(T->lchild); //生成左子树 
CreateBiTree(T->rchild); //生成右子树 
} 
} 

//先序遍历的递归 
void PreOrder(BiTree T) 
{ 
if(T) 
{ 
printf("%c ",T->data); //访问结点 
PreOrder(T->lchild); //遍历左子树 
PreOrder(T->rchild); //遍历右子树 
} 
} 

//中序遍历的递归 
void InOrder(BiTree T) 
{ 
if(T) 
{ 
InOrder(T->lchild); //遍历左子树 
printf("%c ",T->data); //访问结点 
InOrder(T->rchild); //遍历右子树 
} 
} 

//后序遍历的递归 
void PostOrder(BiTree T) 
{ 
if(T) 
{ 
PostOrder(T->lchild); //遍历左子树 
PostOrder(T->rchild); //访问结点 
printf("%c ",T->data); //遍历右子树 
} 
} 

//非递归中序遍历 
void InOrderTraverse(BiTree T) 
{ 
stack<BiTree> S; 
BiTree p; 
S.push(T);//跟指针进栈 
while(!S.empty()) 
{ 
p=new BiTNode; 
while((p=S.top())&&p) 
S.push(p->lchild);//向左走到尽头 
S.pop(); //空指针退栈 
if(!S.empty()) 
{ 
p=S.top(); 
S.pop(); 
cout<<p->data<<" "; 
S.push(p->rchild); 
} 
} 

} 

//先序遍历的非递归 
void PreOrder_Nonrecursive(BiTree T) 
{ 
stack<BiTree> S; 
BiTree p; 

S.push(T);//根指针进栈 
while(!S.empty())//栈空时结束 
{ 
while((p=S.top())&&p) 
{ 
cout<<p->data<<" "; 
S.push(p->lchild); 
}//向左走到尽头 
S.pop();//弹出堆栈 
if(!S.empty()) 
{ 
p=S.top(); 
S.pop(); 
S.push(p->rchild);//向右走一步 
} 
} 
} 


void LeverTraverse(BiTree T) 
{//非递归层次遍历 
queue <BiTree> Q; 
BiTree p; 
p = T; 
if(visit(p)==1) 
Q.push(p); 
while(!Q.empty()) 
{ 
p = Q.front(); 
Q.pop(); 
if(visit(p->lchild) == 1) 
Q.push(p->lchild); 
if(visit(p->rchild) == 1) 
Q.push(p->rchild); 
} 
} 

int visit(BiTree T) 
{ 
if(T) 
{ 
printf("%c ",T->data); 
return 1; 
} 
else 
return 0; 
}