二叉树构造和遍历-蒲公英云

二叉树构造和遍历

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

/** * 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);
    }
}