数据结构—基础知识(12):二叉树算法补充

发布时间:2024年01月24日

数据结构—基础知识(12):二叉树算法补充

  1. 复制二叉树

    【算法步骤】

    如果是空树,递归结束,否则进行以下操作:

    • 申请一个新结点空间,复制根结点;
    • 递归复制左子树;
    • 递归复制右子树。
    void Copy(BiTree T,BiTree &NewT)
    {//复制一棵和T完全相同的二叉树
        if(T==NULL)//如果是空树,递归结束
        {
            NewT=NULL;
            return;
        }
        else
        {
            NewT=new BiTNode;
            NewT->data=T->data;//复制根结点
            Copy(T->lchild,NewT->lchild);//递归复制左子树
            Copy(T->rchild,NewT->rchild);//递归复制右子树     
        }//else
    }
    
  2. 计算二叉树的深度

    【算法步骤】

    如果是空树,递归结束,深度为0,否则进行以下操作:

    • 递归计算左子树的深度记为m;
    • 递归计算右子树的深度记为n;
    • 如果m大于n,二叉树的深度为m+1,否则为n+1
    int Depth(BiTree T)
    {//计算二叉树T的深度
        if(T==NULL) return 0;//如果是空树,深度为0,递归结束
        else
        {
            m=Depth(T->lchild);//递归计算左子树的深度记为m
            n=Depth(T->rchild);//递归计算右子树的深度记为n
            if(m>n) return(m+1);//二叉树的深度为m与n的较大者加1
            else return(n+1)
        }
    }
    
  3. 统计二叉树中结点的个数

    int NodeCount(BiTree T)
    {//统计二叉树T中结点的个数
      if(T==NULL) return 0;//如果是空树,则结点个数为0,递归结束
        else return NodeCount(T->lchild)+NodeCount(T->rchild)+1
            //否则结点个数为左子树的结点个数+右子树的结点个数+1
    }
    
    
  4. 统计二叉树叶子结点个数

    int LeafNode(BiTree T)
    {//统计二叉树T中叶子结点的个数
        if(T==NULL)
            return 0;//空树,返回0
        else if(T->lchild==NULL&&T->rchild==NULL)
            return 1;//叶子结点,返回1
        else//递归
            return LeafNode(T->lchild)+LeafNode(T->rchild)
    }
    
文章来源:https://blog.csdn.net/qq_42257631/article/details/135827235
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。