二叉树的遍历， 排序， 查找

[h476564406]

一. 二叉树的遍历

e.g. (a+b*c)-(d/e)

var tree = {
    value: "-",
    left: {
        value: '+',
        left: {
            value: 'a',
        },
        right: {
            value: '*',
            left: {
                value: 'b',
            },
            right: {
                value: 'c',
            }
        }
    },
    right: {
        value: '/',
        left: {
            value: 'd',
        },
        right: {
            value: 'e',
        }
    }
};

1. 前序遍历（深度遍历）

用来显示目录结构。 value => left => right

(function () {
    var arr = [];
    var rec = function (node) {
        if (node) {
            arr.push(node.value);
            rec(node.left);
            rec(node.right);
        }
    }
    rec(tree);
    console.log(arr);
    // [ '-', '+', 'a', '*', 'b', 'c', '/', 'd', 'e']
})();

2. 中序遍历
   用来显示表达式树， 从小到大排序。left => value => right

(function () {
    var arr = [];
    var rec = function (node) {
        if (node) {
            rec(node.left);
            arr.push(node.value);
            rec(node.right);
        }
    }
    rec(tree);
    console.log(arr);
    //[ 'a', '+', 'b', '*', 'c', '-', 'd', '/', 'e' ]
})();

3. 后序遍历

(function () {
    var arr = [];
    var rec = function (node) {
        if (node) {
            rec(node.left);
            rec(node.right);
            arr.push(node.value);
        }
    }
    rec(tree);
    console.log(arr);
    //  ["a", "b", "c", "*", "+", "d", "e", "/", "-"]
})();

4. 反转二叉树

(function () {
    function invertTree(node) {
        if (node === undefined) {
            return null;
        }
        node.left = invertTree(node.left);
        node.right = invertTree(node.right);

        const temp = node.left;
        node.left = node.right;
        node.right = temp;

        return node;
    }
    console.log(invertTree(tree));
})();

二. 二叉树的排序和查找

[3， 1， 6， 4， 7]
排序完毕后，

function BinaryTree(nodes) {
    this.initialNodes = nodes;
    this.tree = null;
    this.generateTree();
}

BinaryTree.prototype = {
    generateTree() {
        this.initialNodes.forEach(function (value, index) {
            if (this.tree === null) {
                this.tree = this.generateNode(value, index);
            } else {
                this.insertNode(this.tree, this.generateNode(value, index));
            }
            // 如果不传入this， foreach中的this指向Window
        }, this);
    },

    generateNode(value, index) {
        return {
            value,
            index,
            left: null,
            right: null,
        }
    },

    insertNode(node, newNode) {
        if (newNode.value < node.value) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    },

    max() {
        const tree = this.tree;
        while (tree.right !== null) {
            tree = tree.right;
        }
        return tree.value;
    },

    min() {
        const tree = this.tree;
        while (tree.left !== null) {
            tree = tree.left;
        }
        return tree.value;
    },

    sort() {
        const nodes = [];

        function rec(node) {
            if (node) {
                rec(node.left);
                nodes.push(node.value);
                rec(node.right);
            }
        }
        rec(this.tree);

        return nodes;
    },

    invertTree(node = this.tree) {
        if (node === null) {
            return null;
        }
        node.left = this.invertTree(node.left);
        node.right = this.invertTree(node.right);

        [node.left, node.right] = [node.right, node.left]

        return node;
    },

    searchNode(target, node = this.tree) {
        if (node !== null) {
            if (node.value === target) {
                return node;
            }
            if (node.value > target) {
                return this.searchNode(target, node.left);
            } else {
                return this.searchNode(target, node.right);
            }
        }

        return false;
    },
}
const nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13];
const binary = new BinaryTree(nodes);
console.log(binary.tree);
console.log(binary.sort());
console.log(binary.searchNode(10));