主页

go数据结构(二叉树的定义)

2023-04-11 10:31AM

二叉树是我们平时遇到的最常见的树结构,它是一种特殊的树,顾名思义,就是每个节点最多有两个「分叉」,即两个子节点,分别是左子节点和右子节点,不过,二叉树并不要求每个节点都有两个子节点,有的节点只有左子结点,有的节点只有右子节点。

特点:

1. 二叉树是一种非线性的数据结构,由节点构成,每个节点最多只有两个子节点,且每个结点最多有两颗子树,所以二叉树中不存在度大于2的结点。

2. 每个节点都有一个父节点(除了根节点),可以有左子节点和右子节点,没有则为空;

3. 二叉树可以是空树,即不包含任何节点;

4. 左子树和右子树也是二叉树,且它们的节点也可以有左子节点和右子节点;

5.左子树和右子树是有顺序的,次序不能任意颠倒。即使树中某结点只有一棵子树,也要区分它是左子树还是右子树

6. 二叉树的节点之间有明确定义的父子关系,父节点到子节点的路径称为边,节点的层数从根节点开始算起,根节点的层数为1;

7. 二叉树的遍历方式有前序遍历、中序遍历和后序遍历;

8. 二叉树的深度是指从根节点到最远叶子节点的路径上的节点数,而二叉树的高度是指从最底层叶子节点到根节点的路径长度;

9. 在二叉查找树中,左子树所有节点的值都小于根节点的值,右子树所有节点的值都大于根节点的值。

比如以下都是二叉树:

根据左右子节点的饱和度,我们又从二叉树中提取出两种特殊的二叉树 —— 满二叉树完全二叉树

满二叉树即所有分支节点都有左右子节点,并且所有叶子节点都在同一层上,如上面的图2便是满二叉树。

满二叉树的特点有:
1)叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
2)非叶子结点的度一定是2。
3)在同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多。

完全二叉树要复杂一些,深度为 k 有 n 个节点的二叉树,当且仅当其中的每一节点,都可以和同样深度 k 的满二叉树,序号为 1 到 n 的节点一对一对应时,称为完全二叉树,比如上面的图3就是完全二叉树。

完全二叉树的特点有:
1)叶子结点只能出现在最下层和次下层。
2)最下层的叶子结点集中在树的左部。
3)倒数第二层若存在叶子结点,一定在右部连续位置。
4)如果结点度为1,则该结点只有左孩子,即没有右子树。
5)同样结点数目的二叉树,完全二叉树深度最小。
满二叉树一定是完全二叉树,但反过来不一定成立。

参考:Go 数据结构和算法篇(十五):二叉树的定义和存储 - 极客书房

返回>>

登录

请登录后再发表评论。

评论列表:

目前还没有人发表评论