前言

笔者看过很多的数据结构的课程和图书，市面上写的都良莠不齐，走了很多的弯路，所以笔者决定自己写下对数据结构的理解。在我的数据结构的文章或者说课程中，我将考研的常见题目和一些生活化的例子融入数据结构的课程中，尽量让你理解起来不困难，尽快学会这个知识点，在这只讨论数据结构，不讨论算法，请系好安全带，坐好了。

1.1 树的基本概念和常见术语

在看第一小节时，可以看完第一小节后，第二小节的树的应用写的非常精彩，应该能让你有醍醐灌顶的感觉。

正式开始，不知道你有没有家谱，树更多的时候像一个家谱，一个根结点下有子结点，子结点下有自己的家族。

看这个图，A是太太太太太爷爷，分为两个家族

分为4代人，注意我举的例子，我们这一代有4代人，我是J的话，我上面还有3代人，于是引出深度和高度的概念。

结点的深度是从根结点开始自顶向下，

结点的高度是从叶结点开始自底向上。

树表示的是一种层次关系，具有以下两个特点，

1）树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。

2）树中的所有结点都可以有零个或多个后继。

（1）树的度就是树中结点的最大度数。结点的孩子数就是结点的度，如D结点的度为3，树的度就是3了，因为没有比它更大的了。

（2）路径就是边，路径长度是从根到每个节点的路径长度的总和

1.2 树的应用

在我们平常生活中，有很多地方都能见到树的影子，

案例一：

在计算机系统的设计中，我们也能看到树的影子。如windows的文件系统，如

C:\ProgramFiles\MozillaFirefox\browser

在这我们可以看到它是用树的结构来存储，在C盘中肯定有很多和program files一样的文件夹，我们称为兄弟结点，度为0，没有子女的结点称为叶结点（一个树长到最后只剩下叶子了）。

案例二：

在windows的powershell中我们输入tree会得到，一张特别长的树图，看这像不像树结构。

1.3 树的性质

树具有以下最基本的性质：

1）树中的结点数等于所有结点的度数之和加1

2）度为m的树中第i层上m^i-1个结点

3）高度为h的m叉树至多有（m^h-1）/（m-1）个结点

4）具有n个结点的m叉树的最小高度为[log_m(n(m-1))+1]

常见的题目：

树最适合用来表示（元素之间具有分支层次关系）的数据。解：树是用来表示层次关系的。

一棵树具有n个结点的树的所有结点的度数之和为（n-1）。

解：见基本性质