欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-07 07:55:15
...

        首先介绍二叉树的概念。

        不同于链表等线性表,树是一种非线性表。除了根节点没有前驱外,其余节点都有唯一的一个双亲结点和多个或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;
}