数据结构中树与二叉树原理解析

Love The Way You Lie 2022-10-22 02:57 91阅读 0赞

今天我们分析数据结构中树与二叉树原理：这是数据结构中各种树的基础。

1、树的定义

树(Tree):N个结点构成的有限集合。 树中有一个称为”根(Root)”的特殊结点 其余结点可分为若干个互不相交的树，称为原来结点的”子树”，如同：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

其中A为根节点，最下面一层为子节点。

2、树的常用基本术语

1)结点的度：结点的子树个数

2)树的度：树中所有结点中最大的度

3)叶结点：度为0的结点，即没有子节点的节点（最后一层节点）。

4)父结点：有子树的结点是其子树的根结点的父结点

5)子结点：若A是B的父结点，B就是A的子结点

如同：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1][]

3、树与非树的区别：

1)子树是不相交的，一旦出现相交就不再成为树，比如下图红色的线出现时，就不再是树了。

2)除了根结点之外，每个结点之有且只有一个父结点。

3)一个N个结点的树只有N-1条边。

如同所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 2][]

4、二叉树的定义：

1)度为2的树（树中所有结点中最大的度，即一个节点下最多有两个子节点）。

2)子树有左右顺序之分 ，一般称为左子树和右子树。

如同：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 3][]

数据结构中树与二叉树原理解析到此结束，其实还有平衡二叉树、红黑树、B树、B+树等以后会逐个详细分析。而下一篇篇我们分析通过哈夫曼树解决字符的最优编码问题，敬请期待！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221022/ff6d14a73d1a4da5bafa3ebd22267fca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1]: /images/20221022/95ec968c42b0429faa017d7aa23bc182.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 2]: /images/20221022/c09cff45b0154f0d8868b68cd76f8d03.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 3]: /images/20221022/b09e9e5e52544b118e73ca1797c65ddf.png