TS数据结构与算法之二叉查找树的遍历

如果对线性数据进行拓展，为数据结点连接多项，那么就可以得到一种新的数据结构。这种新的数据结构就像树一样，它有一个根，然后发散出了枝条和叶子，并且相互连接在一起。这种新的数据结构就称为树。自然界中的树和计算机科学中的树之间的区别在于树数据结构的根在顶部，叶在底部。树在计算机科学的许多领域中使用，包括操作系统，图形，数据库和计算机网络等。树数据结构简称为树。

二叉树（Binary Tree）

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

数据类型：

export interface TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;
}

二叉树的遍历

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

        A
      /   \
    B      C
   / \     /\
  D   E   F  G

前序： ABDECFG
中序： DBEAFCG
后序： DEBFGCA

代码演示

const tree: TreeNode = {
  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,
    },
  },
};

// 二叉树前序遍历
export function preOrderTraverse(
  node: TreeNode | null,
  callback: (n: number) => void
) {
  if (!node) return null;
  callback(node.value);
  preOrderTraverse(node.left, callback);
  preOrderTraverse(node.right, callback);
}

// 二叉树中序遍历
export function inOrderTraverse(
  node: TreeNode | null,
  callback: (n: number) => void
) {
  if (!node) return null;
  inOrderTraverse(node.left, callback);
  callback(node.value);
  inOrderTraverse(node.right, callback);
}

// 二叉树后序遍历
export function postOrderTraverse(
  node: TreeNode | null,
  callback: (n: number) => void
) {
  if (!node) return null;
  postOrderTraverse(node.left, callback);
  postOrderTraverse(node.right, callback);
  callback(node.value);
}

功能测试

// 功能测试
export function binaryTraverseFunctionalTest() {
  const arr: number[] = [];
  // preOrderTraverse(tree, (n) => arr.push(n)); // [5, 3, 2, 4, 7, 6, 8]
  inOrderTraverse(tree, (n) => arr.push(n)); // [2, 3, 4, 5, 6, 7, 8]
  // postOrderTraverse(tree, (n) => arr.push(n));  //  [2, 4, 3, 6, 8, 7, 5]
  console.log('arr', arr);
}

单元测试

文件： tests/binary-tree-iterator.test.ts

import {
  TreeNode,
  preOrderTraverse,
  inOrderTraverse,
  postOrderTraverse,
} from '../src/utils/binary-tree-iterator';

describe('二叉树遍历单元测试', () => {
  const tree: TreeNode = {
    value: 5,
    left: {
      //... 省略
    }
  };

  test('前序遍历', () => {
    const arr: number[] = [];
    preOrderTraverse(tree, (n: number) => {
      arr.push(n);
    });

    expect(arr).toEqual([5, 3, 2, 4, 7, 6, 8]);
  });

  test('中序遍历', () => {
    const arr: number[] = [];
    inOrderTraverse(tree, (n: number) => {
      arr.push(n);
    });

    expect(arr).toEqual([2, 3, 4, 5, 6, 7, 8]);
  });

  test('后序遍历', () => {
    const arr: number[] = [];
    postOrderTraverse(tree, (n: number) => {
      arr.push(n);
    });

    expect(arr).toEqual([2, 4, 3, 6, 8, 7, 5]);
  });
});

执行：

 PASS  tests/binary-tree-iterator.test.ts
  二叉树遍历单元测试
    √ 前序遍历 (2 ms)
    √ 中序遍历
    √ 后序遍历