CAI

# 二叉树

具有层次关系的一种数据结构，客观世界中普遍存在。比如：图书信息管理，人物关系层次化，国家地区分级管理等等。

特点：

  • 查找效率高
  • 具有一个称为 根 的节点.
  • 根节点子节点本身可以构成一棵树， 称为 子树
  • 子节点只能有一个父节点

# 二叉树

二叉树是一种度为二的树的数据结构，一个节点最多包含左右两个子树。

二叉树类型：

  • 斜二叉树

往一边倾斜的树， 构成线性结构。

  • 完美二叉树 / 满二叉树

除了叶节点（最后一层子树），每个节点都有左右子树，而且叶节点都在同一层。

  • 完全二叉树

一棵深度为 k 的有 n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 i（1≤i≤n）的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

# 二叉树存储结构

# 顺序存储结构（数组的实现方式）

  • 完全二叉树

完全二叉树可以用顺序存储结构存放，按照从上到下，左到右编号存放。

  1. 父节点查找：非根节点 i / 2 向下取整，即为父节点编号
  2. 左子树：序号为 i * 2， 如果 2i <= n(总结点数) ，则表示没有左子树
  3. 右子树：2i + 1 ， 如果 2i + 1 <= n(总结点数) ，则表示没有右子树
  • 一般二叉树（特点：浪费空间）

先将一般二叉树补全成 完全二叉树， 没有的节点留空。

# 链表的存储结构

基本结构：

class LinkNode {
  constructor() {
    // 数据
    this.data = null;
    // 左子树节点
    this.left = null;
    // 右子树节点
    this.right = null;
  }
}

# 操作集

  1. 判断是否为空
  2. 遍历二叉树
  3. 创建二叉树

# 二叉树遍历

# 先序遍历

先根节点，然后左子树，最后右子树。

function PreOrderTraversal(node) {
  if (node) {
    // 访问根节点
    console.log(node.data);
    PreOrderTraversal(node.left);
    PreOrderTraversal(node.right);
  }
}

# 中序遍历

先左子树，然后根节点，最后右子树。

function InOrderTraversal(node) {
  if (node) {
    InOrderTraversal(node.left);
    // 访问根节点
    console.log(node.data);
    InOrderTraversal(node.right);
  }
}

# 后序遍历

先左子树，然后右子树，最后根节点

function PostOrderTraversal(node) {
  if (node) {
    PostOrderTraversal(node.left);
    PostOrderTraversal(node.right);
    // 访问根节点
    console.log(node.data);
  }
}

# 层序遍历

从上到下，从左到右遍历。

思路： 访问节点，将左右子树保存到队列中。一次循环访问节点，重复上一次操作。

class LinkNode {
  constructor(data = null) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

function LevelOrderTraversal(node) {
  if (!node) return;
  // 这里使用数组表示队列
  let queue = [];
  queue.push(node);

  while (queue.length !== 0) {
    // 抛出队列父节点
    const n = queue.pop();

    // 访问节点数据
    console.log(n.data);

    // 左右子树放入队列中
    if (n.left) queue = [n.left, ...queue];
    if (n.right) queue = [n.right, ...queue];
  }
}

# 非递归实现遍历

递归底层使用堆栈实现，我们可以直接使用堆栈来实现。

思路：先循环将左子树压入堆栈中，然后访问节点数据，转向访问右子树。


/**
 * 二叉树遍历实现
 */

class BinTree {
  constructor(data = null) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

// 中序遍历非递归实现
function InOrderTraversal(bintree) {
  let T = bintree;
  const stack = new Stack();
  while (T !== null || !stack.isEmpty()) {
    while (T) {
      stack.push(T);
      T = T.left;
    }
    if (!stack.isEmpty()) {
      T = stack.pop();
      // 访问数据
      console.log(T.data);
      T = T.right;
    }
  }
}

# 应用例子

# 输出所有叶子节点（没有子树的节点）

通过树遍历将结果输出。

function PreOrderPrintLeave(bintree) {
  if (bintree) {
    // 输出叶子节点
    if (!bintree.left && !bintree.right) console.log(bintree.data);
    PreOrderPrintLeave(bintree.left);
    PreOrderPrintLeave(bintree.right);
  }
}

# 求树的高度

计算左右子树高度最大值+1 即为树的高度。递归计算子树高度即可。

function TreeHight(bintree) {
  let SUM = 0,
    HL = 0,
    HR = 0;
  if (bintree) {
    HL = TreeHight(bintree.left);
    HR = TreeHight(bintree.right);
    // 左右子树最大高度加1，为树的高度。
    SUM = Math.max(HL, HR) + 1;
  }
  // 如果子树为空，返回0
  return SUM;
}

# 给出两个序列构造一颗树

