树的基本介绍#

一、简介#

不同于先前的线性数据结构，比如数组，链表，栈，队列。

树则是一种表示层次结构的数据结构。🤔

树长什么样子？？你在大自然里肯定见过吧，长下面的样子。

咳咳！其实是这样的-> 🌲

不过在数据结构里的树是倒过来的，根部在上面，分支树杈在下面。

最顶上的叫做根，其余叫做节点。可以包含任何数据类型。

我们来介绍一下专有名词，容许我标记个编号chaillo！

一个节点可能有指向其他节点的链接或者引用，这些称之为该节点的孩子节点。

比如根节点1链接了2和3，那么2和3就可以被成为1的孩子，1就成为他们的双亲（父亲）。

这里提到三个名词，分别是根——root，孩子——children，双亲——parent。

同一双亲的节点被成为兄弟，比如4和5是兄弟——sibling。

没有孩子的节点比如4，5，6，7都被称为叶子——leaf。

注意我们只能通过节点访问另一个节点时是单向的，比如我们只能顺着根节点访问4，而4不能往上找到根。

我们可以把树定义为一个根节点和一些子树——subtree组成。比如上面那张图就有两个子树，一左一右。

二、子树#

树可以被称为一个递归的数据结构，他有着递归属性。因此可以被定义为一个树根节点和其他子树组成。

比如这里有根节点1，和圈圈里面的两个子树。

对于节点2来说，有三个子树。

三、属性#

• 如果树有N个节点，那它就有N-1个链接或者边（edges)，就是图中链接两个球的线。比如对2节点来说，就有一个来自1的传入链接，和3个传出链接。
• 树的深度：被定义为从根到节点X的路径长度。路径上的每一条边都会贡献一个长度，所以也可以说成，从根到X的路径上的边数。比如对于5节点来说，从根到他这会经历两条边，所以深度为2.
• 高度：可以被定义为该节点到一个叶子节点的最长路径上的边数。对于3来说，从3到最长叶子节点11会走两个边，所以高度为2。而叶子节点的高度为0。
• 树的高度：被定义为从根节点到最长叶子的距离，比如上图就是3.
• 二叉树：每个节点最多有两个孩子的树。

我们可以这么看一棵树。

眼熟吗？就是个复杂的链表。😎

中间存储数据，两边各自存储孩子的地址。

1
struct Node{
2
  int data;
3
  Node* left;
4
  Node* right;
5
}

四、应用#

• 计算机的文件存储，天然的树形目录结构😎
• 应用组织数据，便于查找
• Trie树，被用来存储字典。
• 网络路由算法。