二叉树的先中后序遍历

二叉树:每个节点最多只有两个字节点

JS中通常用 Object来模拟二叉树

(val: 1, left: 0, right: 0)



   const bt = {




       val: 1,




       left: {




           val: 2,




           left: {




               val: 4,




               left: null,




               right: null,




           },




           right: {




               val: 5,




               left: null,




               right: null,




           },




       },




       right: {




           val: 3,




           left: {




               val: 6,




               left: null,




               right: null,




           },




           right: {




               val: 7,




               left: null,




               right: null,




           },




       },




   };

先序遍历算法(preorder)「根左右」

1:访问根节点

2:对根节点的左子树进行先序遍历

3:对根节点的右子树进行先序遍历

递归遍历

 非递归(利用栈)

const preorder = (root) => {
     if (!root) { return; }
     const stack = [root];
     while (stack.length) {
         const n = stack.pop();
         console.log(n.val);
         if (n.right) stack.push(n.right);
         if (n.left) stack.push(n.left);
     }
 };

preorder(bt);

中序遍历算法(inorder): 「左根右」

1:对根节点的左子树进行中序遍历

2:访问根节点

3:对根节点的右了树进行中序遍历

const inorder = (root) => {




          if (!root) { return; }




          const stack = [];




          let p = root;




          while (stack.length || p) {




              while (p) {




                  stack.push(p);




                  p = p.left;




              }




              const n = stack.pop();




              console.log(n.val);




              p = n.right;




          }




      };

inorder(bt);

 后序遍历算法(postorder):「左右根」

1:对根节点的左子树进行后序遍历

2:对根节点的右子树进行后序遍历

3:访问根节点

const postorder = (root) => {
     if (!root) { return; }
     const outputStack = [];
     const stack = [root];
     while (stack.length) {
         const n = stack.pop();
         outputStack.push(n);
         if (n.left) stack.push(n.left);
         if (n.right) stack.push(n.right);
     }
     while(outputStack.length){
        const n = outputStack.pop();
         console.log(n.val);
    }
 };

postorder(bt);