二叉树的遍历
线性数据结构遍历比较简单，可以采用正序遍历、逆序遍历。
遍历树的目的一般是修改树，比如修改树的节点，采用访问者模式
前序遍历
前序遍历（preorder traversal）：先访问根节点，前序遍历左子树，前序遍历右子树；遍历 dom 树可以使用
perorderTraversal(visitor) { if (visitor == null) return; const traversal = (node) => { if (node === null) return; visitor.visit(node); traversal(node.left); traversal(node.right); }; traversal(this.root); }
中序遍历
中序遍历（inorder traversal）：中序遍历左子树，根节点，中序遍历右子树；可以顺序打印数据
inorderTraversal(visitor) { if (visitor == null) return; const traversal = (node) => { if (node === null) return; traversal(node.left); visitor.visit(node); traversal(node.right); }; traversal(this.root); }
后序遍历
后序遍历（postorder traversal）：后序遍历左子树，后续遍历右子树，根节点；遍历子节点可使用后序遍历
postorderTraversal(visitor) { if (visitor == null) return; const traversal = (node) => { if (node === null) return; traversal(node.left); traversal(node.right); visitor.visit(node); }; traversal(this.root); }
层序遍历
层序遍历（level order traversal）：从上到下，从左到右依次访问每一个节点
完整代码
实现如下：
// 节点 class Node { constructor(element, parent) { this.element = element; // 存的数据 this.parent = parent; // 父节点 this.left = null; // 左子树 this.right = null; // 右子树 } } class BST { constructor(compare) { this.root = null; this.size = 0; // 节点个数 this.compare = compare || this.compare; } compare(e1, e2) { return e1 - e2; } // 添加节点 add(element) { // 如果根元素不存在 if (this.root === null) { this.root = new Node(element, null); this.size++; return; } else { // 如果根元素存在，那么增加的就不是根节点，需要找到 parent let currentNode = this.root; // 当前比较的结果 let compare = 0; // 先找到需要对比的 parent（当前父节点） let parent = null; while (currentNode) { parent = currentNode; compare = this.compare(element, currentNode.element); // 如果大于 0 找右树，小于 0 找左树 if (compare > 0) { currentNode = currentNode.right; } else if (compare < 0) { currentNode = currentNode.left; } else { // 如果比较后结果一样，由自己决定是否需要覆盖 currentNode.element = element; // 覆盖 return; } } // 找到了 parent，生成新节点 let newNode = new Node(element, parent); if (compare > 0) { parent.right = newNode; } else { parent.left = newNode; } } } // 先序遍历 perorderTraversal(visitor) { if (visitor == null) return; const traversal = (node) => { if (node === null) return; visitor.visit(node); traversal(node.left); traversal(node.right); }; traversal(this.root); } // 中序遍历 inorderTraversal(visitor) { if (visitor == null) return; const traversal = (node) => { if (node === null) return; traversal(node.left); visitor.visit(node); traversal(node.right); }; traversal(this.root); } // 后序遍历 postorderTraversal(visitor) { if (visitor == null) return; const traversal = (node) => { if (node === null) return; traversal(node.left); traversal(node.right); visitor.visit(node); }; traversal(this.root); } } let bst = new BST(); let arr = [10, 8, 19, 6, 15, 22, 20]; arr.forEach((element) => { bst.add(element); }); // 遍历树的目的一般是修改树，比如修改树的节点，采用访问者模式 console.log( bst.perorderTraversal({ visit(node) { console.log("visitor.visit---->", node.element); }, }) ); console.log( bst.inorderTraversal({ visit(node) { console.log("visitor.visit---->", node.element); }, }) ); console.log( bst.postorderTraversal({ visit(node) { console.log("visitor.visit---->", node.element); }, }) );
