你说什么是树？

树是什么？是路边的小树苗吗？是的，就是它们～

我们现在把那个树压扁了，放在书上面，就是我们今天要谈的数据结构——树，之所以称之为树，是因为两者看起来挺像的，但是我觉得这个玩意更像是树根，你觉得呢？

属性

• 树中每个元素成为节点
  
• 用来连线相邻节点之间的关系，叫作父子关系
  
• 父节点是同一节点的节点之间互称为兄弟节点。
  
• 没有父节点的节点为根节点
  
• 没有子节点节点为叶子节点或者叶节点
  

节点的度

子树的个数，我们常说做人要有个度，说的做人要有基本的准则，看你能容忍多少不同的规则，放在树中就是表示这个节点的度，容忍的树杈有多少

节点的高度

节点到叶子节点的最长路径（边数）

节点的深度

这个节点到根节点所经历的边的个数

节点的层数

节点的深度+1

树的高度

根节点的高度

二叉树（Binary Tree）

二叉树的每个节点最多只有两个节点，分别为左子节点和右子节点。二叉树的不一定有两个子节点，也可能只有一个。

叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。

完全二叉树

叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。

完全二叉树看起来并不完全，那么它为什么叫完全二叉树呢？

这要从怎么存储一棵二叉树开始说起，首先最简单是就是链式存储法，每个节点包含三部分，左指针、右指针和数据区，通过左右指针很容易把整个树串起来，这个很容易理解，也比较容易实现。

还有另外一种存储方式，那就是线性存储，把树的节点放到数组中，采用广度遍历的方式存放节点，假设节点的下标为 i ，那么 X 的左子树节点的位置为 2*i，右子树节点的位置为 2*i+1。

线性存储是，完全二叉树仅仅是浪费了下标为 0 的存储位置，其余位置全部会填满。如果不是完全二叉树的话，会在数组中出现空缺位置，浪费存储空间。

判断一棵树是否为完全二叉树，可以将节点按照自上往下，从左往右的顺序将节点逐一放入数组中，若中间不会产生多余的存储位置，那么就是完全二叉树。

二叉树的遍历

假设现在有一个棵树，拥有三个节点，分别是：父节点A、左子树节点B，右子树节点C。

二叉树的遍历分为三种，先序遍历、中序遍历和后序遍历。所谓的先序、中序和后序是指的是父节点的位置。

先序遍历

先输出父节点，再输出左子树节点，最后输出右子树节点。顺序为：A->B->C

// p表示父节点
traverse(p) {
    print p;// 打印父节点
    traverse(p->left);//打印左子树节点
    traverse(p->right);//打印右子树节点
}

中序遍历

先输出左子树节点，再输出父节点，最后输出右子树节点。顺序为：B->A->C

// p表示父节点
traverse(p) {
    traverse(p->left);//输出左子树节点
    print p;// 输出父节点
    traverse(p->right);//输出右子树节点
}

后序遍历

先输出左子树节点，再输出右子树节点，最后输出父节点。顺序为：B->A->C

// p表示父节点
traverse(p) {
    traverse(p->left);//打印左子树节点
    traverse(p->right);//打印右子树节点
    print p;// 打印父节点
}

时间复杂度

遍历的过程中每个节点会被访问一遍，故时间复杂度为O(n)