树

树是一种比较高级的基础数据结构，由 n 个有限节点组成的具有层次关系的集合。

树的定义：

  1. 有节点间的层次关系，分为父节点和子节点。
  2. 有唯一一个根节点，该根节点没有父节点。
  3. 除了根节点，每个节点有且只有一个父节点。
  4. 每一个节点本身以及它的后代也是一棵树，是一个递归的结构。
  5. 没有后代的节点称为叶子节点，没有节点的树称为空树。

二叉树：每个节点最多只有两个儿子节点的树。

满二叉树：叶子节点与叶子节点之间的高度差为 0 的二叉树，即整棵树是满的，树呈满三角形结构。在国外的定义，非叶子节点儿子都是满的树就是满二叉树。我们以国内为准。

完全二叉树：完全二叉树是由满二叉树而引出来的，设二叉树的深度为 k，除第 k 层外，其他各层的节点数都达到最大值，且第 k 层所有的节点都连续集中在最左边。

树根据儿子节点的多寡，有二叉树，三叉树，四叉树等，我们这里主要介绍二叉树。

一、二叉树的数学特征

  1. 高度为 h≥0 的二叉树至少有 h+1 个结点，比如最不平衡的二叉树就是退化的线性链表结构，所有的节点都只有左儿子节点，或者所有的节点都只有右儿子节点。
  2. 高度为 h≥0 的二叉树至多有 2^h+1 个节点，比如这棵树是满二叉树。
  3. 含有 n≥1 个结点的二叉树的高度至多为 n-1，由 1 退化的线性链表可以反推。
  4. 含有 n≥1 个结点的二叉树的高度至少为 logn，由 2 满二叉树可以反推。
  5. 在二叉树的第 i 层，至多有 2^(i-1) 个节点，比如该层是满的。

二、二叉树的实现

二叉树可以使用链表来实现。如下：

  1. // 二叉树
  2. type TreeNode struct {
  3.     Data  string    // 节点用来存放数据
  4.     Left  *TreeNode // 左子树
  5.     Right *TreeNode // 右字树
  6. }

当然，数组也可以用来表示二叉树，一般用来表示完全二叉树。

对于一棵有 n 个节点的完全二叉树，从上到下，从左到右进行序号编号，对于任一个节点，编号 i=0 表示树根节点，编号 i 的节点的左右儿子节点编号分别为：2i+1,2i+2，父亲节点编号为：i/2，整除操作去掉小数。

如图是一棵完全二叉树，数组的表示：

树 - 图1

我们一般使用二叉树来实现查找的功能，所以树节点结构体里存放数据的 Data 字段。

三、遍历二叉树

构建一棵树后，我们希望遍历它，有四种遍历方法：

  1. 先序遍历：先访问根节点，再访问左子树，最后访问右子树。
  2. 后序遍历：先访问左子树，再访问右子树，最后访问根节点。
  3. 中序遍历：先访问左子树，再访问根节点，最后访问右子树。
  4. 层次遍历：每一层从左到右访问每一个节点。

先序，后序和中序遍历较简单，代码如下：

  1. package main
  3. import (
  4.     "fmt"
  5. )
  7. // 二叉树
  8. type TreeNode struct {
  9.     Data  string    // 节点用来存放数据
  10.     Left  *TreeNode // 左子树
  11.     Right *TreeNode // 右字树
  12. }
  14. // 先序遍历
  15. func PreOrder(tree *TreeNode) {
  16.     if tree == nil {
  17.         return
  18.     }
  20.     // 先打印根节点
  21.     fmt.Print(tree.Data, " ")
  22.     // 再打印左子树
  23.     PreOrder(tree.Left)
  24.     // 再打印右字树
  25.     PreOrder(tree.Right)
  26. }
  28. // 中序遍历
  29. func MidOrder(tree *TreeNode) {
  30.     if tree == nil {
  31.         return
  32.     }
  34.     // 先打印左子树
  35.     MidOrder(tree.Left)
  36.     // 再打印根节点
  37.     fmt.Print(tree.Data, " ")
  38.     // 再打印右字树
  39.     MidOrder(tree.Right)
  40. }
  42. // 后序遍历
  43. func PostOrder(tree *TreeNode) {
  44.     if tree == nil {
  45.         return
  46.     }
  48.     // 先打印左子树
  49.     PostOrder(tree.Left)
  50.     // 再打印右字树
  51.     PostOrder(tree.Right)
  52.     // 再打印根节点
  53.     fmt.Print(tree.Data, " ")
  54. }
  56. func main() {
  57.     t := &TreeNode{Data: "A"}
  58.     t.Left = &TreeNode{Data: "B"}
  59.     t.Right = &TreeNode{Data: "C"}
  60.     t.Left.Left = &TreeNode{Data: "D"}
  61.     t.Left.Right = &TreeNode{Data: "E"}
  62.     t.Right.Left = &TreeNode{Data: "F"}
  64.     fmt.Println("先序排序：")
  65.     PreOrder(t)
  66.     fmt.Println("\n中序排序：")
  67.     MidOrder(t)
  68.     fmt.Println("\n后序排序")
  69.     PostOrder(t)
  70. }

