文档章节

javascript - 二叉树

huangjacky
 huangjacky
发布于 2014/10/12 12:21
字数 224
阅读 7
收藏 0

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

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

 

本文转载自:http://www.cnblogs.com/huangjacky/p/4005317.html

共有 人打赏支持
huangjacky
粉丝 5
博文 19
码字总数 0
作品 0
深圳
高级程序员
私信 提问
二叉搜索树的简明实现(ES5 & ES6)

二叉树 & 二叉搜索树 二叉树(Binary Tree)是 n(n >= 0)个节点的有限集合,集合为空集时,叫作空二叉树;不为空时,由根节点及左子树、右子树组成,左子树、右子树也都是二叉树。 从这个描...

天方夜
10/30
0
0
JavaScript实现排序二叉树的基本操作

记得一开始学习数据结构用的是c语言实现,学了这么久前端就想用JavaScript来实现一下,顺便复习下数据结构。 先来了解下什么是排序二叉树,排序二叉树是具有以下特点的二叉树 若左子树不空,...

a独家记忆
06/29
0
0
JavaScript专题之递归

JavaScript 专题系列第十八篇,讲解递归和尾递归 定义 程序调用自身的编程技巧称为递归(recursion)。 阶乘 以阶乘为例: 示意图(图片来自 wwww.penjee.com): 斐波那契数列 在《JavaScript专...

冴羽
2017/09/13
0
0
可视化讲解 深度优先遍历(DFT)

可视化讲解 深度优先遍历(DFT) 深度优先遍历, 刷过题的朋友应该都很熟悉了,难是不难,但是理解起来还是要费一些功夫的. 深度优先遍历的实现方法有递归和非递归两种, 这里我们用可视化的角度,...

ssthouse_hust
09/16
0
5
js vis vue 实现AVL树

AVL树,插入和删除节点, 不同的旋转实现 参考 http://blog.csdn.net/zhangxiangdavaid/article/details/37115355 js: 二叉树的三种遍历递归实现与非递归实现,删除采用中序遍历重新创建.....懒...

阿豪boy
2017/11/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

makefile 常用函数

Linux 环境下的程序员如果不会使用GNU make来构建和管理自己的工程,应该不能算是一个合格的专业程序员,至少不能称得上是 Unix程序员。今天我们来学习下makefile的常用函数。 《GNU make》h...

科陆李明
27分钟前
6
0
Android 报错 Could not find com.android.tools.build:aapt2:3.2.1-4818971.

报错信息: Could not find com.android.tools.build:aapt2:3.2.1-4818971.Searched in the following locations: file:/C:/Users/96110/AppData/Local/Android/Sdk/extras/m2reposito......

lanyu96
39分钟前
1
0
我的Linux系统九阴真经

我的Linux系统九阴真经 在今天,互联网的迅猛发展,科技技术也日新月异,各种编程技术也如雨后春笋一样,冒出尖来了。各种创业公司也百花齐放百家争鸣,特别是针对服务行业,新型互联网服务行...

linuxCool
今天
24
0
Python程序员需要知道的30个技巧

1 直接交换两个数字位置 1x, y = 10, 202print(x, y)3x, y = y, x4print(x, y)5#1 (10, 20)6#2 (20, 10) 2 比较运算符的链接 1n = 102result = 1 < n < 203print(result)4# True5result = 1 ......

糖宝lsh
今天
13
0
[LintCode] Linked List Cycle(带环链表)

描述 给定一个链表,判断它是否有环。 样例 给出 -21->10->4->5, tail connects to node index 1,返回 true。 这里解释下,题目的意思,在英文原题中,tail connects to node index 1 表示的...

honeymose
今天
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部