数据结构-------二叉树的基本操作（递归实现）

        首先介绍二叉树的概念。

        不同于链表等线性表，树是一种非线性表。除了根节点没有前驱外，其余节点都有唯一的一个双亲结点和多个或0个孩子节点。其中，对每个节点来说，最多有两个孩子节点的称为二叉树。二叉树的几种形式如下图：

        对于二叉树的任一结点，都可以表示为以上的任一一种形式。所以，一个二叉树是由无数个子树组成。每棵子树都可以表示为上图中的任一一种形式。因此，在对二叉树进行遍历时，可以采取递归的形式来进行。

1. 二叉树的表示方法

        二叉树中的节点最多有两个孩子节点，分别为左孩子和右孩子。所以，这里采用孩子表示法来表示二叉树的结点。一个二叉树的结点包含一个数据域，该结点的左孩子及右孩子。

//二叉树中各节点的数据类型定义
typedef char TreeType;

//二叉树中各节点的结构定义
typedef struct TreeNode
{
    TreeType data;//节点的数据域
    struct TreeNode* lchild;//指向左节点的指针
    struct TreeNode* rchild;//指向右节点的指针
}TreeNode;       

2. 二叉树的初始化

        与用头结点的指针来表示一个链表类似，这里用根节点的指针来表示一棵树。初始时，树中没有任何结点，所以将根节点的指针取值置为空即可。因为这里要改变根节点的指针取值，所以，需要传递二级指针作为参数：

void TreeInit(TreeNode** proot)                                                                                                       
{
    if(proot == NULL)
    {
        //非法输入
        return;
    }

    *proot = NULL;
    return;
}

3. 二叉树的先序遍历

        先序遍历的顺序为：先遍历根节点，然后遍历左子树，最后遍历右子树。在遍历左右子树时，将左右子树再当做一棵树，按照先序遍历的顺序对其进行遍历。所以要对左右子树进行递归遍历。根节点为空时，即为递归出口。

        代码如下：

//先序遍历树
void PreOrder(TreeNode* root)
{
    if(root == NULL)
    {
        //空树
        printf("# ");//输出#表示空节点                                                                                                
        return;
    }

    //输出根节点
    printf("%c ",root->data);
    //递归遍历左子树
    PreOrder(root->lchild);
    //递归遍历右子树
    PreOrder(root->rchild);
    return;
}

4. 二叉树的中序遍历

        与先序遍历类似，在中序遍历时，先递归遍历左子树，然后访问根节点，最后递归遍历右子树。当结点为空时，即到达递归出口。

//中序遍历
void InOrder(TreeNode* root)
{
    if(root == NULL)
    {
        //空树
        printf("# ");
        return;
    }

    //中序遍历左子树
    InOrder(root->lchild);
    //输出根节点
    printf("%c ",root->data);
    //中序遍历右子树
    InOrder(root->rchild);
    return;
}

5. 二叉树的后序遍历

        有二叉树的先序遍历类似，在后序遍历时，先递归遍历左子树，再递归遍历右子树，最后访问根节点。结点为空时即为递归出口。

//后序遍历
void PostOrder(TreeNode* root)
{
    if(root == NULL)
    {
        //空树
        printf("# ");
        return;
    }
    //后序遍历左子树
    PostOrder(root->lchild);
    //后序遍历右子树
    PostOrder(root->rchild);
    ////输出根节点
    printf("%c ",root->data);
    return;
}

6. 二叉树的层序遍历

        二叉树的层序遍历需要借助一个队列来实现。

（1）首先将根节点入队

（2）取队首元素

（3）如果队首元素不为为空，转至（4），否则，直接返回

（4）访问队首元素，将队首元素出队，如果队首元素的左右孩子不为空，分别将左右孩子入队，转至（2）

        这里需要注意的是，入队列时保存的时结点的指针，所以，队列中保存的时树的结点指针类型的数据。有关队列的基本操作见：顺序队列/链式队列

        例如：

        代码如下：

//层序遍历
void LevelOrder(TreeNode* root)                                                                                                       
{
    if(root == NULL)
    {
        //空树
        return;
    }

    //借助队列来完成层序遍历
    SeqQueue queue;//定义一个顺序队列
    SeqQueueInit(&queue);//初始化队列
    
    //1. 将根节点的指针入队列
    SeqQueuePush(&queue,root);
    int ret;
    SeqQueueType front;
    while(1)
    {
        //2. 取队首元素，如果队列为空，说明已经遍历结束
        ret = SeqQueueTop(&queue,&front);
        if(ret == -1)
        {
            //队列已空，树已经遍历完
            break;
        }
   //3. 打印队首元素
        printf("%c ",front->data);
        //4. 队首元素出对列
        SeqQueuePop(&queue);
        //5. 如果队首元素的左右节点非空，则将左右节点的指针入队
        if(front->lchild != NULL)
        {
            SeqQueuePush(&queue,front->lchild);
        }
        if(front->rchild != NULL)
        {
            SeqQueuePush(&queue,front->rchild);
        }
        //6. 循环2.～5.
    }
    return;
}

