欢迎来到 Claffic 的博客

前言：

往期给大家讲了链表，栈，队列等数据结构， 它们都是线性结构，而今天要讲的是一种非线性结构：树，让我们开始吧！

目录

1.什么是树？

2.有关树的概念

3.树的表示

⛏️4.树的实际应用

1.什么是树？

树，木本植物之总名… …欸，走错频道了？

其实数据结构中的树就是由大自然中的树定义来的，因为它们有很多相似之处：

自然中的树(倒置) 数据结构的树

怎么样？是不是还蛮像的

自然地，最顶端的那个结点就叫做 根节点 (图中A结点)

此时引出树的概念：

树是一种非线性的数据结构，它是由 n (n>=0)个有限结点组成的一个具有层次关系的集合。

我们仔细来看看这颗树：

从顶端开始，可以发现 根结点 以上是没有结点的，这里暂称为没有前驱结点

注意看，这棵树由根节点分出了三个方向，这三个箭头下又分别有一颗小树，我们称它们为子树。

把子树2拿出来再进行分割：

子树2下又有子树2.1…

子树下有子树，子树下又有子树… …

怎么有点像，

递归？

是的，可以理解为 树是递归定义的 。

接下来跟我看看下面的结构是不是树：

记住：这不是树，三条红边不能存在任意一条！！！

这部分的总结：

• 树顶端的结点称为根节点，根节点没有前驱结点；

• 子树之间不能相交；

• 除了根节点之外，每个结点有且仅有一个前驱节点；

• 一棵N个结点的树有N-1条边；

• 树是递归定义的。

2.有关树的概念

为了更好介绍树的有关概念，这里画一个更复杂的树：

• 结点的度：一个结点含有的子树个数（结点下的分支） 如结点A的度为5；

• 树的度：一棵树中最大的结点的度 如上树的度为5；

• 结点的层次：根是第1层，根的子节点所在层是第2层，如此递增；

• 树的高(深)度：最大的结点的层次 如上树的高(深)度是4；

• 叶子结点：度为0的结点（没有子树） 如结点 N，O；

• 双亲结点：如A是B，C，D，E，F的双亲结点；

•(孩)子结点：如B，C，D，E，F是A的(孩)子结点；

• 兄弟结点：具有相同双亲结点的子节点 如G，H；

• 堂兄弟结点：双亲在同一层的结点互为堂兄弟结点 如H，I；

• 非终端结点/分支结点：度不为0的结点 如C，D，E…；

• 结点的祖先：从根节点所经分支上的所有结点 如A是所有结点的祖先；

3.树的表示

毕竟是代码人，知道了树的结构，就要考虑怎么表示树比较好，

先来想想具体需要表示什么：

一个是要存储的数据，

另一个是结点与结点之间的关系；

重点看后者：

要表示关系，最好是既能在一条线上深入，又能关系到临近的一条线。

我们想到了孩子与兄弟：

typedef int DataType;struct Node{    struct Node* Child1; // 第一个孩子结点    struct Node* brother; // 指向兄弟结点    DataType data; // 结点中的数据域};

除了孩子兄弟表示法这种最常见的表示法，此外还有双亲表示法，孩子表示法，孩子双亲表示法。

由于树的结构本身是具有不确定性的，所以这里不做深一步的实现，大家知道有这些表示方法就好。

4.树的实际应用

这里说个最典型的吧：

文件资源管理器中的文件管理就是一个树结构：

总结：

这篇博客介绍了树，其实主要作用是为了后期二叉树做铺垫，大家了解它的结构，知道相关概念即可。

码文不易

如果你觉得这篇文章还不错并且对你有帮助，不妨支持一波哦