二叉树，顾名思义，是有每个结点有两个分支的树，我们将结点称为根节点，将它的两个分支称为它的左子树、右子树，所以我们用以下结构来定义二叉树的结构。
typedef char TreeNodeType;
typedef struct TreeNode//树的结点
{
TreeNodeType data;//数据
struct TreeNode* lchild;//左子树
struct TreeNode* rchild;//右子树
}TreeNode;
树的基本实现：
void TreeInit(TreeNode** proot)//初始化
{
if(proot == NULL)//非法输入
return;
*proot = NULL;
return;
}
TreeNode* CreateTreeNode(TreeNodeType value)//创造一个新结点
{
TreeNode* new_node = (TreeNode*)malloc(sizeof(TreeNode));
new_node->data = value;
new_node->lchild = NULL;
new_node->rchild = NULL;
return new_node;
}
void DestroyTreeNode(TreeNode* node)//销毁结点
{
free(node);
return;
}
对于二叉树，最最基本的操作就是对二叉树进行遍历。而二叉树的遍历方式我们有先序遍历、中序遍历、后序遍历、层次遍历这几种，且遍历二叉树最重要的就是做到“
不重不漏”。
1. 先序遍历（先访问根节点，再访问左子树，最后访问右子树）
如图，即我们对图中二叉树进行了一个先序遍历。
（1）我们对整棵树的根节点进行访问，也就是图中的1即结点A；
（2）然后访问整棵树的左子树即2，对于2子树，我们再访问它的根节点也就是B，再访问它的左子树也就是3；
（3）我们可以看到3子树，只有根结点而无子树，所以我们访问了根结点D就可以返回到2树；
（4）返回到2树之后，按先序遍历的顺序接下来该访问2的右子树即4树；
（5）访问4树的根节点E，再访问它的左子树，因为它的左子树只有根结点G，所以我们访问完G就可以返回，而4树也无右子树，所以我们继续返回；
（6）上步最后我们应该返回到1树，去访问它的右子树5，对于5树先访问它的根节点C；
（7）访问完C后，应该访问C的左子树，但它左子树为空，所以我们直接访问右子树F；
（8）至此，该树已遍历完，所以先序遍历的结果是：A B D E G C F
整个过程，利用代码我们可以用递归实现，实现代码如下：
void TreePreOrder(TreeNode* root)//先序遍历
{//根左右
//树为空也是遍历结束的条件
if(root == NULL)//空树
{
printf("[%c] ",'#');
return;
}
//访问根结点
printf("[%c] ",root->data);
//递归访问左子树
TreePreOrder(root->lchild);
//递归访问右子树
TreePreOrder(root->rchild);
return;
}
2. 中序遍历（先访问左子树，再访问根节点，最后访问右子树）
中序遍历的思想与先序遍历一样，只是访问顺序改变了。针对上图的二叉树，我们进行中序访问：
（1）首先访问1树的左子树2，对2树再访问左子树即3，3树无子树，所以访问根节点D，再返回到2树；
（2）此时，2树已访问完左子树，接下来访问根节点B，再到右子树4树；
（3）对4树，先访问它的左子树，左子树仅一个单节点，所以直接访问G，再返回访问E，4树无右子树，所以返回到2树，2树也访问完了，再继续返回到1树；
（4）1树该访问根节点即A，再访问1树的右子树即5树；
（5）对5树再按中序遍历访问，即C再F；
（6）至此，中序遍历访问结束，结果是：D B G E A C F
利用递归实现，实现代码如下：
void TreeInOrder(TreeNode* root)//中序遍历
{//左根右
//树为空也是遍历结束的条件
if(root == NULL)//空树
return;
//递归访问左子树
TreeInOrder(root->lchild);
//访问根结点
printf("[%c] ",root->data);
//递归访问右子树
TreeInOrder(root->rchild);
return;
}
3
. 后序遍历（先访问左子树，再访问右子树，最后访问根节点）
（1）首先访问1的左子树2树，再访问2的左子树3，所以访问结点D，再返回到2树访问2的右子树4树；
（2）对4树，先访问左子树G，再访问右子树，因为右子树为空，所以访问根节点E，再返回到2树；
（3）此时该访问2树的根节点B，再返回到1树；
（4）此时该访问1树的右子树5树，对于5树先访问左子树为空，再访问右子树为F，最后访问根节点C，再返回1树；
（5）最后访问1树的根节点即A；
（6）至此，遍历结束结果为：D G E B F C A
利用递归实现代码如下：
void TreePostOrder(TreeNode* root)//后序遍历
{//左右根
//树为空也是遍历结束的条件
if(root == NULL)//空树
return;
//递归访问左子树
TreePostOrder(root->lchild);
//递归访问右子树
TreePostOrder(root->rchild);
//访问根结点
printf("[%c] ",root->data);
return;
}
4.层序遍历（从第一层，一层一层向下访问）
层序遍历很简单，大家应该都能很快地遍历出来：A B C D E F G
代码实现的思想：
（1）我们可以利用队列实现，首先将二叉树的根节点放入队列即入A；
（2）拿队首元素为当前元素并访问，访问完出队，同时将当前元素的左右子树即B、C入队（子树为空则不入队）；
（3）重复（2）步骤，即访问B再入D、E；访问C再入F；
（4）直至队列为空，遍历结束
实现代码：
void TreeLevelOrder(TreeNode* root)//层序遍历
{//1.建一个队列，若根结点非空，先将根结点入队
//2.打印当前队列的首元素结点的data值，并将其出队
//3.若刚刚出队元素的左/右子树不为空，就将其入列，再重复23步骤，直至队列为空即遍历结束
//树空也作为遍历结束的条件
if(root == NULL)//空树
return;
SeqQueue queue;
SeqQueueInit(&queue);
SeqQueuePush(&queue,root);
while(1)
{
SeqQueueType front;
int ret = SeqQueueGetFront(&queue,&front);
//队首元素为空说明遍历结束
if(ret == 0)
break;
//访问当前元素结点，并打印其值
printf("[%c] ",front->data);
//将当前结点出队
SeqQueuePop(&queue);
//将当前结点的左右子树（若非空）则入队
if(front->lchild != NULL)
SeqQueuePush(&queue,front->lchild);
if(front->rchild != NULL)
SeqQueuePush(&queue,front->rchild);
}
printf("\n");
return;
}
其中，以上用到的队列相关代码如下：（具体队列相关操作的实现，大家都可以在这里找到
点击打开链接，这里的代码只是稍作了修改而已）
typedef TreeNode* SeqQueueType;
typedef struct SeqQueue//整个队列的元素是从head到tail，
{ //由于出队是头删，所以前面可能会有空，所以当tail走到最后时，tail再指向0，只要size与MAX_SIZE不相等，就还有空间
SeqQueueType data[MAX_SIZE];
size_t head;//队列第一个元素下标
size_t tail;//队列最后一个元素的下标
size_t size;//用了多少个元素的空间
}SeqQueue;
因为这里，要向队列里存放的是子树结点的指针，所以这里稍微修改了，下面的基本操作代码还是没有什么变化的。
void SeqQueueInit(SeqQueue* q)//初始化
{
if(q == NULL)//非法操作
return;
q->size = 0;
q->head = 0;
q->tail = 0;
return;
}
void SeqQueueDestroy(SeqQueue* q)//销毁队列
{
if(q == NULL)
return;
q->size = 0;
q->head = 0;
q->tail = 0;
return;
}
void SeqQueuePush(SeqQueue* q,SeqQueueType value)//入队列(尾插)
{
if(q == NULL)
return;
if(q->size >= MAX_SIZE)//队列已满
return;
q->data[q->tail++] = value;
if(q->tail >= MAX_SIZE)//tail走到最后，就再指向头(只要size<MAX_SIZE)
q->tail = 0;
q->size++;
return;
}
void SeqQueuePop(SeqQueue* q)//出列队(头删)
{
if(q == NULL)//非法操作
return;
if(q->size == 0)//空队
return;
q->head++;
if(q->head >= MAX_SIZE)//别忘记！！！
q->head = 0;
q->size--;
return;
}
int SeqQueueGetFront(SeqQueue* q,SeqQueueType* value)//取队首元素
{
if(q == NULL)
return 0;
if(q->size == 0)
return 0;
*value = q->data[q->head];
return 1;
}
void SeqQueuePrint(SeqQueue* q,const char* msg)//打印
{
printf("[%s]\n",msg);
if(q == NULL)
return;
if(q->size == 0)//空队列
{
printf("空队\n");
return;
}
size_t i = q->head;
if(q->tail <= q->head)//tail在head前
{
for(; i<MAX_SIZE; ++i)
printf("[%c] ",q->data[i]);
for(i=0; i<q->tail; ++i)//q->tail指向最后一个元素的下一个位置
printf("[%c] ",q->data[i]);
}
else//tail在head后
{
for(i=q->head; i<q->tail; ++i)
printf("[%c] ",q->data[i]);
}
printf("\n");
return;
}
5.根据数组所给内容（包括空子树），构建一颗二叉树
TreeNode* _TreeCreate(TreeNodeType data[],size_t size,size_t* index,TreeNodeType null_node)//真正实现构建二叉树的代码
{
if(index == NULL)//非法输入
return NULL;
if(*index >= size)//访问数组越界
return NULL;
if(data[*index] == null_node)//当前是空子树
return NULL;
TreeNode* new_node = CreateTreeNode(data[*index]);//2.
++(*index);//3.
new_node->lchild = _TreeCreate(data,size,index,null_node);
++(*index);//4.
new_node->rchild = _TreeCreate(data,size,index,null_node);
return new_node;//返回当前子树的根结点
}
TreeNode* TreeCreate(TreeNodeType data[],size_t size,TreeNodeType null_node)//根据数组所给内容构建一颗二叉树
{//数组所给内容（这里给的是先序遍历结果）包括空子树，即参数null_node所代表的，第二个参数size表示树的大小
//1.index用来标记当前元素为数组的哪个元素的下标
//2.根据index所指内容创建一个结点
//3.先++index，然后递归构建新结点的左子树
//4.再++index,然后构建新结点的右子树
size_t index = 0;
return _TreeCreate(data,size,&index,null_node);
}
6.树的深拷贝
拷贝分为深拷贝、浅拷贝两种。浅拷贝是新建一个指针，将所要拷贝内容的空间的地址拿到放入指针；而深拷贝则是创建一块新内存，将想要的内容全部拷贝一份。
TreeNode* TreeClone(TreeNode* root)//树的深拷贝
{
if(root == NULL)//空树
return NULL;
//按先序来拷贝
TreeNode* new_node = CreateTreeNode(root->data);
new_node->lchild = TreeClone(root->lchild);
new_node->rchild = TreeClone(root->rchild);
return new_node;
}
7. 树的销毁
法一：
void TreeDestroy1(TreeNode** root)//树的销毁1
{//基于后序来遍历销毁，防止根结点销毁之后找不到子树，造成没有全部销毁
if(root == NULL)//非法输入
return;
if(*root == NULL)//空树
return;
TreeDestroy1(&((*root)->lchild));
TreeDestroy1(&((*root)->rchild));
DestroyTreeNode(*root);
*root = NULL;
return;
}
法二：
void TreeDestroy2(TreeNode** root)//树的销毁2
{//基于先序来遍历销毁，在销毁当前子树的根结点时，先保存左右子树，避免找不到而没删除
if(root == NULL)//非法输入
return;
if(*root == NULL)//空树
return;
TreeNode* lchild = (*root)->lchild;
TreeNode* rchild = (*root)->rchild;
DestroyTreeNode(*root);
TreeDestroy2(&lchild);
TreeDestroy2(&rchild);
*root = NULL;
return;
}
8. 求树的结点
法一：
void _TreeSize(TreeNode* root,size_t* size)//真正用来计算树的结点
{
if(root == NULL)//空树
return;
++(*size);
_TreeSize(root->lchild,size);
_TreeSize(root->rchild,size);
}
size_t TreeSize(TreeNode* root)//求树的结点(不计算空结点)
{//用一个计数器，依次遍历结点，不为空就加1
size_t size = 0;
_TreeSize(root,&size);
return size;
}
法二：
size_t TreeSize1(TreeNode* root)//求树的结点
{//根结点加左右子树的结点树
if(root == NULL)//空树
return 0;
return 1+TreeSize(root->lchild)+TreeSize(root->rchild);
}
9. 求树的叶子结点个数
size_t TreeLeafSize(TreeNode* root)//求叶子结点的个数
{//左子树的叶子结点和右子树的叶子结点的和
if(root == NULL)//空树
return 0;
//当前结点是叶子结点
if(root->lchild == NULL && root->rchild == NULL)
return 1;
//当前结点不是叶子结点
return TreeLeafSize(root->lchild) + TreeLeafSize(root->rchild);
}
10. 求树第K层结点个数
size_t TreeKlevelSize(TreeNode* root,int K)//求第K层结点的个数(这里从第一层开始数)
{//求树的第K层结点数即求树的第K-1层结点子树的第一层结点数之和
if(root == NULL || K < 1)//非法输入
return 0;
if(K == 1)
return 1;
return TreeKlevelSize(root->lchild,K-1)+TreeKlevelSize(root->rchild,K-1);
}
11.求树的高度
size_t TreeHeight(TreeNode* root)//求树的高度
{//根结点左右子树的高度较高者加1
if(root == NULL)
return 0;
//当前结点无子树
if(root->lchild==NULL && root->rchild==NULL)
return 1;
//当前结点有子树
size_t lchild = TreeHeight(root->lchild);
size_t rchild = TreeHeight(root->rchild);
return 1+(lchild > rchild ? lchild : rchild);
}
12.给定一个数值，返回对应结点的指针（假设树上结点值无重复）
TreeNode* TreeFind(TreeNode* root,TreeNodeType to_find)//查找结点
{//给出一个数值，求对应结点的指针（假设无重复的数值结点)
if(root == NULL)
return NULL;
//按照先序遍历访问
if(root->data == to_find)
return root;
TreeNode* lresult = TreeFind(root->lchild,to_find);
TreeNode* rresult = TreeFind(root->rchild,to_find);
return lresult != NULL ? lresult :rresult;
}
13.给定一个结点，返回它的父结点
TreeNode* Parent(TreeNode* root,TreeNode* child)//求结点的父结点
{
if(root == NULL || child == NULL)//非法输入
return NULL;
//当前结点的左或右子树是输入参数孩子结点
if(root->lchild==child || root->rchild==child)
return root;
TreeNode* lresult = Parent(root->lchild,child);
TreeNode* rresult = Parent(root->rchild,child);
return lresult != NULL ? lresult : rresult;
}
14.给定一个结点，求它的左右子树
TreeNode* Lchild(TreeNode* root)//求当前结点的左子树
{
if(root == NULL)
return NULL;
return root->lchild;
}
TreeNode* Rchild(TreeNode* root)//求当前结点的右子树
{
if(root == NULL)
return NULL;
return root->rchild;
}