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

这篇具有很好参考价值的文章主要介绍了数据结构—基础知识(12):二叉树算法补充。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数据结构—基础知识(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,否则进行以下操作:文章来源地址https://www.toymoban.com/news/detail-824343.html

    • 递归计算左子树的深度记为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)
    }
    

到了这里,关于数据结构—基础知识(12):二叉树算法补充的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 探索树形数据结构,通识树、森林与二叉树的基础知识(专有名词),进一步利用顺序表和链表表示、遍历和线索树形结构

      结点之间有分支,具有层次关系 树的定义 : 树 (tree)是n(n≥0)个有限集。 若n = 0,则称为空树; 若n 0,则它满足如下两个条件: 有且仅有一个特定的称为根(Root)的结点; 其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,.....,Tm,其中每一个集合本身又是一棵树,并称为根的

    2024年02月01日
    浏览(47)
  • 数据结构--基础知识

    数据结构是计算机科学中研究数据组织、存储和管理的方法和原则。它涉及存储和操作数据的方式,以便能够高效地使用和访问数据。 数组(Array):数组是一种线性数据结构,由相同类型的元素按顺序排列而成。数组具有固定长度,在内存中占据连续的位置。可以通过索引

    2024年02月14日
    浏览(40)
  • 数据结构|基础知识定义

    1.值传递、地址传递、值返回、地址返回 1 值传递 :普通变量作为函数参数传递是单向的值传递,只是将实参的值复制一份给形参变量,形参的改变不会影响实参的值,因为所在内存空间不同 如果传递的是地址,被调函数使用指针接收,如果在被调函数中,没有更改指针指向

    2024年02月08日
    浏览(42)
  • 数据结构基础知识、名词概述

    整体知识框架 1.1.1 数据、 数据元素、 数据项和数据对象 数据 (Data) 是客观事物的符号表示,是所有 能输入到计算机中并被计算机程序处理的符号 的总称 。如数学计算中用到的整数和实数,文本编辑中用到的字符串,多媒体程序处理的图形、 图像、声音及动画等通过特殊编

    2024年02月15日
    浏览(49)
  • 数据结构—基础知识:哈夫曼树

    哈夫曼(Huffman)树 又称最优树,是一类带权路径长度最短的树,在实际中有广泛的用途。哈夫曼树的定义,涉及路径、路径长度、权等概念,下面先给出这些概念的定义,然后再介绍哈夫曼树 路径 :从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 路

    2024年02月21日
    浏览(43)
  • 【数据结构】树的基础知识及三种存储结构

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 把它叫做树是因为它

    2024年02月09日
    浏览(48)
  • 数据结构—基础知识(15):哈夫曼树

    哈夫曼(Huffman)树 又称最优树,是一类带权路径长度最短的树,在实际中有广泛的用途。哈夫曼树的定义,涉及路径、路径长度、权等概念,下面先给出这些概念的定义,然后再介绍哈夫曼树 路径 :从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 路

    2024年02月19日
    浏览(45)
  • 【数据结构】C--单链表(小白入门基础知识)

    前段时间写了一篇关于顺序表的博客,http://t.csdn.cn/0gCRp 顺序表在某些时候存在着一些不可避免的缺点: 问题: 1. 中间 / 头部的插入删除,时间复杂度为 O(N) 2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 3. 增容一般是呈 2 倍的增长,势必会有一定的空间

    2024年02月16日
    浏览(48)
  • 【数据结构】栈和队列(栈的基本操作和基础知识)

    🌈个人主页: 秦jh__ https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343 🔥 系列专栏: 《数据结构》 https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482 目录  前言 栈 栈的概念和结构 栈的实现 ​编辑 数组栈的实现 总的声明 初始化  插入 删除 取栈顶元素 销毁 判断是否为空

    2024年02月03日
    浏览(51)
  • 【数据结构】—— 队列基础知识以及数组模拟队列的分析、演示及优化

    ❤️一名热爱Java的大一学生,希望与各位大佬共同学习进步❤️ 🧑个人主页:@周小末天天开心 各位大佬的点赞👍 收藏⭐ 关注✅,是本人学习的最大动力 感谢! 📕该篇文章收录专栏—数据结构 目录 什么是队列? 数组模拟队列 分析 存入队列的步骤 使用数组模拟队列—

    2024年01月19日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包