首页 > 代码库 > javascript - 二叉树

javascript - 二叉树

都是些简单的东西,所以直接上代码了。

/** * Created by huangjacky on 14-10-3. */function Node(element, left, right) {    this.element = element;    this.level = 0;    this.left = left;    this.right = right;}function BST() {    this.root = null;}BST.prototype = {    insert: function (element) {        var n = new Node(element, null, null);        if (this.root == null) {            this.root = n;            n.level = 0;            return true;        } else {            var current = this.root;            var parent = null;            while (current != null) {                if (element < current.element) {                    parent = current;                    current = current.left;                } else if (element > current.element) {                    parent = current;                    current = current.right;                } else {                    return false;                }            }            n.level = parent.level + 1;            if (element < parent.element) {                parent.left = n;            } else {                parent.right = n;            }            return true;        }    }, toString: function () {        return this.inOrder(this.root, function (n) {            return "\t" + n.element + ‘(‘ + n.level + ")\t";        });    }, inOrder: function (n, fn) {// 中序遍历        if (!n) {            return ‘‘;        } else {            return this.inOrder(n.left, fn) + fn(n) + this.inOrder(n.right, fn);        }    }, preOrder: function (n, fn) { // 先序遍历        if (!n) {            return ‘‘;        } else {            return fn(n) + this.preOrder(n.left, fn) + this.preOrder(n.right, fn);        }    }, postOrder: function (n, fn) {// 后序遍历        if (!n) {            return ‘‘;        } else {            return this.postOrder(n.left, fn) + this.postOrder(n.right, fn) + fn(n);        }    }};var a = new BST();a.insert(3);a.insert(1);a.insert(5);a.insert(2);a.insert(4);console.log("inorder: " + a.toString());var fn = function (n) {    return "\t" + n.element + ‘(‘ + n.level + ")\t";};var s1 = a.preOrder(a.root, fn);var s2 = a.postOrder(a.root, fn);console.log("pre order:" + s1);console.log("post order:" + s2);

 

javascript - 二叉树