一、二叉树

1、树

1）概念

树是 n(n >= 0) 个结点的有限集合。若 n=0 ，为空树。

在任意一个非空树中：

（1）有且仅有一个特定的根结点；

（2）当 n>1 时，其余结点可分为 m 个互不相交的有限集合T1、T2......Tm，其中每一个集合又是一个树，并且称为子树。

2）度、度数、深度

结点拥有子树的个数称为结点的度。度为 0 的结点称为叶结点；度不为 0 称为分支结点。

树的度数：指在这颗树中，最大的结点的度数，称为树的度数。

树的深度（高度）：指从根开始，根为第一层，根的孩子为第二层，即树的层数，称为树的深度。

树的存储：顺序结构、链表结构。

2、二叉树（binary tree）

1）概念

二叉树是 n 个结点的有限集合，集合要么为空树，要么由一个根节点和两棵互不相交的树组成，这两棵树分别称为根节点的左子树和右子树。

2）特点

（1）每个结点最多两个子树。

（2）左子树和右子树是有顺序的，次序不能颠倒。

（3）如果某个结点只有一个子树，也要区分左、右子树。

3）特殊的二叉树

（1）斜树

斜树分为两种，一种是所有的结点都只有左子树，称为左斜树；另一种是所有的结点都只有右子树，称为右斜树。

（2）满二叉树

满二叉树是指所有的分支结点都存在左右子树，并且叶子都在同一层上。

（3）完全二叉树

完全二叉树是指：对于一颗具有 n 个结点的二叉树按照层序编号，如果编号 i( 1<= i <= n )的结点于同样深度的满二叉树中编号为 i 的结点在二叉树中的位置完全相同，则此树称为完全二叉树。

4）特性

（1）在二叉树的第 i 层上最多有 2^(i-1) 个结点，i >= 1。

（2）深度为 k 的二叉树至多有 2^k-1 个结点，k >= 1。

（3）任意一个二叉树T，如果其叶子结点的个数为 N，度数为 M，则 N=M+1。

（4）有 n 个结点的完全二叉树深度为（logn / log2）+ 1。

5）层序

前序：根左右。先访问根结点，再访问左结点，最后访问右结点。

中序：左根右。先从根结点开始（不是先访问根结点），从左结点开始访问，再访问根结点，最后访问右结点。

后序：左右根。先从根结点开始（不是先访问根结点），从左结点开始访问，再访问右结点，最后访问根结点。

6）二叉树的函数应用

（1）创建二叉树函数

void CreateTree(BiTNode **root)
{char c = data[ind++];if('#' == c){*root = NULL;return ;}else{*root = malloc(sizeof(BiTNode));if(NULL == *root){printf("malloc error\n");*root = NULL;return ;}(*root) -> data = c;CreateTree(&(*root) -> ichild);CreateTree(&(*root) -> rchild);}return ;
}

（ 2）根左右（前序）函数封装

//根左右
void PreOrderTraverse(BiTNode *root)
{if(NULL == root){return ;}else{printf("%c", root -> data);PreOrderTraverse(root -> ichild);PreOrderTraverse(root -> rchild);}return ;
}

（ 3）左根右（中序）函数封装

//左根右
void InOrderTraverse(BiTNode *root)
{if(NULL == root){return ;}InOrderTraverse(root -> ichild);printf("%c", root -> data);InOrderTraverse(root -> rchild);return ;
}

（4）左右根（后序）函数封装

//左右根
void PostOrderTraverse(BiTNode *root)
{if(NULL == root){return ;}PostOrderTraverse(root -> ichild);PostOrderTraverse(root -> rchild);printf("%c", root -> data);return ;
}

（5）二叉树销毁函数封装

//销毁
void DestroyTree(BiTNode *root)
{if(NULL == root){return ;}DestroyTree(root -> ichild);DestroyTree(root -> rchild);free(root);return ;
}

（ 6）头文件与其余声明

#include <stdio.h>
#include <string.h>
#include <stdlib.h>typedef char DATATYPE;typedef struct BiTNode
{DATATYPE data;struct BiTNode *ichild, *rchild; 
}BiTNode;char data[] = "Abd#g###ce#h##fi###";
int ind = 0;

（ 7）主函数运行格式

int main(int argc, char **argv)
{BiTNode *root;CreateTree(&root);PreOrderTraverse(root);printf("\n");InOrderTraverse(root);printf("\n");PostOrderTraverse(root);printf("\n");DestroyTree(root);root = NULL;return 0;
}