空二叉树是什么

Fanly QA 2020-10-17 01:58:59 阅读(...)

二又树是有限元素的集合,该集合或者为空,或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时,称该二又树为空二又树。在二又树中,一个元素也称作一个结点。

二又树是有限元素的集合,该集合或者为空,或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时,称该二又树为空二又树。在二又树中,一个元素也称作一个结点。

空二叉树是什么

概念

二叉树是 n(n≥0)个结点的有限集合。n=0 的树称为空二叉树。n>0 的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。
显然,二叉树是一种有序树。二叉树中某个结点即使只有一个子树也要区分是左子树还是右子树。
二叉树中所有结点的形态共有 5 种:空结点、无左右子树结点、只有左子树结点、只有右子树结点和左右子树均存在的结点。

性质

性质 1:具有 n 个结点的非空二叉树有且仅有 n-1 个分支。
性质 2:非空二叉树的第 i 层最多有 2i-1 个结点。
性质 3:深度为 h 的非空二叉树最多有 2h-1 个结点。
性质 4:在任意非空二叉树中,若叶结点的数目为 n0,度为 2 的结点数目为 n2,则有关系 n0=n2+1 成立。
性质 5:具有 n(n>0)个结点的完全二又树的深度 h= log2n+1。

二叉树的基本运算

1、CreateBTree(bt,str):已知二叉树的括号表示法表达字符串 str,建二叉树 bt。
2、BTHeight(bt):求二叉树 bt 的高度。
3、NodeCount(bt):求二叉树 bt 的结点个数。
4、LeafCount(bt):求二叉树 bt 的叶子结点个数。

二叉树拓展

1、线索二叉树
按照某种遍历方式对二叉树进行遍历,可以把二叉树中所有节点排列为一个线性序列。但是,二叉树中每个节点在这个序列中的直接前驱节点和直接后继节点在二叉树的存储结构中并没有反映出来,只有在对二叉树遍历的动态过程中才能够得到这些信息。线索二叉树就是研究在静态下,如何得到这样的信息。
2、二叉排序树
3、最优二叉树(哈夫曼树)
在权为 w1,w2,…,wn 的 n 个叶子所构成的所有二叉树中,带权路径长度最小(即代价最小)的二叉树称为最优二叉树或 Huffman(赫夫曼)树。
4、平衡树
二叉平衡树(balanced binary tree)又称 AVL 树。它或者是一棵空二叉树,或者是具有下列性质的二叉树:
(1)它的左、右子树高度之差的绝对值不超过 1;
(2)它的左、右子树都是二叉平衡树。

收藏 0个人收藏
走进科技生活方式

评论交流

泪雪默认头像 请「登录」后参与评论
  1. 加载中..

相关推荐

  • Garbage disposer 垃圾处理器

    垃圾处理器不能处理什么垃圾

    垃圾处理器不可以处理牛奶盒、塑料袋、玻璃、金属等;动物毛发和大量热油;较大的骨棒;贝壳类不易被粉碎,还可能对机器刀片造成伤害;粽子叶和玉米皮,属于长纤维结构无法被磨得粉碎;猪皮和鱼鳞会造成机器噪音大和研磨不到位,大量的鱼鳞会造成下水道堵塞。
  • Garbage disposer 垃圾处理器

    如何选垃圾处理器

    选垃圾处理器需要考虑电机功率,直流电机技术更加成熟稳定,交流电机的质量相对轻一些;推荐选择无线开关,可免打孔不破坏水槽,随意粘贴,更安全;选择适合容量的垃圾处理器;自动反转功能的机器在遇到卡机时会自动恢复机器的运转;最后还要看噪音大小。
  • Garbage disposer 垃圾处理器

    安装垃圾处理器有哪些好处

    安装垃圾处理器可减少厨房尤其是存放垃圾桶的橱柜内的臭味,减少滋生蟑螂、细菌的可能;还可减少垃圾收运过程的二次污染;以及可以增加污水中易腐性有机物的含量利于污水处理,减少垃圾车的数量和对路面的污染;提高资源回收率减少渗滤液、沼气、烟气等排放。
  • Garbage disposer 垃圾处理器

    厨房垃圾处理器的缺点是什么

    使用垃圾处理器会浪费水,垃圾粉碎之后,必须用大量的水才能冲走,不仅增多水费,更会加重水资源短缺的危机;各种垃圾通过厨房垃圾处理器粉碎之后混在水中排出,容易导致下水道的堵塞;容易滋生细菌、生虫和引起堵塞;会增加污水处理难度。
  • Garbage disposer 垃圾处理器

    垃圾处理器的作用是什么

    垃圾处理器可方便地将菜头菜尾、剩菜剩饭等厨房垃圾粉碎后排入下水道,不会堵塞排水管和下水道;可以减少厨余垃圾对可回收物的污染,提高资源回收率以及改善填埋场和焚烧厂的处理状况;可迅速清理干净厨余垃圾,避免蚊虫细菌的骚扰;节省了下楼扔垃圾的时间。
  • 垃圾处理器 Garbage disposer

    什么是垃圾处理器

    垃圾处理器是一种现代化的厨房电器,安装于厨房水槽下方,与排水管相连,通过交流或直流电机驱动刀盘,利用离心力将粉碎腔内的食物垃圾粉碎后排入下水道,粉碎后颗粒直径小于4毫米,不会堵塞排水管和下水道,可避免食物垃圾因储存而滋生病菌、蚊虫和异味等。