数据结构-树

最后更新：2017-12-16

一、什么是树(tree)？

1.1 定义

在日常生活中, 我们总能看到树. 树是由树根、树枝、树叶组成。在计算机中， 树的结构根现实中的树很类似，像是倒过来的树。 如下:

由上图, 对照现实生活, 树根为树的开始(例如:A点), 树枝可以理解为有子分支的(例如: B点、C点)， 树叶可以为没有子分支的(例如: F点、J点)。

可能当初搞计算机的觉得这样不够清晰, 就对树做了统一:

• 每一个元素称之为节点(node), 现在树根、树枝、树叶都叫节点了。
• 树根 称之为 根节点。
• 除树根(根节点), 树枝、树叶可以看做一个单独的树, 我们可以称之为原树的子树（subtree)。 其中有个很明显的特征就是 它们是互不相交的

1.2 如何判断树与非树

根据上图，可以总结树的如下特点:

• 每个节点有零个或多个子节点；
• 每一个非根节点有且仅有一个子节点;
• 除了根节点外, 每个子节点可以分为多个不相交的子树。

下面的都为非树

1.3 树的基本术语

1. 查找: 静态查找、动态查找

二分查找(Binary Search)

前提: 有序查找、 数组

树的定义

树的表示

数组不行， 链表会造成空间浪费

二叉树，就是儿子-兄弟表示法

二叉树

存储结构

二叉树遍历
递归方式

1. 先序遍历

2. 中序遍历

3. 后序遍历
   
   

4. 层序遍历
   二维结构序列化
   队列实现层序
   
   
   
   

二叉树应用

必须要有中序