本文主要内容：二叉树
树：（1：N）层次结构。只能有一个根结点
二叉树主要有满二叉树（一个都不能少）和完全二叉树，
二叉树是n(n=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。
特点：
每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
左子树和右子树是有顺序的，次序不能任意颠倒。
即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
其中在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
特点：
叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
非叶子结点的度一定是2。
在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多
对一颗具有n个结点的二叉树按层编号，如果编号为i(1=i=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
特点：
叶子结点只能出现在最下层和次下层。
最下层的叶子结点集中在树的左部。
倒数第二层若存在叶子结点，一定在右部连续位置。
如果结点度为1，则该结点只有左孩子，即没有右子树。
同样结点数目的二叉树，完全二叉树深度最小。
满二叉树一定是完全二叉树，但反过来不一定成立。
定义结构体：
typedefstructnode{intdata;structnode*left;//保存左孩子的地址structnode*right;//保存右孩子的地址}tree_t;
创建（采用递归：根-左-右）：
tree_t*create_tree(intdata,intmax){if(datamax)returnNULL;//申请空间tree_t*tree=malloc(sizeof(tree_t));//初始化tree-data=data;//初始化左孩子，右孩子的地址tree-left=create_tree(2*data,max);tree-right=create_tree(2*data+1,max);returntree;}
先序打印（采用递归：根-左-右）：
voidprintf_pre(tree_t*tree){if(tree==NULL)return;//遍历自己printf("%3d",tree-data);//遍历左孩子printf_pre(tree-left);//遍历右孩子printf_pre(tree-right);return;}
中序打印（采用递归：左-根-右）：
voidprintf_mid(tree_t*tree){if(tree==NULL)return;//遍历左孩子printf_mid(tree-left);//遍历自己printf("%3d",tree-data);//遍历右孩子printf_mid(tree-right);return;}
后序打印（采用递归：左-右-根）：
voidprintf_post(tree_t*tree){if(tree==NULL)return;//遍历左孩子printf_post(tree-left);//遍历右孩子printf_post(tree-right);//遍历自己printf("%3d",tree-data);return;}
层次打印（顺序队列实现）：
voidprint_level(tree_t*tree){if(tree==NULL)return;//创建顺序队列tree_t**queue=malloc(sizeof(tree_t*)*30);//二级指针//int*stack=malloc(sizeof(int)*size);inthead=0;//存放即将取数据的位置inttail=0;//存放即将存数据的位置//入队根结点（尾入）queue[0]=tree;tail++;//判断队列不为空，出队数据并打印出队数据while(head!=tail){//判断有没有左孩子，有入队if(queue[head]-left!=NULL)queue[tail++]=queue[head]-left;//判断有没有右孩子，有入队if(queue[head]-right!=NULL)queue[tail++]=queue[head]-right;//出队打印头结点printf("%3d",queue[head++]-data);}printf("\n");free(queue);return0;}//上方不理解可参考下方方法//intprint_level(tree_t*tree){//创建顺序队列tree_t*queue[30];//指针数组inthead=0;//存放即将取数据的位置inttail=0;//存放即将存数据的位置//创建临时变量存放结点tree_t*temp;//入队根结点（尾入）queue[0]=tree;tail++;//判断队列不为空，出队数据并打印出队数据while(head!=tail){//出队队头结点，临时变量需要先指向头才能进行temp操作，使用二级指针则不需要temp=queue[head++];//打印出队结点中的数据printf("%3d",temp-data);//判断有没有左孩子，有入队if(temp-left!=NULL){queue[tail++]=temp-left;}//判断有没有右孩子，有入队if(temp-right!=NULL){queue[tail++]=temp-right;}}printf("\n");return0;}
main函数：
#includestdio.h#includestdlib.htypedefstructnode{intdata;structnode*left;structnode*right;}tree_t;intmain(intargc,constchar*argv[]){tree_t*tree=create_tree(1,7);printf("printf_pre:");printf_pre(tree);printf("\n");printf("printf_mid:");printf_mid(tree);printf("\n");printf("printf_post:");printf_post(tree);printf("\n");print_level(tree);return0;}
参考资料：（