树和二叉树

1. 树的基本概念

树和二叉树

如图所示,一棵树最上面的点称为根节点,如果一个节点下面连接多个节点,那么该节点成为父节点,它下面的节点称为子节点,一个节点可以有0个、1个或更多节点,没有子节点的节点叫叶子节点。

1.1 二叉树:

是一种特殊的树,即子节点最多只有两个,这个限制可以使得写出高效的插入、删除、和查找数据。在二叉树中,子节点分别叫左节点和右节点。
树和二叉树

1.2 二叉查找树

二叉查找树是一种特殊的二叉树,相对较小的值保存在左节点中,较大的值保存在右节点中,这一特性使得查找的效率很高,对于数值型和非数值型数据,比如字母和字符串,都是如此。现在通过JavaScript实现一个二叉查找树。

1.3 实现二叉查找树

1.3.1 定义树节点

二叉树的最小元素是节点,所以先定义一个节点

// 定义节点的数据结构
function Node(data, left, right) {
    this.left = left;
    this.right = right;
    this.data = data;
    this.show = () => { return this.data }
}

1.3.2 定义二叉树结构

// 二叉树---构造函数
function BST() {
    this.root = null; //初始化,root为null
    this.insert = insert;  //数据插入方法
}

BST初始化时,只有一个根节点,且没有任何数据。 接下来,我们利用二叉查找树的规则,定义一个插入方法,这个方法的基本思想是:

  1. 如果 BST.root === null ,那么就将节点作为根节点
  2. 如果 BST.root !==null ,将插入节点进行一个比较,小于根节点,拿到左边的节点,否则拿右边,再次比较、递归。

这里就出现了递归了,因为,总是要把较小的放在靠左的分支。

1.3.3 完善节点数据的插入

// 插入数据方法
function insert(data) {
    var node = new Node(data, null, null);
    if (this.root === null) {
        this.root = node
    } else {
        var current = this.root;
        var parent;
        while (true) {
            parent = current;
            if (data < current.data) {
                current = current.left; //到左子树
                if (current === null) {  //如果左子树为空,说明可以将node插入在这里
                    parent.left = node;
                    break;  //跳出while循环
                }
            } else {
                current = current.right;
                if (current === null) {
                    parent.right = node;
                    break;
                }
            }
        }
    }
}

1.3.4 生成二叉树

// 构建二叉树
var bst = new BST();
bst.insert(10);
bst.insert(8);
bst.insert(2);
bst.insert(7);
bst.insert(5);

二叉树结构如图:
树和二叉树

如何查看数据?可能就需要使用二叉树的遍历

1.4 二叉树的遍历

  • 前序遍历 (根左右)
  • 中序遍历 (左根右)
  • 后序遍历 (左右根)

例题:
树和二叉树

JavaScript递归实现:

// 前序遍历
function preOrder(node) {
    if (node !== null) {
        //如果不是null,就一直查找左变,因此递归
        console.log(node.show());
        preOrder(node.left);
        preOrder(node.right);
    }
}
// 中序遍历
function inOrder(node) {
    if (node !== null) {
        //如果不是null,就一直查找左变,因此递归
        inOrder(node.left);
        //递归结束,打印当前值
        console.log(node.show());
        //上一次递归已经把左边搞完了,右边
        inOrder(node.right);
    }
}
// 后序遍历
function postOrder(node) {
    if (node !== null) {
        //如果不是null,就一直查找左变,因此递归
        postOrder(node.left);
        postOrder(node.right);
        console.log(node.show());
    }
}

//在刚才已有bst的基础上执行命令
preOrder(bst.root);  // 10 8 2 7 5 
inOrder(bst.root);  // 2 5 7 8 10 
postOrder(bst.root);  //  5 7 2 8 10

1.5 二叉树的查找

在二叉树这种数据结构中进行数据查找是最方便的,现在我们就对查找最小值、最大值和特定值进行一个梳理:

  • 最小值: 最左子树的叶子节点
  • 最大值: 最右子树的叶子节点
  • 特定值: targetcurrent进行比较,如果比current大,在current.right进行查找,反之类似。

1.5.1 最大、最小值

//最小值
function getMin(bst) {
    var current = bst.root;
    while (current.left !== null) {
        current = current.left;
    }
    return current.data;
}

//最大值
function getMax(bst) {
    var current = bst.root;
    while (current.right !== null) {
        current = current.right;
    }
    return current.data;
}
console.log(getMin(bst));   // 2
console.log(getMax(bst));   // 10

1.5.2 查找特定值

// 查找特定值
function find(target, bst) {
    var current = bst.root;
    while (current !== null) {
        if (target === current.data) {
            return true;
        }
        else if (target > current.data) {
            current = current.right;
        } else if (target < current.data) {
            current = current.left;
        }
    }
    return -1;
}

console.log(find(9, bst));   // -1找不到
console.log(find(8, bst));   // true 在树中
上一篇:jQuery Easyui datagrid 数据表格的使用


下一篇:c# – 排序十进制类型的列? (可为空)在WPF DataGrid中