二叉树及其操作

[hubvue]

树的概念及用途

树是一种非线性的数据结构，特点是分层存储数据。树被用来存储具有层级关系的数据，还被用来存储有序列表。

树关键概念定义

1. 树由一组以边连接的节点组成。
2. 一棵树最上面的节点称为根节点,如果一个节点相面连接多个节点,那么该节点称为父节点,它下面的节点被称为子节点.一个节点可以有0个、1个、或多个子节点。没有任何子节点的节点称为叶子节点。
3. 二叉树是一种特殊的树，子节点个数不超过两个。
4. 从一个节点走到另一个节点的者一组边叫做路径。
5. 以某种特定顺序访问树中的所有节点称为树的遍历。
6. 树分为几个层次，根节点是第0层，它的子节点是第1层，以此类推。我们定义树的层数就是树的深度。
7. 每个节点都有一个与之相关的值，该值有时被称为键。
8. 一个父节点的两个子节点分别称为左节点和右节点。二叉查找树是一种特殊的二叉树，相对较小的值保存在左节点，较大的值保存在右节点，者一特性使得查找效率很高。

二叉树

什么是二叉树，一个树最多只有两个子节点，最少有0个子节点，这样的树叫做二叉树。

当一个树的左子节点小于该节点，右子节点大于该节点，这样的树叫做二叉排序树或者叫做二叉搜索树。

二叉搜索树查找特别快，为二叉树添加或删除元素也特别快，把相对较小的值放在左节点，相对较大的值放在右节点。

二叉树的遍历

1. 先序：根左右
2. 中序：左根右
3. 后续：左右根

二叉树的查找

查找最小值

从根节点出发，递归查找左节点，直到找到节点没有左子节点为止，那么此节点的值就是最小值。

查找最大值

从根节点出发，递归查找右节点，直到找到节点没有右子节点为止，那么此节点的值就是最大值。

二叉树的插入

对二叉树插入一个值，从根节点出发与插入值进行比较，当找到最终比较节点，如果比最终比较节点小，则插入到它的左侧，反之插入右侧。

二叉树的删除操作

1. 首先先查找二叉树中是否有该值。
2. 判断节点是否是子节点，是否只有一个节点，是否有两个节点。
3. 当是子节点的时候直接把子节点删除即可。
4. 当只有一个子节点的时候，则需要把节点删除，子节点替换到节点原来的位置。
5. 当有两个子节点的时候，则需要把原节点删除，右子树的节点替换到节点的原来的位置上。

代码实现二叉搜索树

创建一个节点的构造函数，一个show方法显示节点的数据。

class Node{
    constructor(data,left,right){
        this.data = data;
        this.left = left;
        this.right = right;
    }
    show(){
        return this.data;
    }
}

class BST{
    constructor(){
        this.root = null;
    }
    //插入操作
    insert(data){
        let node = new Node(data,null,null);
        if(this.root === null) {
            this.root = node;
        }else{
            let current = this.root;
            while(true){
                if(data > current.data){
                    if(current.right === null) {
                        current.right = node;
                        return node;
                    } else{
                        current = current.right;
                    }
                } else {
                    if(current.left === null) {
                        current.left = node;
                        return node;
                    } else{
                        current = current.left;
                    }
                }
            }
        };
        return false;
    }
    //递归
    //中序遍历
    recInOrder(node){
        // console.log(node);
        if(!(node === null)) {
            this.recInOrder(node.left);
            console.log(node.data);
            this.recInOrder(node.right);
        }
    }
    //先序遍历
    recPreOrder(node){
        if(!(node === null)) {
            console.log(node.data);
            this.recPreOrder(node.left);
            this.recPreOrder(node.right);
        }
    }
    //后序遍历
    recOutOrder(node){
        if(!(node === null)) {
            this.recOutOrder(node.left);
            this.recOutOrder(node.right);
            console.log(node.data);
        }
    }
    //非递归
    //中序
    noRecInOrder(node){
        let stack = [];
        let temp;
        stack.push(node);
        while(stack.length !== 0){
            while((temp = stack[stack.length - 1]) && temp){
                stack.push(temp.left);
            }
            stack.pop();
            if(stack.length !== 0){
                temp = stack.pop();
                console.log(temp.data);
                stack.push(temp.right)
            }
        }
    }
    //先序
    noRecPreOrder(node){
        let stack = [];
        let temp;
        stack.push(node);
        while(stack.length !== 0){
            temp = stack.pop();
            while(temp){
                console.log(temp.data);
                if(temp.right){
                    stack.push(temp.right);
                }
                temp = temp.left;
            }
        }
    }
    //后序
    noRecOutOrder(node){
        let stack = [];
        let temp = node;
        while(temp || stack.length !== 0){
            if(temp){
                stack.push(temp);
                stack.push(temp);
                temp = temp.left
            } else {
                temp = stack.pop();
                if(temp === stack[stack.length - 1]){
                    temp = temp ? temp.right : null;
                } else {
                    console.log(temp.data);
                    temp = null;
                }
            }
        }
    }
    //获取到最小值
    getMin(root){
        let temp = root;
        while(temp.left){
            temp = temp.left;
        }
        return temp;
    }
    //获取到最大值
    getMax(root){
        let temp = root;
        while(temp.right){
            temp = temp.right;
        }
        return temp;
    }
    // 查找特定的值
    find(data){
        let root = this.root;
        while(root){
            if(data === root.data){
                return root.data;
            }else if(data > root.data) {
                root = root.right;
            } else if(data < root.data) {
                root = root.left;
            }
        }
        return false;
    }
    //删除一个节点
    remove(data){
        this.removeNode(this.root,data);
    }
    removeNode(node,data){
        if(!node){
            return null;
        }
        if(data === node.data) {
            if(node.left == null && node.right == null) {
                return null;
            }
            if(node.left == null) {
                return node.right;
            }
            if(node.right == null) {
                return node.left;
            }
            let tempNode = this.getMin(node.right);
            node.data = tempNode.data;
            node.right = this.removeNode(node.right,tempNode.data);
            return node;
        } else if(data < node.data) {
            node.left = this.removeNode(node.left,data);
            return node;
        } else {
            node.right = this.removeNode(node.right,data);
            return node;
        }
    }
}