数据结构-二叉树

概念

• 是一棵树
• 每个节点，最多只能有 2 个子节点
• 树节点的数据结构 {value, left?, right?}

interface ITreeNode {
  value: number;
  left: ITreeNode | null;
  right: ITreeNode | null;
}

三种遍历

/**
 *     5
 *    / \
 *   3   7
 *  / \  /\
 * 2  4 6  8
 */

const tree: ITreeNode = {
  value: 5,
  left: {
    value: 3,
    left: {
      value: 2,
      left: null,
      right: null,
    },
    right: {
      value: 4,
      left: null,
      right: null,
    },
  },
  right: {
    value: 7,
    left: {
      value: 6,
      left: null,
      right: null,
    },
    right: {
      value: 8,
      left: null,
      right: null,
    },
  },
};

• 前序遍历：**root**->left->right
• 中序遍历：left->**root**->right
• 后序遍历：left->right->**root**

// 前序遍历
function proOrderTraverse(node: ITreeNode | null) {
  if (node == null) return;
  console.log(node.value);
  proOrderTraverse(node.left);
  proOrderTraverse(node.right);
}
// 测试
// proOrderTraverse(tree)

// 中序遍历
function inOrderTraverse(node: ITreeNode | null) {
  if (node == null) return;
  inOrderTraverse(node.left);
  console.log(node.value);
  inOrderTraverse(node.right);
}
// 测试
// inOrderTraverse(tree)

// 后序遍历
function postOrderTraverse(node: ITreeNode | null) {
  if (node == null) return;
  postOrderTraverse(node.right);
  postOrderTraverse(node.left);
  console.log(node.value);
}
// 测试
postOrderTraverse(tree);

二叉搜索树

• left（包括其后代）value <= root value
• right（包括其后代）value >= root value
• 可以使用 二分法 进行快速查找

/**
 *     5
 *    / \
 *   3   7
 *  / \  /\
 * 2  4 6  8
 */