二叉树

二叉树(Binary Tree)：
特点：每个结点至多只有两棵子树。
二叉树的子树有左右之分，其次序不能任意颠倒。

完全二叉树：
定义：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中的编号1至n的结点一一对应。
特点：

二叉树的性质：
性质1：在二叉树的第i层上至多有2的i-1次方个结点。
性质2：深度为k的二叉树至多有2的k次方减1个结点。
性质3：对任何一棵二叉树T,如果其终端结点数为n0，度为2的节点数为n2，则n0=n2+1；
性质4：具有n个结点的完全二叉树的深度为log2n取下整加1。

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

typedef struct BinNode{
	char data;
	struct BinNode *lchild,*rchild;
}BinNode,*BinTree;

//'#'表示根节点
void createBinTree(BinTree &T){
	char ch;
	scanf("%c",&ch);
	if(ch == '#'){
		T = NULL;
	}else{
		if(!(T = (BinNode*) malloc(sizeof(BinNode)))){
			exit(0);
		}
		T->data = ch;
		printf("数据%c\n", T->data);
		createBinTree(T->lchild);
		createBinTree(T->rchild);
	}
}

/*递归实现二叉树的遍历方法*/
void preOrderTraverse(BinTree &T){
	if(T){
		printf("%c",T->data);
		preOrderTraverse(T->lchild);
		preOrderTraverse(T->rchild);
	}
}
void InOrderTravese(BinTree &T){
	if(T){
		InOrderTravese(T->lchild);
		printf("%c",T->data);
		InOrderTravese(T->rchild);
	}
}
void BackOrderTraverse(BinTree &T){
	if(T){
		BackOrderTraverse(T->lchild);
		BackOrderTraverse(T->rchild);
		printf("%c",T->data);
	}
}



int main(){
	BinTree T;
	createBinTree(T);
	preOrderTraverse(T);
	printf("\n");
	InOrderTravese(T);
	printf("\n");
	BackOrderTraverse(T);
	printf("\n");
	return 0;
}