三者介绍

这种遍历方式首先访问树的根节点，然后遍历左子树，最后遍历右子树。‌

类别		描述
先序遍历	NLR、PreOrder	访问根节点：首先访问树的根节点 先序遍历左子树：对左子树进行先序遍历 先序遍历右子树：对右子树进行先序遍历。
中序遍历	LNR、InOrder	‌ 中序遍历左子树：对左子树进行中序遍历 访问根节点：首先访问树的根节点 中序遍历右子树：对右子树进行中序遍历。
后序遍历	RLN、PostOrder	‌ 后序遍历右子树：对右子树进行后序遍历 后序遍历左子树：对左子树进行后序遍历 访问根节点：首先访问树的根节点。

算法实现

1. 假如我们有这么一个二叉树：

2. 先实现这个二叉树

// 首先我们先定义一个 node对象
class node {
  constructor(name, left, right) {
    this.name = name;
    this.left = left;
    this.right = right;
  }
}
let nodeA = new node("A");
let nodeB = new node("B");
let nodeC = new node("C");
let nodeD = new node("D");
let nodeE = new node("E");
let nodeF = new node("F");
let nodeG = new node("G");
let nodeH = new node("H");
let nodeI = new node("I");
let nodeJ = new node("J");
let rootNode = nodeA;
rootNode.left = nodeB;
nodeB.left = nodeD;
nodeD.left = nodeG;
rootNode.right = nodeC;
nodeB.right = nodeE;
nodeD.right = nodeH;
nodeC.right = nodeF;
nodeF.left = nodeI;
nodeF.right = nodeJ;
console.log(rootNode);
// {
//     "name": "A",
//     "left": {
//         "name": "B",
//         "left": {
//             "name": "D",
//             "left": {
//                 "name": "G"
//             },
//             "right": {
//                 "name": "H"
//             }
//         },
//         "right": {
//             "name": "E"
//         }
//     },
//     "right": {
//         "name": "C",
//         "right": {
//             "name": "F",
//             "left": {
//                 "name": "I"
//             },
//             "right": {
//                 "name": "J"
//             }
//         }
//     }
// }

3. 先序遍历 NLR preOrder

• 访问根节点：首先访问树的根节点
• 先序遍历左子树：对左子树进行先序遍历
• 先序遍历右子树：对右子树进行先序遍历

let result = [];
function preOrder(node) {
  // 1. 塞入根节点
  result.push(node.name);
  // 2. 先序遍历左子树
  if (node.left) {
    preOrder(node.left);
  }
  // 3. 先序遍历右子树
  if (node.right) {
    preOrder(node.right);
  }
}
preOrder(rootNode);
console.log(result);
// ['A', 'B', 'D', 'G', 'H', 'E', 'C', 'F', 'I', 'J']

4. 中序遍历 LNR inOrder

• 中序遍历左子树：对左子树进行中序遍历
• 访问根节点：首先访问树的根节点
• 中序遍历右子树：对右子树进行中序遍历

let result = [];
function inOrder(node) {
  // 1. 中序遍历左子树
  if (node.left) {
    inOrder(node.left);
  }
  // 2. 塞入根节点
  result.push(node.name);
  // 3. 中序遍历右子树
  if (node.right) {
    inOrder(node.right);
  }
}
inOrder(rootNode);
console.log(result);
// ['G', 'D', 'H', 'B', 'E', 'A', 'C', 'I', 'F', 'J']

5. 后序遍历 RLN postOrder

• 后序遍历右子树：对右子树进行后序遍历

• 后序遍历左子树：对左子树进行后序遍历

• 访问根节点：首先访问树的根节点。

let result = [];
function postOrder(node) {
  // 1. 后序遍历右子树
  if (node.right) {
    postOrder(node.right);
  }
  // 2. 后序遍历左子树
  if (node.left) {
    postOrder(node.left);
  }
  // 3. 塞入根节点
  result.push(node.name);
}
postOrder(rootNode);
console.log(result);
// ['J', 'I', 'F', 'C', 'E', 'H', 'G', 'D', 'B', 'A']

更新日志

2025/8/24 08:17

查看所有更新日志

• e7112-1于 2025/8/24