二叉树与二叉查找树

一、树的相关术语

树是一种非线性的数据结构，以分层的形式存储数据 树由一组以边连接的节点组成，如下：

树的层数被定义为树的深度

二、二叉树

二叉树是一种特殊的树，规定每个节点的子节点不能超过两个 通过将子节点的个数设置为2，可以高效地在树中插入、删除、查找数据 二叉查找树是一种特殊的二叉树，相对较小的值保存在左节点上，较大的值保存在右节点上，这一特性使得查找的效率很高

三、二叉查找树的实现

1、 二叉查找树由节点组成，或者说树都是由节点组成，因此，我们要定义的第一个对象就是Node:

function Node(data){
    this.data = data;   //存储键值
    this.left = left;   //指向左孩子的指针
    this.right = right; //指向右孩子的指针
    this.show = show;   //显示保存在节点中的数据
}
function show(){
    return this.data;
}

2、创建一个类，用来表示二叉查找树（BST）。类中只包含一个数据成员：root（一个用来表示二叉查找树的根节点的Node对象），初始化为null，从而创建一个空节点。

function BST (){
    this.root = null;
}

3、设计一个insert（）方法，用来向树中加入新节点

function BST() {
    this.root = null;
    this.insert = insert;
}

function insert(data) {
    var node = new Node(data,null,null);
    if(this.root == null) {
        this.root = node;
    } else {
        var currentNode = this.root;
        var parent;
        while(true) {
            parent = currentNode;
            if(data < currentNode.data) {
                currentNode = currentNode.left;
                if(currentNode == null) {
                    parent.left = node;
                    break;
                }
            } else {
                currentNode = currentNode.right;
                if(currentNode == null) {
                    parent.left = node;
                    break;
                }
            }
        }
    }
}

4、二叉查找树的遍历

function inOrder(node){
    if( node != null){
        inOrder(node.left);
        console.log(node.show()+' ');
        inOrder(node.right)
    }
}

（2） 先序遍历：先访问根节点，然后以同样的方式访问左子树和右子树

function preOrder(node){
    if(node != null){
        console.log(node.show());
        preOrder(node.left);
        preOrder(node.right)
    }
}

（3） 后序遍历:先访问叶子节点，从左子树到右子树再到根节点

function postOrder(node){
    if(node != null){
        postOrder(node.left);
        postOrder(node.right);
        console.log(node.show());
    }
}

var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);

console.log("inOrder:")
inOrder(nums.root); //3 16  22  23  37  45  99
console.log("preOrder")
preOrder(nums.root); //23 16  3  22  45  37  99
console.log("postOrder")
postOrder(nums.root); //3  22  16  37  99  45  23

四、在二叉查找树上进行查找
1、查找最小值和最大值

function getMin(){
    var node = this.root;
    var parent;
    while(node != null){
        parent = node;
        node = node.left;
    }
    return parent.data;
}

function getMax(){
    var node = this.root;
    var parent;
    while(node != null){
        parent = node;
        node = node.right;
    }
    return parent.data;
}

console.log(nums.getMax());     //99
console.log(nums.getMin());     //3

2、查找给定值

function find(data){
    var node = this.root;
    while(node != null){
        if(node.data == data){
            return node;
        }else if(node.data > data){
            node = node.left;
        }else{
            node = node.right;
        }
    }
    return null;
}

console.log(nums.find("23"));
console.log(nums.find("100"));