二叉树构造和遍历

客官°小女子只卖身不卖艺 2022-05-28 07:05 156阅读 0赞

今天又看了一遍树的操作，发现二叉树的先序遍历，中序遍历，后序遍历的原理竟然如此简单。虽然以前也会，但是今天找到了更简单的方法。  
温故而知新，很好。

/** * Created by BiuBiu_Jiao on 2018/3/31. */
     //声明一个节点
    function Node(data, left, right) { 
        this.data = data;
        this.left = left;
        this.right = right;
        this.show = show;
    }
    
    function show() { 
        return this.data;
    }
    //声明一个二叉树的构造函数
    function BST() { 
        this.root = null;
        this.inSert = inSert;
        this.inOrder = inOrder;
        this.inOrderList = [];
        this.preOrder = preOrder;
        this.preOrderList = [];
        this.afterOrder = afterOrder;
        this.afterOrderList = [];
        this.generateTree = generateTree;
    }
    //将一个数组，快速生成二叉树
    function generateTree(array) { 
        if(Array.isArray(array)){
            for(let item of array){
                this.inSert(item);
            }
        }
    }
    //插入节点
    function inSert(data) { 
        var n = new Node(data,null,null);
        if(this.root == null){
            this.root = n;
        }else{
            //用两个变量存储root对象的指针，很灵活
            var current = this.root;
            var parent;
            while (true){
                parent = current;
                if(data < current.data){
                    current = current.left;
                    if(current == null){
                        parent.left = n;
                        break;
                    }
                    //否则叶子节点就是父节点，在下一次循环的时候
                }else if(data > current.data){
                    current = current.right;
                    if(current == null){
                        parent.right = n;
                        break;
                    }
                }else{
                    //如果相等，就跳出循环
                    break;
                }
            }
        }
    }
    //中序遍历
    var inOrderList = [];
    function inOrder(node,that) { 
        if(node !== null){
            inOrder(node.left,that);
            // console.log(node.show()+" ");
            that.inOrderList.push(node.show());
            inOrder(node.right,that);
        }
    }
    
    //前（先）序遍历
    function preOrder(node,that) { 
        if(!(node == null)){
            // console.log(node.show() + " ");
            that.preOrderList.push(node.show());
            preOrder(node.left,that);
            preOrder(node.right,that);
        }
    }
    
    //后序遍历
    function afterOrder(node,that) { 
        if(!(node == null)){
            afterOrder(node.left,that);
            afterOrder(node.right,that);
            that.afterOrderList.push(node.show());
            // console.log(node.show() + " ");
        }
    }
    
    var bst = new BST();
    
    let array = [23,45,16,37,3,99,22];
    array = [56,22,30,10,81,77,92];
    bst.generateTree(array);
    
    
    
    bst.inOrder(bst.root,bst);
    console.log("inOrderList",bst.inOrderList.toString());
    bst.preOrder(bst.root,bst);
    console.log("preOrderList",bst.preOrderList.toString());
    bst.afterOrder(bst.root,bst);
    console.log("afterOrderList",bst.afterOrderList.toString());

结果：

inOrderList 10,22,30,56,77,81,92
    preOrderList 56,22,10,30,81,77,92
    afterOrderList 10,30,22,77,92,81,56

--------------------

**现在我们说说，温故知新的新，究竟新在哪里？**  
在此之前，我们要深刻理解，递归到底是什么。  
如果你有兴趣的话，不妨再了解一下递归和迭代的区别。  
先序遍历  
我们可以看到的是，打印节点的语句在最前面，所以这叫先序遍历。  
以此类推，中序遍历、后序遍历其实都有类似的结论。  
中序遍历，将打印当前节点的语句，放在中间。  
后序遍历，将打印当前节点的语句，放在最后。

//前（先）序遍历
    function preOrder(node,that) {
        if(!(node == null)){
            // console.log(node.show() + " ");
            that.preOrderList.push(node.show());
            preOrder(node.left,that);
            preOrder(node.right,that);
        }
    }

PS：为什么要传指针进去？  
因为这是递归调用，当在函数中自己调用自己的时候，没有声明这个方法是谁的（没有用obj.method的方式调用）。因此我们需要将指针传进去。

为什么不适用arguments.callee？  
他并不能保证指针的指向是相同的。

--------------------