表示将以下结构的树进行遍历：

树 - 图2

结果如下：

  1. 先序排序：
  2. A B D E C F 
  3. 中序排序：
  4. D B E A F C 
  5. 后序排序
  6. D E B F C A

层次遍历较复杂，用到一种名叫广度遍历的方法，需要使用辅助的先进先出的队列。

  1. 先将树的根节点放入队列。
  2. 从队列里面 remove 出节点，先打印节点值，如果该节点有左子树节点，左子树入栈，如果有右子树节点，右子树入栈。
  3. 重复2，直到队列里面没有元素。

核心逻辑如下：

  1. func LayerOrder(treeNode *TreeNode) {
  2.     if treeNode == nil {
  3.         return
  4.     }
  6.     // 新建队列
  7.     queue := new(LinkQueue)
  8.     // 根节点先入队
  9.     queue.Add(treeNode)
  10.     for queue.size > 0 {
  11.         // 不断出队列
  12.         element := queue.Remove()
  14.         // 先打印节点值
  15.         fmt.Print(element.Data, " ")
  17.         // 左子树非空，入队列
  18.         if element.Left != nil {
  19.             queue.Add(element.Left)
  20.         }
  22.         // 右子树非空，入队列
  23.         if element.Right != nil {
  24.             queue.Add(element.Right)
  25.         }
  26.     }
  27. }

完整代码：

  1. package main
  3. import (
  4.     "fmt"
  5.     "sync"
  6. )
  8. // 二叉树
  9. type TreeNode struct {
  10.     Data  string    // 节点用来存放数据
  11.     Left  *TreeNode // 左子树
  12.     Right *TreeNode // 右字树
  13. }
  15. func LayerOrder(treeNode *TreeNode) {
  16.     if treeNode == nil {
  17.         return
  18.     }
  20.     // 新建队列
  21.     queue := new(LinkQueue)
  23.     // 根节点先入队
  24.     queue.Add(treeNode)
  25.     for queue.size > 0 {
  26.         // 不断出队列
  27.         element := queue.Remove()
  29.         // 先打印节点值
  30.         fmt.Print(element.Data, " ")
  32.         // 左子树非空，入队列
  33.         if element.Left != nil {
  34.             queue.Add(element.Left)
  35.         }
  37.         // 右子树非空，入队列
  38.         if element.Right != nil {
  39.             queue.Add(element.Right)
  40.         }
  41.     }
  42. }
  44. // 链表节点
  45. type LinkNode struct {
  46.     Next  *LinkNode
  47.     Value *TreeNode
  48. }
  50. // 链表队列，先进先出
  51. type LinkQueue struct {
  52.     root *LinkNode  // 链表起点
  53.     size int        // 队列的元素数量
  54.     lock sync.Mutex // 为了并发安全使用的锁
  55. }
  57. // 入队
  58. func (queue *LinkQueue) Add(v *TreeNode) {
  59.     queue.lock.Lock()
  60.     defer queue.lock.Unlock()
  62.     // 如果栈顶为空，那么增加节点
  63.     if queue.root == nil {
  64.         queue.root = new(LinkNode)
  65.         queue.root.Value = v
  66.     } else {
  67.         // 否则新元素插入链表的末尾
  68.         // 新节点
  69.         newNode := new(LinkNode)
  70.         newNode.Value = v
  72.         // 一直遍历到链表尾部
  73.         nowNode := queue.root
  74.         for nowNode.Next != nil {
  75.             nowNode = nowNode.Next
  76.         }
  78.         // 新节点放在链表尾部
  79.         nowNode.Next = newNode
  80.     }
  82.     // 队中元素数量+1
  83.     queue.size = queue.size + 1
  84. }
  86. // 出队
  87. func (queue *LinkQueue) Remove() *TreeNode {
  88.     queue.lock.Lock()
  89.     defer queue.lock.Unlock()
  91.     // 队中元素已空
  92.     if queue.size == 0 {
  93.         panic("over limit")
  94.     }
  96.     // 顶部元素要出队
  97.     topNode := queue.root
  98.     v := topNode.Value
  100.     // 将顶部元素的后继链接链上
  101.     queue.root = topNode.Next
  103.     // 队中元素数量-1
  104.     queue.size = queue.size - 1
  106.     return v
  107. }
  109. // 队列中元素数量
  110. func (queue *LinkQueue) Size() int {
  111.     return queue.size
  112. }
  114. func main() {
  115.     t := &TreeNode{Data: "A"}
  116.     t.Left = &TreeNode{Data: "B"}
  117.     t.Right = &TreeNode{Data: "C"}
  118.     t.Left.Left = &TreeNode{Data: "D"}
  119.     t.Left.Right = &TreeNode{Data: "E"}
  120.     t.Right.Left = &TreeNode{Data: "F"}
  122.     fmt.Println("\n层次排序")
  123.     LayerOrder(t)
  124. }

输出：

  1. 层次排序
  2. A B C D E F