学习笔记之树

[学习笔记] - 树

树的存储结构

双亲表示法

问题： 查找孩子需要遍历。

改进：

孩子(双亲)表示法

• 表头节点
• 孩子链表节点

---

二叉树

经典应用 - 折半查找决策树

二叉树的五种形态

1. 空二叉树
2. 只有一个根节点
3. 根节点只有左子树
4. 根节点只有右子树
5. 根节点既有左子树又有右子树

特殊二叉树

1. 斜树 （左斜树，右斜树）

2. 满二叉树

   1. 叶子最下层
   2. 非叶子节点度一定为2
   3. 同样深度的二叉树中，满二叉树节点个数最多

3. 完全二叉树

   1. 叶子出现最下两层
   2. 最下层叶子节点集中在左部连续位置
   3. 倒数第二层，如果有叶子，一定在右部连续位置
   4. 如果有节点度为1，该节点只有左孩子
   5. 同样节点数的二叉树，完全二叉树深度最小

二叉树性质

1. 第i层至多 \(2^{i-1}\) 个节点
2. 深度k的二叉树至多有 \(2^k -1\) 个节点
3. 对于任何二叉树，终端节点数为\(n_0\), 度为2节点数为\(n_2\), 则\(n_0\)=\(n_2\) +1
4. （重要）具有n个节点的完全二叉树，深度为\(\lfloor log_2n \rfloor\) + 1
5. （重要）如果n个节点的完全二叉树节点按层序编号
   1. i=1，i是二叉树的根，无双亲；i>1, 双亲为\(\lfloor i/2 \rfloor\)
   2. 如果2i > n, 则 无左孩子，否则左孩子是2i
   3. 如果2i+1 > n, 则无右孩子，否则右孩子是2i+1

二叉树的存储结构

1. 顺序存储

2. 链式存储

二叉树的遍历

广度优先

code （使用queue）

public static void bft(Node root) {
  if (root == null) {
    return ;
  }

  Queue<Node> nodes = new LinkedList<>();
  nodes.add(root);

  while (!nodes.isEmpty()) {
    Node node = nodes.remove();

    System.out.println(node.getValue());

    if(node.getLeft() != null) {
      nodes.add(node.getLeft());
    }
    if(node.getRight() != null) {
      nodes.add(node.getRight());
    }
  }
}

深度优先 - 递归

前序遍历（根左右）

code

public static void preOrder(Node node) {
  if (node == null) {
    return;
  }
  System.out.println(" " + node.getValue());
  preOrder(node.getLeft());
  preOrder(node.getRight());
}

##### 中序遍历（左根右）

code

public static void inOrder(Node node) {
  if (node == null) {
    return;
  }
  inOrder(node.getLeft());
  System.out.println(" " + node.getValue());
  inOrder(node.getRight());

}

##### 后序遍历（左右根）

code

public static void postOrder(Node node) {
  if (node == null) {
    return;
  }
  postOrder(node.getLeft());
  postOrder(node.getRight());
  System.out.println(" " + node.getValue());

}

---

线索二叉树

二叉链表存储结构的问题

1. 存在空指针域
2. 如果寻找前驱和后继需要整个遍历 （中序）

添加指向前驱和后继的指针（线索），加上线索的二叉链表称为线索链表，相应的 二叉树称为线索二叉树。空域改为 直接前驱或者后继， 通过添加标志域（ltag，rtag） 来表明是孩子还是前驱/后继。

中序线索化：

类似于双向链表，二叉线索链表添加一个头结点，lchild指向二叉树根节点，rchild指向中序遍历最后一个节点。中序第一个节点（最左下）lchild和中序最后一个（最右下）rchild 指向头结点

如果所用的二叉树需经常遍历或查找节点是需要某种遍历序列中的前驱和后继，可采用线索二叉树