二叉树

1， 二叉树的定义：每个结点的度不大于2 每个结点的孩子结点次序不能随意颠倒

2， 二叉树的性质：在二叉树的第i层上至多有2的i-1次方，深度为k的二叉树至多有2的k次方减1个结点，对任意一个二叉树T若终点数为n0,其度为2的结点数n2，则n0=n2+1;

3， 满二叉树：深度为K且有2的K次方减1个结点的二叉树。在满二叉树中每个结点都是满的，每层结点都有最大的结点数。

4， 完全二叉树中；深度为K结点数为n的二叉树【满二叉树一定完全二叉树，而完全二叉树不一定是满二叉树

具有N个结点的完全二叉树深度为log以2为底N的对数向下取整加一。 对于N个结点完全二叉树，按照从上到下，从左到右的顺序 （1） i=1则序号i为根结点，i>1,则序号为i的结点的双亲序号为i/2向下取整。

（2） 2i>n则序号为i的结点无左孩子，2i<=n序号为i的结点的左孩子的结点序号为2*i

（3） 2i+1>n则序号为i的结点无右孩子，2i+1<=n,序号为i的结点的右孩子的结点的序号为2*i+1;

5, 二叉树的存储结构，结构是非线性的，每个结点有最多两个后继。顺序存储结构和链式结构

一维数组作为存储结构，将二叉树中的编号为i的结点放在数组的第i个位置则i的左孩子位置为2i，右孩子的位置为2i+1;

代码实现

  #include<stdio.h>
 #include<stdlib.h>

 typedef struct Tree{

 int data;					//	存放数据域
 struct Tree *lchild;			//	遍历左子树指针
 struct Tree *rchild;			//	遍历右子树指针

}Tree,*BitTree;

BitTree CreateLink()
{
int data;
int temp;
BitTree T;

scanf("%d",&data);		//	输入数据
temp=getchar();			//	吸收空格

if(data == -1){			//	输入-1 代表此节点下子树不存数据，也就是不继续递归创建
	
	return NULL;

}else{
	T = (BitTree)malloc(sizeof(Tree));			//		分配内存空间
	T->data = data;								//		把当前输入的数据存入当前节点指针的数据域中
	
	printf("请输入%d的左子树: ",data);		
	T->lchild = CreateLink();					//		开始递归创建左子树
	printf("请输入%d的右子树: ",data);			
	T->rchild = CreateLink();					//		开始到上一级节点的右边递归创建左右子树
	return T;							//		返回根节点
}	

}
 //	先序遍历
   void ShowXianXu(BitTree T)			//		先序遍历二叉树
   {
if(T==NULL)						//	递归中遇到NULL，返回上一层节点
{
	return;
}
printf("%d ",T->data);
ShowXianXu(T->lchild);			//	递归遍历左子树
ShowXianXu(T->rchild);			//	递归遍历右子树
    }
 //	中序遍历
void ShowZhongXu(BitTree T)			//		先序遍历二叉树
  {
if(T==NULL)						//	递归中遇到NULL，返回上一层节点
{
	return;
}

ShowZhongXu(T->lchild);			//	递归遍历左子树
printf("%d ",T->data);
ShowZhongXu(T->rchild);			//	递归遍历右子树

 }
//	后序遍历
void ShowHouXu(BitTree T)			//		后序遍历二叉树
  {
if(T==NULL)						//	递归中遇到NULL，返回上一层节点
{
	return;
}

ShowHouXu(T->lchild);			//	递归遍历左子树
ShowHouXu(T->rchild);			//	递归遍历右子树
printf("%d ",T->data);
}


  int main()
 {
BitTree S;
printf("请输入第一个节点的数据:\n");
S = CreateLink();			//		接受创建二叉树完成的根节点
printf("先序遍历结果: \n");
ShowXianXu(S);				//		先序遍历二叉树

printf("\n中序遍历结果: \n");
ShowZhongXu(S);				//		中序遍历二叉树

printf("\n后序遍历结果: \n");
ShowHouXu(S);				//		后序遍历二叉树

return 0;	
}