算法学习总结（3）——二叉树数据结构重点知识总结

╰+攻爆jí腚メ 2024-04-17 17:45 47阅读 0赞

# 一、关键术语  #

1. **节点的度**：一个节点含有的子树的个数称为该节点的度；

2. **叶节点或终端节点**：度为零的节点；

3. **非终端节点或分支节点**：度不为零的节点；

4. **父亲节点或父节点**：若一个节点含有子节点，则这个节点称为其子节点的父节点；

5. **兄弟节点**：具有相同父节点的节点互称为兄弟节点；

6. **节点的层次**：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

7. **树的高度或深度**：树中节点的最大层次；

8. **堂兄弟节点**：父节点在同一层的节点互为堂兄弟；

9. **节点的祖先**：从根到该节点所经分支上的所有节点；

10. **孙**：以某节点为根的子树中任一节点都称为该节点的子孙。

11. **森林**：由m（m>=0）棵互不相交的树的集合称为森林；

12. **满二叉树：一棵深度为k，且有2^k-1 (2的k次方减一)个节点称之为满二叉树 ；**

13. **完全二叉树：**完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。**叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。**

# 二、二叉树的性质 #

1.在非空二叉树中，第i层的结点总数不超过2^(i-1),i>=1；

2.深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点；

3.对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

4.具有n个结点的**完全二叉树**的深度为**K =\[log2n」+1(取下整数)**

5.有N个结点的**完全二叉树**各结点如果用顺序方式存储，**则结点之间有如下关系： 若I为结点编号则 如果I>1，则其父结点的编号为I/2；**

6.**完全二叉树，如果2\*I<=N，则其左儿子（即左子树的根结点）的编号为2\*I；若2\*I>N，则无左儿子； 如果2\*I+1<=N，则其右儿子的结点编号为2\*I+1；若2\*I+1>N，则无右儿子。**

7.给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2\*n，n)/(n+1)。

8.设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i

# 二叉树的遍历三种方式，如下：  #

（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。

（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。

（3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。

发表评论取消回复

表情：

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

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

相关阅读

相关二叉树基础知识总结

题外话昨晚面了腾讯，问了一个完全二叉树的题，竟然让我算了快10分钟，因为等比公式记错了导致最后用最原始的方法推算结果也没算对，一下子就懵了。本来精心准备了1周的面

﹏ヽ暗。殇╰゛Y/ 2022年10月01日 00:58/ 0 赞/ 204 阅读

相关【数据结构】二叉树面试题总结

为了对二叉树的知识进行巩固，今天我们来解析5道二叉树的经典面试题。这五道面试题如下： 1. 求二叉树中最远两个结点的距离； 2. 判断一棵树是否是完全二叉树； 3.

朴灿烈づ我的快乐病毒、/ 2022年07月14日 07:16/ 0 赞/ 205 阅读

相关二叉树知识点总结

二叉树是一种比较重要的数据结构，这里对一些常见的二叉树的基础知识做一个总结，具体的代码实现放到下一篇博文首选对二叉树进行一个分类，二叉树分为以下的几种:

- 日理万妓/ 2022年07月11日 15:57/ 0 赞/ 247 阅读

相关数据结构（一）二叉树基础知识总结

一、树的定义树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。 ![20170324154348019][] 树具有的特点有

柔光的暖阳◎/ 2022年05月20日 06:13/ 0 赞/ 176 阅读

相关二叉树基础知识总结

一、树的定义树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。 ![20170324154348019][] 树具

超、凢脫俗/ 2022年05月19日 21:07/ 0 赞/ 213 阅读

相关数据结构-二叉树基础知识总结

数据结构-二叉树基础知识总结 -------------------- ①二叉树之递归实现篇：[\[递归实现\]-二叉树][-] 包括如下递归操作：

快来打我*/ 2022年05月19日 06:39/ 0 赞/ 220 阅读

相关数据结构之二叉树总结

数据结构之二叉树一种非线性数据结构 1. 树（森林） 1. 四种表示方法 1. 树形表示法

约定不等于承诺〃/ 2022年05月09日 23:04/ 0 赞/ 179 阅读

相关数据结构总结---------非线性表（二叉树）

数据结构总结---------非线性表（二叉树） 1.二叉树 1.1 二叉树的遍历 1.2 存储结构 1.顺序存储结构

- 日理万妓/ 2022年03月15日 05:30/ 0 赞/ 214 阅读

相关二叉树知识点总结

二叉树知识点总结二叉树的基本术语定义二叉树的计算公式完全二叉树叶节点计算完全二叉树的节点数计算解题思路—二分思路

偏执的太偏执、/ 2022年01月29日 01:04/ 0 赞/ 438 阅读

相关【数据结构】树、二叉树总结（一）

知识结构 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nL

ゞ浴缸里的玫瑰/ 2021年09月21日 06:54/ 0 赞/ 428 阅读