7. 根据先序遍历的结果创建一棵树

        根据先序遍历的序列：ABC，还原出一棵树，则该树是不定的，如：

        所以除了知道先序遍历的序列，还需要知道空树的位置。如果空树用#表示，则AB##C##可唯一的表示为上述的左图。ABC####可唯一的表示为上述的右图。所以根据先序遍历的结果来还原一棵树时，除了先序序列外还需要空树的位置。

        因为已知的是先序遍历的结果，所以在创建树时，也是根据先根节点，再递归创建左子树，最后递归创建右子树的顺序来创建的。

        假如有一个字符串序列“AB##C##”。

（1）首先，定义当前位置下标index用来表示字符串中字符的下标，初始为0。

（2）然后根据index处的值来创建树的结点。当遇到空树时，不做处理，直接返回即可。

（3）最后，返回创建的树的根节点的指针。

        在利用递归函数创建结点时，

（1）根据A创建根节点。然后，index++，指向B

（2）再递归创建左子树。在创建左子树时，也是按照：根节点1->左子树1->右子树1的顺序来创建的。所以，

          根据B创建左子树的根节点1，然后index++，此时index指向#，说明左子树的左子树1为空树。index++

          index还指向#，说明左子树的右子树1为空树。此时根节点的左子树创建完毕。然后index++。

（3）再递归创建根节点的右子树。在创建右子树时，也是按照：根节点2->左子树2->右子树2的顺序来创建的。

          所以，此时，根据C创建右子树的根节点2，然后index++，此时，index指向#，说明右子树的左子树2为空

          树。index++，index还指向#，说明右子树的左子树2为空树。此时，index已经遍历完整个字符串序列

          了，直接返回即可。

        上述创建过程如下图所示：

        代码如下：

//根据先序遍历的结果创建一棵树
//arr为带#的先序序列字符串，size为字符串的长度，index为位置下标，null_flag为空树的标志
TreeNode* _TreeCreate(TreeType arr[],size_t size,size_t* index,char null_flag)
{                                                                                                                                     
    if(arr == NULL ||  size < 0 || index == NULL)
    {
        //非法输入
        return NULL;
    }
    
    if(*index == size)
    {
        //数组已遍历结束,树创建完成
        return NULL;
    }
    if(arr[*index] == null_flag)//null_flag是空树的标志，这里为#
    {
        //空树
        return NULL;
    }
    //创建根节点
    TreeNode* root = CreateNode(arr[*index]);
    (*index)++;
    //递归创建左子树
    root->lchild = _TreeCreate(arr,size,index,null_flag);
    (*index)++;
    //递归创建右子树
    root->rchild = _TreeCreate(arr,size,index,null_flag);
    return root;
}
TreeNode* TreeCreate(TreeType arr[],size_t size,char null_flag)
{
    size_t index = 0;
    TreeNode* root =  _TreeCreate(arr,size,&index,null_flag);
    return root;
}

8. 克隆一棵树

        树是递归创建的。所以在克隆一棵树时，也要通过递归来实现。这里采用先序遍历的方法来克隆一棵树。

（1）首先，根据已知树的根节点来创建新树的根节点

（2）再根据已知树的左子树来创建新树的左子树

（3）最后根据已知树的右子树来创建新树的右子树

（4）子树的创建过程也遵照（1）~（3）的顺序。

（5）当遇到空树时，直接返回，跳出递归函数即可。

        如已知树：

        新树的克隆创建过程与7中创建树的过程图相似。

        代码如下：

//克隆一棵树
TreeNode* TreeClone(TreeNode* root)
{
    if(root == NULL)
    {
        //空树
        return NULL;
    }
    
    TreeNode* new_root;
    //克隆根节点
    new_root = CreateNode(root->data);
    //递归克隆左子树
    new_root->lchild = TreeClone(root->lchild);
    //递归克隆右子树
    new_root->rchild = TreeClone(root->rchild);
    return new_root;
}

9. 求二叉树的结点个数

        这里有两种方法来实现该问题。

方法一：

        将先序遍历时的打印操作改为计数器加1操作，当遍历到一个非空节点时，计数器加1。所以，这里也利用递归函数来实现：

（1）首先遍历根节点，此时，计数器加1

（2）再递归遍历左子树。

（3）最后递归遍历右子树

（4）子树的遍历过程也遵循（1）~（3）

