美文网首页
60_二叉树的深层特性

60_二叉树的深层特性

作者: 编程半岛 | 来源:发表于2018-07-26 17:11 被阅读2次

关键词:二叉树的5个重要性质

性质1:在二叉树的第i层最多有2^(i-1)个结点(i>=1)

性质2:高度为k的二叉树最多有2^k - 1个结点。(k>=0)

性质3:对任何一颗二叉树,如果其叶结点有n0个,度为2的非叶结点有n2个,则n0 = n2 + 1。

证明过程

性质4:具有n个结点的完全二叉树的高度为|logn|+1。(其中|logn|表示对logn向下取整)

证明过程

性质5:一颗有n个结点的完全二叉树(高度为|logn| +1),按层次对结点进行编号(从上到下,从左到右),对任意结点i有:

声明:此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记,文章中包含狄泰软件资料内容,一切版权归狄泰软件所有!
实验环境:ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4

相关文章

  • 60_二叉树的深层特性

    关键词:二叉树的5个重要性质 性质1:在二叉树的第i层最多有2^(i-1)个结点(i>=1) 性质2:高度为k的二...

  • 2022.9.30(晴)

    中国女篮战胜澳大利亚女篮,挺进决赛。60_

  • 59_树到二叉树的转换

    关键词:双亲孩子表示法、孩子兄弟表示法、二叉树的定义、特殊的二叉树、完全二叉树的特性 0. 双亲孩子表示法 每个结...

  • 二叉树的公共祖先

    问题1 平衡二叉树的公共祖先,找到该树中两个指定节点的最近公共祖先 原理 首先需要了解平衡二叉树的特性,平衡二叉树...

  • 数据结构-如何用二叉树实现hash表(C语言)

    在用二叉树实现散列表之前,首先需要明白的是二叉树与散列表各自的特性。 对于二叉树,主要表现形式是一对二...

  • 114. Flatten Binary Tree to Link

    题目 给定一个二叉树的根 root,将这棵二叉树展开为链表。这个链表有两个特性 链表节点由二叉树类表示,节点左节点...

  • 排序算法(五):堆排序

    从二叉搜索树和平衡二叉树的介绍中,可以发现二叉树这种结构具有一个很好的特性,当有序的二叉树构造完成之后,更改树中节...

  • Days27 笔试·专业课程

    1.二叉树 前序遍历: 中(根)左右 中序遍历: 左中右 后序遍历: 左右中 先要利用以下几个特性: 特性A,对于...

  • 红黑树

    一、二叉搜索树 二叉搜索树,也称有序二叉树,排序二叉树,具有以下特性: 1、是一棵二叉树 2、若任意节点的左子树不...

  • 普通树与二叉树的相互转化及哈夫曼树的了解

    普通树与二叉树的相互转化及哈夫曼树的了解 二叉树与普通树的转化 二叉树的种种特性使得它更便于处理,如果能将普通树转...

网友评论

      本文标题:60_二叉树的深层特性

      本文链接:https://www.haomeiwen.com/subject/dhvbmftx.html