算法与数据结构之树与二叉树

爱被打了一巴掌 2022-12-16 06:28 229阅读 0赞

## 重要概念 ##

1. 树在计算机内的表示方式有①**双亲链表表示法**②**孩子链表表示法**③**孩子兄弟表示法**。

2. 在二叉树中，指针p所指结点为叶子结点的条件是**p→lchild==null&&p→rchild==null**。

3. 一棵二叉树的高度为h，则最大的结点数**2^h-1**。

4. 一个n个结点的二叉树，叶子结点的数量为n0，度为2的结点数量为n2，则n0与n2的关系是**n0=n2+1**。如果用二叉链表存储该二叉树，则空指针数量为**2\*n0+(n-n0-n2)=n+n0-n2=n+1**。

5. 在树的孩子兄弟表示法中，二叉链表的左指针指向**结点的第一个孩子**，右指针指向**结点的右兄弟**。

6. 先序遍历森林时，首先访问森林中第一棵树的**根结点**。

7. 对于一个具有n个结点的二叉树，当它为一棵**完全二叉树**时的深度是具有最小高度，当它为一棵**只有一个叶子结点的二叉树**时，具有最大高度。

8. 哈夫曼树是指**带权路径最小的二叉树，又称最优二叉树**。

9. 将一棵树转换成二叉树后，**根结点没有右子树**。

10. 线索二元树的**左线索指向其前驱**，**右线索指向其后继**。

11. 一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为？。

12. 二叉树的先序序列和中序序列相同的条件是**任何结点至多只有右子女的二叉树**。

13. 当哈夫曼树的叶子结点数目为n0，则该哈夫曼树共有**(2n0 - 1)**个结点。

14. 高度为K的完全二叉树至少有**2^(K-2)**个叶子结点。

15. 完全二叉树结点的**平衡因子取值只能为1，0**。

16. 一棵有n个结点的满二叉树0有个度为1 的结点，有**(n-1)/2**个分支(非终端结点)和**(n+1)/2**个叶子结点，该满二叉树的深度为**log2^(n+1)**。

17. 在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是：

**前提：**用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加"虚结点"。当编号为i和j的结点在顺序存储中的下标为m和n，则结点i和j在同一层的条件是**⌊log2^m⌋=⌊log2^n⌋**。

18. 高为h的二叉树只有度为0和2的结点时，则此类二叉树的结点至少为**2h-1**，至多为**2^h -1**。

19. 已知完全二叉树的第7层有10个叶子结点，则整个二叉树的**结点数最多为235**。

发表评论取消回复

表情：

评论列表（有 0 条评论，229人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构与算法之树（二）二叉查找树

*数据结构与算法之树** [数据结构与算法之树（一）二叉树概念及遍历方式（图文并茂）][Link 1] [数据结构与算法之树（二）二叉查找树][Link 2] [数...

矫情吗；*/ 2024年04月19日 09:56/ 0 赞/ 73 阅读

相关算法与数据结构之树与二叉树

重要概念 1. 树在计算机内的表示方式有①双亲链表表示法②孩子链表表示法③孩子兄弟表示法。 2. 在二叉树中，指针p所指结点为叶子结点的条件是p→lchild==nul

爱被打了一巴掌/ 2022年12月16日 06:28/ 0 赞/ 230 阅读

相关【数据结构与算法】二叉树

树 1.树、二叉树 2.二叉查找树 3.平衡二叉树、红黑树 4.递归树一、树 1.树的常用概念根节点、叶子节点、父节点、子节点、兄弟节点，还有节

逃离我推掉我的手/ 2022年11月29日 05:49/ 0 赞/ 213 阅读

相关数据结构与算法之树与二叉树

上篇博文主要介绍的是数据结构的线性结构，我们这篇博文介绍非线性结构—树与二叉树，我先介绍树的一些基本概念，树的遍历，再介绍二叉树相关概念和特性，以及二叉树的遍历，最后再树与二

我就是我/ 2022年06月07日 02:23/ 0 赞/ 405 阅读

相关【数据结构与算法】树（二）：二叉树

二叉树的特点每个结点最多有两颗子树，所以二叉树的度最大就是2. 左子树和右子树是由顺序的，不能够颠倒，即使树中只有一颗子树，也是要区分它是左子树还是右子树的

骑猪看日落/ 2022年05月21日 06:58/ 0 赞/ 280 阅读

相关数据结构与算法二叉树

数据结构与算法二叉树一、简述记--简单的有序链式二叉树添加、删除、遍历操作例子，有序：左孩子<父节点<右孩子。二、例子输入正数

柔情只为你懂/ 2022年05月17日 03:47/ 0 赞/ 260 阅读

相关二叉查找树-二叉树-数据结构与算法

C++ 语言: 二叉查找树二叉查找树(Binary Search Tree)，又被称为二叉搜索树。它是特殊的二叉树：对于二叉树，假设x为二叉树中的任意一个结点，x节

以你之姓@/ 2022年02月18日 20:51/ 0 赞/ 337 阅读

相关 C 数据结构与算法树之二叉树

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 树非线性数据结构稍后补充更多描述以及二叉树的链式存

傷城~/ 2022年01月16日 12:27/ 0 赞/ 244 阅读

相关二叉树（数据结构与算法）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXh

￡神魔★判官ぃ/ 2021年12月24日 00:34/ 0 赞/ 325 阅读

相关数据结构与算法之二叉树

基本结构 ![70][] 结点的度：结点与下一层几个结点相关联，它的度就是多少（A的度是3）树的度：所有结点里最高结点的度（最高的度是A为3）叶子结点：度

曾经终败给现在/ 2021年06月11日 15:11/ 0 赞/ 480 阅读