数据

{
 "value": 1,
 "left": {
 "value": 2,
 "left": {
 "value": 4,
 "left": null,
 "right": null
 },
 "right": {
 "value": 5,
 "left": null,
 "right": null
 }
 },
 "right": {
 "value": 3,
 "left": {
 "value": 6,
 "left": null,
 "right": null
 },
 "right": {
 "value": 7,
 "left": null,
 "right": null
 }
 }
}

遍历二叉树

深度优先遍历(包括前序、中序、后序遍历)

前序

先访问根节点,然后访问左子树,最后访问右子树:

function foreachTree(tree) {
 if(!tree) return
 console.log(tree.value)
 foreachTree(tree.left)
 foreachTree(tree.right)
}

function foreachTree(tree) {
 if(!tree) return
 const stack = [tree];
 while(stack.length> 0) {
 const node = stack.pop();
 console.log(node.value);
 if(node.right) {
 stack.push(node.right);
 }
 if(node.left) {
 stack.push(node.left);
 }
 }
}

中序

先访问左子树,然后访问根节点,最后访问右子树:

function foreachTree(tree) {
 if(!tree) return
 foreachTree(tree.left)
 console.log(tree.value)
 foreachTree(tree.right)
}

function inorderTraversalIterative(root) {
 const stack = [];
 let current = root;
 while (current || stack.length> 0) {
 // 不断将当前节点及其左子节点压入栈中
 while (current) {
 stack.push(current);
 current = current.left;
 }
 // 从栈中弹出一个节点并访问
 current = stack.pop();
 console.log(current.value)
 // 将当前节点更新为弹出节点的右子节点
 current = current.right;
 }
}

后序

先访问左子树,然后访问右子树,最后访问根节点:

function foreachTree(tree) {
 if(!tree) return
 foreachTree(tree.left)
 foreachTree(tree.right)
 console.log(tree.value)
}

function postorderTraversalIterative(root) {
 if (!root) return;
 const stack1 = [root];
 const stack2 = []; // 用于存储反向的结果

 while (stack1.length) {
 const node = stack1.pop();
 stack2.push(node); // 将节点压入辅助栈
 if (node.left) stack1.push(node.left); // 左子节点先入主栈
 if (node.right) stack1.push(node.right); // 右子节点后入主栈
 }

 // 依次输出辅助栈内容(反转)
 while (stack2.length) {
 const node = stack2.pop();
 console.log(node.value); // 访问当前节点
 }
}

广度优先遍历(层级遍历)

按层从上到下依次访问节点。

function breadthFirstTraversal(root) {
 if (!root) return;

 const queue = [root]; // 初始化队列,将根节点放入队列

 while (queue.length> 0) {
 const currentNode = queue.shift(); // 从队列中取出当前节点
 console.log(currentNode.value); // 输出当前节点的值

 // 将当前节点的左子节点和右子节点放入队列
 if (currentNode.left) {
 queue.push(currentNode.left);
 }
 if (currentNode.right) {
 queue.push(currentNode.right);
 }
 }
}