  • 只能先序序列和中序序列，或者后序序列和中序序列。
  • 必须要有一个是中序序列，否则无法构造出来一棵树。

例如：

  • 先序序列为： [4,3,8,9,10,5,7,11,2,6,15,1,16,20]
  • 中序序列为： [9,8,10,3,7,5,11,4,15,6,2,16,1,20]
// 二叉树数据结构
class BinTree {
  constructor() {
    this.data = null;
    this.left = null;
    this.right = null;
  }
}

// 根据先序中序序列生成二叉树
function makeTree(preOrder, inOrder) {
  let BT = new BinTree();

  if (preOrder.length < 1 || inOrder.length < 1) return null;

  // 先序第一个为父节点data
  const data = preOrder[0];
  BT.data = data;
  preOrder = preOrder.slice(1);

  // 获取中序根节点索引
  const idx = inOrder.indexOf(data);

  // 根据索引获取左右子树集合
  const inOrderLeft = inOrder.slice(0, idx);
  const inOrderRight = inOrder.slice(idx + 1);

  // 根据中序序列左右子树长度获取先序序列左右子树集合
  const preOrderLeft = preOrder.slice(0, inOrderLeft.length);
  const preOrderRight = preOrder.slice(inOrderLeft.length);

  // 生成左右子树
  BT.left = makeTree(preOrderLeft, inOrderLeft);
  BT.right = makeTree(preOrderRight, inOrderRight);

  return BT;
}

let preorderlist = [];

// 先序遍历
function PreOderTraversal(bintree) {
  if (bintree) {
    preorderlist.push(bintree.data);
    if (bintree.left) PreOderTraversal(bintree.left);
    if (bintree.right) PreOderTraversal(bintree.right);
  }
}

let inorderlist = [];
// 中序遍历
function InOderTraversal(bintree) {
  if (bintree) {
    if (bintree.left) InOderTraversal(bintree.left);
    inorderlist.push(bintree.data);
    if (bintree.right) InOderTraversal(bintree.right);
  }
}

const preorder = [4, 3, 8, 9, 10, 5, 7, 11, 2, 6, 15, 1, 16, 20];
const inorder = [9, 8, 10, 3, 7, 5, 11, 4, 15, 6, 2, 16, 1, 20];

const tree = makeTree(preorder, inorder);
PreOderTraversal(tree);
InOderTraversal(tree);

console.log('preorder:\t', preorder);
console.log('tree preorder:\t', preorderlist);

console.log('inorder:\t', inorder);
console.log('tree inorder:\t', inorderlist);

/*
preorder:        [ 4, 3, 8, 9, 10, 5, 7, 11, 2, 6, 15, 1, 16, 20 ]
tree preorder:   [ 4, 3, 8, 9, 10, 5, 7, 11, 2, 6, 15, 1, 16, 20 ]
inorder:         [ 9, 8, 10, 3, 7, 5, 11, 4, 15, 6, 2, 16, 1, 20 ]
tree inorder:    [ 9, 8, 10, 3, 7, 5, 11, 4, 15, 6, 2, 16, 1, 20 ]
*/
上次更新: 8/7/2020, 1:07:53 AM