数据结构 非线性结构

树

数的定义

专业定义：

1. 有且只有一个根的节点
2. 有若干的互不相交的子树，这些子树本身也是一棵树

通俗的定义：

1. 树是由节点和边组成
2. 每个节点只有一个父节点，但可以有多个子结点
3. 但有一个节点例外，该节点没有父节点，此节点为根节点。

专业术语：

节点

父节点

子节点

子孙

祖先

堂兄弟

深度：从根节点到最底层节点的层数。（根节点是第一层）

叶子节点：没有子节点的节点

非终端节点：实际就是非叶子节点

度:子结点的个数

树的分类

一般树

任意一个节点的子节点的个数都不受限制

二叉树

任意一个节点的子节点的个数最多为两个，且子节点的位置不可变更

分类：

1. 一般二叉树
2. 满二叉树 在不增加树的层数的前提下，无法再多添加一个节点的二叉树。
3. 完全二叉树 如果只是删除了满二叉树最底层最右边的连续若干个节点。

森林

n 个互不相交的树的集合

树的存储

二叉树的存储

连续存储完全二叉树

优点：

查找某个节点的父节点和子结点速度(也包括有没有子结点)很快.

缺点：

耗用的内存空间比较大.

链式存储

一般树的存储

双亲表示法

求父节点方便。

孩子表示法

求子节点方便。

双亲孩子表示法

求父节点和子结点都很方便。

二叉树表示法

把一个普通的树转换成二叉树来存储。

具体转换方法:

1. 设法保证任意一个节点的左指针指向它的第一个孩子，右指针指向它的堂兄弟。
2. 只要能满足此条件，就可以把一个普通的树转换成为二叉树。
3. 一个普通树转换成的二叉树一定没有右子树。

森林的存储

先把森林转化成二叉树，再存储二叉树

树的操作

遍历

先序遍历

先访问根节点

再先序访问左子树

再先序访问右子树

先序遍历顺序：ABDCEFG

先序遍历顺序：ABCDEFLQMNS

中序遍历

中序遍历左子树

再访问根节点

再中序遍历右子树

中序遍历顺序：CDFELBAMSNQA

后序遍历

中序遍历左子树

中序遍历右子树

遍历根节点

后序遍顺序：FLEDCBSNMQA

已知两种遍历序列求原始二叉树

通过先序和中序 或者 中序和后序

可以还原出原始的二叉树

但是通过先序和后序是无法还原出原始的二叉树的

换种说法：

只有通过先序和中序，或通过中序与后序

我们才能可以唯一的确定一个二叉树

示例1（已知先序和中序求后序）：

先序：ABCDEFGH

中序：BDCEAFHG

画出图如下：

求后序：DECBHGFA

示例2（已知中序和后序求先序）：

中序：BDCEAFHG

后序：BECBHGFA

画出图如下：

求先序：ABCDEFGH

树的应用

1. 树是数据库中数据组织的一种重要形式。
2. 操作系统子父进程的关系本身就是一棵树。
3. 面向对象中的类的继承关系
4. 赫夫曼树

​

本文链接：https://cloud.tencent.com/developer/article/1557678

本文采用CC BY-NC-SA 3.0 Unported协议进行许可，转载请保留此文章链接