背景音乐 Crazy Frog(疯狂的青蛙) 初中时听得歌 听一次洗脑一次。
typedef 结点 节点；
//输入法脑残，懒得去区分了，正确为结点
今天我们来讲树，首先来讲自然界的树，树有根，有枝干，有叶子，并且从根到叶子有且只有一条路径（奇葩的树，不考虑）。这是人类最喜欢接触的一种存储结构。欢喜吧，不信吧。
比如，你去图书馆看书，啊看什么呢？我想看小说，最新的有什么呢？《不学好数据结构你凭什么找老婆？老公也别想！》这本就不错。那么，其实你就经历了一个树的搜索的过程。我们来还原下
第一，你想看书。书就是根节点，书下一级有什么呢？工程类，科学类，历史类，小说类……你选了小说，小说有经典，最新……，你选了最新，最新下有《不学好数据结构你凭什么找老婆？老公也别想！》，《不学好C++你凭什么找老婆？老公也别想！》……，你选了第一本。这就是树的搜索。
那么来介绍下树的基本概念：
树有N个结点，N大于等于0，等于0时是空树。
忽略次要，直击主要
易错点混析
1.祖先结点 从根到这个叶子路上的所有结点
2.与你直接相连的上级结点为双亲结点（有且只有一个！根节点没有）
3.有相同双亲的节点成为兄弟结点。
树中一个结点的子节点个数称为该节点的度，度数为零的结点为叶子结点（与离散数学上的出度相同，注意区分）。树中结点最大的度称为树的度，欧耶！
非叶子结点称为分支结点（或非终端结点）。
结点的层次
根节点为第一层（部分教材为第零层，魔性），以此向下累加。
结点深度 从根节点往下数层数。
结点高度 阿西吧，从叶子结点往上数
树的高度/深度 树的最大层。
有序树 结点左右排列是有顺序的，别给人家乱换。
无序树 结点左右无序，随便换。
路径 从一个结点到另一个结点所经过的结点的有序序列。
路径长度 经过边的个数
性质性质
性质
性质
重要的事情多说几遍
树的结点数等于所有结点度数的和+1
度数为M的树的第i层上至多有M^(i-1)个结点