（5）当为空树时，直接返回，跳出递归函数即可。

        因为，在递归过程中要一直改变计数器变量的值，所以，该变量不能在递归函数中定义，而是在递归函数外定义，在根据该变量的地址来改变其值。

        代码如下：

void _TreeSize(TreeNode* root,size_t* count)
{
    if(root == NULL)
    {
        //空树
        return;
    }
    if(count == NULL)
    {
        //非法输入
        return;
    }
    (*count)++;
    _TreeSize(root->lchild,count);
    _TreeSize(root->rchild,count);
    return;
}

//求二叉树中的结点个数
size_t TreeSize(TreeNode* root)
{
    if(root == NULL)
    {
        //空树
        return 0;
    }
    size_t count = 0;
    _TreeSize(root,&count);
    return count;
}  

方法二：

        也是根据递归函数来实现。如果树不为空，则根结点的个数一定为1

（1）统计根节点左子树的个数

（2）统计根节点右子树的个数

（3）左子树的结点个数加右子树的结点个数再加1即为整棵树的结点个数

（4）统计左右子树结点个数时也是按照（1）~（3）来进行的

（5）当树为空时，根节点的个数为0，此时即到达递归函数的递归出口。

        代码如下：

//求二叉树中的结点个数
size_t TreeSize(TreeNode* root)
{
    if(root == NULL)
    {
        //空树
        return 0;
    }
    //统计左子树的节点个数
    size_t lsize = TreeSize(root->lchild);
    //统计右子树的节点个数
    size_t rsize = TreeSize(root->rchild);
    //整棵树的节点个数为左子树加右子树加根节点的个数                                                                                  
    return 1 + lsize + rsize;
}

10. 求二叉树中叶子结点的个数

        与上个问题类似，也有两种方法。

方法一：

       将先序遍历时的打印操作改为：先判断是否为叶子结点（左孩子和右孩子均为空），如果是，计数器加1操作，如果不是，则不作处理。当遍历到一个非空节点时，判断一次。所以，这里也利用递归函数来实现：

（1）先判断根节点

（2）再递归遍历右子树

（3）最后递归遍历左子树

（4）子树的遍历过程遵照（1）~（3）

（5）当为空树时，即到达递归出口

void _TreeLeafCount(TreeNode* root,size_t* count)
{
    if(root == NULL)
    {                                                                                                                                 
        return;
    }
    if(count == NULL)
    {
        //非法输入
        return;
    }
    if(root->lchild == NULL && root->rchild == NULL)
    {
        (*count)++;
    }
    _TreeLeafCount(root->lchild,count);
    _TreeLeafCount(root->rchild,count);
}

//求二叉树中叶子节点个数
size_t TreeLeafCount(TreeNode* root)
{
    if(root == NULL)
    {
        //空树
        return 0;
    }
    size_t count = 0;
    _TreeLeafCount(root,&count);
    return count;
}

方法二：

（1）当树为空时，叶子结点个数必为0

（2）当只有一个根节点时，也自己结点个数必为1

（3）不为（1）（2）时，先递归统计左子树的叶子结点个数，再递归统计右子树的叶子结点个数

（4）将左右子树叶子结点个数求和即为整个树的叶子结点个数

        代码如下：

//求二叉树中叶子节点个数
size_t TreeLeafCount(TreeNode* root)
{
    if(root == NULL)
    {
        //空树
        return 0;
    }
    if(root->lchild == NULL && root->rchild == NULL)
    {
        return 1;//只有根节点时
    }
    //递归统计左子树的叶子节点个数
    size_t lcount = TreeLeafCount(root->lchild);
    //递归统计右子树的叶子节点个数
    size_t rcount = TreeLeafCount(root->rchild);
    //左右子树的叶子节点个数求和                                                                                                      
    return lcount + rcount;
}

11. 求二叉树第K层结点的个数

        如果一棵树非空，K=1时，结点个数为1。K=2时，结点个数为2，此时，相当于求根节点的左孩子的个数及右孩子的个数之和，即对于左孩子和右孩子来说，是求K=1时的结点个数。

        因此，对于任意的K来说，相当于求根节点的左孩子的第K-1层结点个数和右孩子的第K-1层结点个数之和。依次往下递归，直到最后当K=1时，节点个数为1，此时即到达递归出口。

        代码如下：

//求二叉树第k层节点的个数
size_t TreeKLevelSize(TreeNode* root,int K)
{
    if(K < 1)
    {
        return 0;
    }
    if(root == NULL)
    {
        //空树
        return 0;
    }                                                                                                                                 
    if(K == 1)
    {
        return 1;
    }
    return TreeKLevelSize(root->lchild,K-1) + TreeKLevelSize(root->rchild,K-1);
}

12. 求二叉树的深度或高度

（1）当二叉树为空时，深度为0

（2）当只有根节点时，深度为1

