1 构造一个二叉树

首先用javascript实现一个简单的二叉树构造函数；其实就是一个组织结构；跟我们普通的组织树对象一样，就是个普通对象；无非二叉树更加标准，有左右孩子节点；代码如下

                                            
function TreeCode() {
    let BiTree = function(ele) {
        this.value= ele;
        this.lChild = null;
        this.rChild = null;
    }

    this.createTree = function() {
        let biTree = new BiTree('A');
        biTree.lChild = new BiTree('B');
        biTree.rChild = new BiTree('C');
        biTree.lChild.lChild = new BiTree('D');
        biTree.lChild.lChild.lChild = new BiTree('G');
        biTree.lChild.lChild.rChild = new BiTree('H');
        biTree.rChild.lChild = new BiTree('E');
        biTree.rChild.rChild = new BiTree('F');
        biTree.rChild.lChild.rChild = new BiTree('I');
        return biTree;
    }
}
                                            
                                        

调用

                                            
let myTree = new TreeCode().createTree();
                                            
                                        

这样我们就构建了一个如下图的二叉树

2 方法一:递归

下面通过递归实现DFS深度遍历的先序遍历、中序遍历、和后序遍历

                                            
let preArray=[],middleArray=[],lastArray=[];
    //先序遍历：根、左、右
    function preOrder(root){
        if(root){
            preArray.push(root.value);
            preOrder(root.lChild);
            preOrder(root.rChild);
        }
    }
    //中序遍历：左 根 右   
    function inOrder(root){
            if(root){
                inOrder(root.lChild)
                middleArray.push(root.value);
                inOrder(root.rChild);
            }
    }
    //后序遍历：左 右 根
    function lastOrder(root){
        if(root){
            lastOrder(root.lChild);
            lastOrder(root.rChild);
            lastArray.push(root.value);
        }
    }
    preOrder(myTree);
    inOrder(myTree);
    lastOrder(myTree);
                                            
                                        

测试结果:

3 DFS深度遍历方式

利用栈先进后出，后进先出的特点

                                            
// 先序（中 左  右） 非递归
 function preOrder(root){
        let res=[],
        stack=[root];
        while(stack.length>0){
            let node=stack.pop();
            res.push(node.value);
            if(node.rChild){
                stack.push(node.rChild);
            }
            if(node.lChild){
                stack.push(node.lChild);
            }
 
        }
        return res;
   }
   // 中序 （左 中 右） 非递归
   function middleOrder(root) {
    let res = [];
    let stack = [];
    let node = root;
    while(stack.length !== 0 || node !== null) {
        if(node !== null) {
            stack.push(node);
            node = node.lChild;
        }else {
            node = stack.pop();
            res.push(node.value);
            node = node.rChild;
        }
    }
    return res;
};
   // 后序 (左 右 中) 非递归
   // 先序 中左右=>调换右左，变成中右左，然后反转返回即可
   function lastOrder(root) {
        let res=[],
        stack=[root];
        while(stack.length>0){
            let node=stack.pop();
            res.push(node.value);
            if(node.lChild){
                stack.push(node.lChild);
            }
            if(node.rChild){
                stack.push(node.rChild);
            }
         
        }
        return res.reverse();
    };
                                            
                                        

测试结果与上述是一样的