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

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

程序员文章站 2022-03-13 10:34:11
...

二叉树的拷贝
求二叉树的节点个数
求二叉树叶子节点个数
求第K层节点的个数
求二叉树的高度
在二叉树中查找节点:给定值,返回地址
已知孩子节点,求父节点
求出当前节点的左子树,右子树

  • 二叉树 的拷贝分为深拷贝和浅拷贝
    深拷贝:重新申请物理内存,将原有二叉树的复制过去,
    优点:修改其中一个二叉树,不会影响其他和此二叉树相同的二叉树。
    缺点:占用内存大,耗时

    浅拷贝:不会重新申请物理内存,在一块物理内存上完成复制
    优点:节省空间,时间。
    缺点:牵一发而动全身。只要修改其中一个一个节点,其他的元素都会受到影响
    应用:父进程创建子进程时,地址空间共享,而数据写实拷贝。这里的写实拷贝就应用了深浅拷贝的原理。
    数据结构-二叉树的常见操作(基于递归实现)
    本文中实现深拷贝

//二叉树的深拷贝
BinTreeNode* BinTreeClone(BinTreeNode* root)
{
      //空树
      if(  root==NULL)
      {
            return NULL;
      }
      //拷贝根节点
      BinTreeNode* newnode=BinTreeNodeCreate(root->data);
      newnode->data=root->data;
      //递归拷贝左子树
      newnode->pleft=BinTreeClone(root->pleft);
      //递归拷贝右子树
      newnode->pright=BinTreeClone(root->pright);
      return newnode;
}

求节点个数时,包括根节点


//求二叉树的节点个数(递归版本)
size_t BinTreeSizeR(  BinTreeNode* root)
{
      if(  root==NULL)
      {
            return 0;
      }
      return 1+BinTreeSizeR(root->pleft)+BinTreeSize(root->pright);
}



void _BinTreeSize(BinTreeNode* root,size_t * size)
{
      if(root==NULL)
      {
            return;
      }

      ++(*size);
      _BinTreeSize(root->pleft,size);
      _BinTreeSize(root->pright,size);
}

//求二叉树节点个数(非递归:通过参数带值方法)
size_t BinTreeSize(  BinTreeNode* root)
{
      size_t size=0;
      if(  root==NULL)
      {
            return 0;
      }

      _BinTreeSize(root,&size);
      return size;

}

叶子节点:度为0的节点,即终端没有孩子节点的节点个数


//求二叉树叶子节点的个数
size_t BinTreeLeafSize(BinTreeNode* root)
{

      if(root==NULL)
      {
            return 0;
      }
      if(  root->pleft==NULL&&root->pright==NULL)
      {
            return 1;
      }
      return BinTreeLeafSize(root->pleft)+BinTreeLeafSize(root->pright);
}

求第K层节点个数,我们无法直接获得第K层节点个数,但我们可以将问题化整为零,先求第K-1层节点,求K-1层节点时先求第(k-1)-1层节点,后面以此类推,知道第1层节点,即根节点,然后将将第K层左右子树节点相加,即可


//求二叉树中第K层节点的个数
size_t BinTreeK_leveSize(BinTreeNode* root,int k)
{
      if(root==NULL||k<1)
      {
            return 0;
      }
      if(  k==1)
      {
            return 1;
      }
      return BinTreeK_leveSize(root->pleft,k-1)+BinTreeK_leveSize(root->pright,k-1);
}

//求二叉树的高度



 //使用递归
        // 如果该树只有一个结点,它的深度为1.如果根节点只有左子树没有右子树,
        // 那么树的深度为左子树的深度加1;同样,如果只有右子树没有左子树,
        // 那么树的深度为右子树的深度加1。如果既有左子树也有右子树,
        // 那该树的深度就是左子树和右子树的最大值加1.
C语言版本
size_t BinTreeHight(BinTreeNode* root)
{
      //空树
      if(  root==NULL)
      {
            return 0;
      }
      //只有一个节点,即左右子树为空
      if(root->pleft==NULL&&root->pright==NULL)
      {
            return 1;
      }
      //递归遍历左子树节点个数
      size_t l_height=BinTreeHight(root->pleft);
      //递归遍历右子树节点个数
      size_t r_height=BinTreeHight(root->pright);
      //比较根节点左子树节点个数和根节点加上右子树节点个数,谁大取谁
      return (1+l_height)>(1+r_hight)?(1+l_height):(1+r_height);
}

C++版本:
class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if(pRoot==NULL)
        {
            return 0;
        }
        return max(TreeDepth(pRoot->left),TreeDepth(pRoot->right))+1;

    }
};

//在二叉树中查找节点:给定值,返回指针
BinTreeNode* BinTreeFind(BinTreeNode* root,DataType to_find)
{
      //空树
      if(  root==NULL)
      {
            return NULL;
      }
      //根节点 就是要找的值
      if(  root->data==to_find)
      {
            return root;
      }

      else
      {
            //递归遍历左子树,查找给定值
            BinTreeNode* LResult=BinTreeFind(root,to_find);
            //递归遍历左子树,查找给定值
            BinTreeNode* RResult=BinTreeFind(root,to_find);

            return LResult!=NULL?LResult:RResult;
      }
}

//给定孩子节点,求父节点
BinTreeNode* BinTreeParent(BinTreeNode* root,BinTreeNode* child)
{
      //空树或者孩子节点为NULL
      if(root==NULL||child==NULL)
      {
            return NULL;
      }
      //如果根节点就是目标给定孩子节点的父节点
      else if(root->pleft==child||root->pright==child)
      {
            return root;
      }
      else
      {
          //递归遍历左子树,查找给定孩子节点的父节点
          BinTreeNode* LResult= BinTreeParent(  root->pleft,child);
          //递归遍历左子树,查找给定孩子节点的父节点
          BinTreeNode* RResult= BinTreeParent(  root-pright,child);
           return (LResult!=NULL)?LResult:RResult;
      }

}

//求当前节点的左子树
BinTreeNode* BinTreeFindLchild(BinTreeNode* root)
{
      if(  root==NULL)
      {
            return NULL;
      }
      return root->pleft;

}

//求当前节点的右子树
BinTreeNode* BinTreeFindRchild(BinTreeNode* root)
{
      if(  root==NULL)
      {
            return NULL;
      }
      return root->pright;
}