（3）当不为（1）（2）时，二叉树的深度为根节点的左子树与根节点右子树深度的最大值加1

（4）其中，根节点的左右子树的深度按照（1）~（3）来递归求解

（5）上述的二叉树为空时，即为递归出口。

        代码如下：

//求二叉树的深度或高度
size_t TreeHeight(TreeNode* root)
{
    if(root == NULL)
    {
        //空树
        return 0;
    }
    if(root->lchild == NULL && root->rchild == NULL)
    {
        return 1;
    }
    //统计左子树的深度
    size_t lheight = TreeHeight(root->lchild);
    //统计右子树的深度
    size_t rheight = TreeHeight(root->rchild);
    //左右子树的最大值加1                                                                                                             
    return (lheight > rheight)? 1+lheight : 1+rheight;
}

13. 在二叉树中查找指定结点所在的地址

        该问题与先序遍历操作类似，当遍历到一个非空结点时，比较该结点是否与指定值相同，相同，则直接返回地址即可，不相同，则继续遍历。所以，先遍历根节点，在递归遍历左子树，最后递归遍历右子树。当树为空或找到指定值时，即到达递归出口。

        代码如下：

//在二叉树中查找节点(给定数值，求对应节点的指针，假设二叉树中的节点是不重复的)
TreeNode* TreeFind(TreeNode* root,TreeType to_find)
{
    if(root == NULL)
    {
        //空树
        return NULL;
    }
    if(root->data == to_find)
    {
        return root;
    }
    //递归遍历左子树进行查找
    TreeNode* lret = TreeFind(root->lchild,to_find);
    //递归遍历右子树进行查找                                                                                                          
    TreeNode* rret = TreeFind(root->rchild,to_find);
    return (lret == NULL)? rret : lret;
}

14. 求指定节点的父结点

        该问题与遍历操作类似，这里采用先序遍历的方式进行。当遍历到一个结点时，判断该结点的左右孩子是否为指定结点，如果是，则直接返回该结点即可。如果不是，则继续往后遍历，直到遍历完整棵树。所以，根据：先遍历根节点，在递归遍历左子树，最后递归遍历右子树的顺序来遍历整棵树。当树为空或找到指定结点的父节点时，即达到递归出口。

        代码如下：

//求当前节点的父节点
TreeNode* Parent(TreeNode* root,TreeNode* child)
{
    if(root == NULL)
    {
        //空树
        return NULL;
    }
    if(child == NULL)
    {
        //非法输入
        return NULL;
    }                                                                                                                                 
    if(root->lchild == child || root->rchild == child)
    {
        return root;
    }   
    TreeNode* lret = Parent(root->lchild,child);
    TreeNode* rret = Parent(root->rchild,child);
    return (lret != NULL)? lret : rret;
    
}   

15. 查找指定结点的左右孩子

        当指定结点不为空时，直接返回指定结点的左右孩子的指针即可。

        代码如下：

//查找指定节点的左孩子
TreeNode* LChild(TreeNode* node)
{                                                                                                                                     
    if(node == NULL)
    {
        return NULL;
    }
    return node->lchild;
}
//查找指定节点的右孩子
TreeNode* RChild(TreeNode* node)
{
    if(node == NULL)
    {
        return NULL;
    }
    return node->rchild;
}

16. 销毁一棵树

        销毁树时与遍历操作类似，当遍历到一个结点时，将该结点所占有的内存释放即可。上面有介绍过三种遍历方法。当采用先序遍历进行销毁时，先销毁的是根节点，这时根节点的左右孩子就找不到了，所以在销毁根节点前要保存左右孩子的地址。同理，中序遍历进行销毁时也需要保存右孩子的地址。而采取后序遍历进行销毁时，只需按照先左孩子，在右孩子，最后根节点的顺序进行递归销毁即可。此时，并不需要保存任何结点的地址。所以，这里采取后序遍历的方法进行销毁。当结点为空时，即到达递归出口。

        注意：当销毁一个节点后，为防止该结点的指针变为野指针，所以，free一个节点后，再将该指针置为空。所以这里需要改变指针的指向即要改变指针的值，因此在函数传参时，传递的是二级指针。

        代码如下：

void DestroyNode(TreeNode* node)
{
    free(node);
    return;
}

//void TreeDestroy(TreeNode** root);
//二叉树的销毁(后序遍历销毁)
void TreeDestroy(TreeNode** root)
{
    if(root == NULL)
    {   
        //非法输入
        return;
    }   
    if(*root == NULL)
    {   
        //空树
        return;
    }   
    TreeDestroy(&((*root)->lchild));//销毁左子树
    TreeDestroy(&((*root)->rchild));//销毁右子树
    DestroyNode(*root);//销毁根节点
    *root = NULL;//将销毁的结点置为空
    return;
}