树的概念

通常树和递归有关，当面试官问你树的问题时，是在考察你递归算法的能力。

树常考结构

  • 普通二叉树
  • 平衡二叉树
  • 完全二叉树
  • 二叉搜索树
  • 四叉树
  • 多叉树
  • 红黑树

  • 自平衡二叉搜索树

    树的考点

  • 树的遍历：前序遍历，中序遍历，后序遍历

  • 树的序列化

    二叉树的特点

  • 每个结点最多有两颗子树

  • 左子树和右子树都是有顺序的，次序不能换

  • 即使某结点只有一个子树，也要区分左子树还是右子树

    二叉查找树

    二叉查找树是一种 特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点中。

    1. function Node(data, left, right) {
    2.   this.data = data;
    3.   this.left = left;
    4.   this.right = right;
    5.   this.show = show;
    6. }
    7. function show() {
    8.   return this.data;
    9. }

    Node 对象既保存数据，也保存和其他节点的链接（left 和 right），show() 方法用来显示 保存在节点中的数据。

    1. function BST() {
    2.   this.root = null;
    3.   this.insert = insert;
    4. }
    5. function insert(data) {
    6.   var n = new Node(data, null, null);
    7.   if (this.root == null) {
    8.       this.root = n;
    9.   }
    10.   else {
    11.       var current = this.root;
    12.       var parent;
    13.       while (true) {
    14.           parent = current;
    15.           if (data < current.data) {
    16.               current = current.left;
    17.               if (current == null) {
    18.                   parent.left = n;
    19.                   break;
    20.               }
    21.           }
    22.           else {
    23.               current = current.right;
    24.               if (current == null) {
    25.                   parent.right = n;
    26.                   break;
    27.               }
    28.           }
    29.       }
    30.   }
    31. }

  • 根结点为空就插入根结点，不为空就检查插入的节点。

  • 如果待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点

  • 每次插入都要从根节点开始遍历

    中序遍历

    中序遍历按照节点上的键值，以升序访问 BST 上的所有节点。中序遍历按元素大小从小到大遍历

    1. function inOrder(node) {
    2.   if (!(node == null)) {
    3.   inOrder(node.left);
    4.   console.log(node.show()) //遍历代码
    5.   inOrder(node.right);
    6.   }
    7. }

    从 nums.root 进入，一直执行 inOrder(node.left) 直到进入最左边的结点假设从 node1 进入 node2 ，此时 inOrder(node2.left) 为空，那么代码就会执行 inOrder(node1.right)。
    image.png

  • 10 的左子树为空时，执行遍历代码，然后检查右子树

  • 10 的右子树结束后，开始 执行 22 的遍历代码，然后检查 22 的右子树

    前序和后序

    1. function preOrder(node) {
    2. if (!(node == null)) {
    3.   console.log(node.show()) //遍历代码
    4.   preOrder(node.left);
    5.   preOrder(node.right);
    6. }
    7. }
    意 inOrder() 和 preOrder() 方法的唯一区别，就是 if 语句中代码的顺序。在 inOrder() 方法中，show() 函数像三明治一样夹在两个递归调用之间；在 preOrder() 方法中，show() 函数放在两个递归调用之前。同理后序遍历。