树和二叉树

2024-01-12 12:52:46

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

如果 BST.root === null ，那么就将节点作为根节点
如果 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 二叉树的查找

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

最小值：最左子树的叶子节点
最大值：最右子树的叶子节点
特定值： target与current进行比较，如果比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 在树中

码农公寓