数据结构与算法--二叉树

一、二叉树相关简介

树是一种非线性的数据结构，以分层的方式存储数据；
树由一组以边连接的节点组成；
树最上面的节点称为根节点；
如果一个节点下面有子节点，则称为父节点；
没有任何子节点的节点称为叶子节点；
二叉树的子节点不超过两个；
一个父节点的两个子节点分别称为左节点和右节点；
二叉查找树：是一种特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点中；

二、实现二叉查找树

a. 实现算法

1. 设根节点为当前节点
2. 如果待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点；反之执行第4步
3. 如果当前节点的左节点为null，就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环
4. 设新的当前节点为原节点的右节点
5. 如果当前节点的右节点为null，就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环

b. 遍历二叉查找树的几种方法
先序：根节点 => 左子树 => 右子树
中序：左子树 => 根节点 => 右子树
后序：左子树 => 右子树 => 根节点
分层遍历：根节点 => 子节点，左子树 => 右子树

c. 二叉树进行查找
查找给定值（算法：需要比较该值和当前节点的值的大小，通过比较，就能确定如果给定值不在当前节点时，该向左遍历还是向右遍历）
查找最大值（算法：因为较大的值在右边树上，只需要遍历右子树）
查找最小值（算法：因为较小的值在左边树上，只需要遍历左子树）

d. 二叉查找树删除节点
1.要删除的节点没有子节点
2.要删除的节点有子节点 => 递归操作
删除算法：

1. 判断当前节点是否包含要删除的节点，如果包含，删除该节点，如果不包含，比较当前节点数据和要删除的节点数据的大小
2. 如果待删除数据小于当前节点数据，则移至当前节点的左节点继续比较
3. 如果待删除数据大于当前节点数据，则移至当前节点的右节点继续比较
4. 如果待删除节点时叶子节点，只需要将从父节点指向它的链接指向null
5. 如果待删除节点包含一个子节点，那么原本指向它的节点就得做些调整，使其指向它的子节点

实现二叉查找树类：

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; //根节点
        this.showData = '';
    }
    //向树中加入新节点
    insert (data) {
        let node = new Node(data, null, null);
        if (this.root === null) {
            this.root = node;
        } else {
            let current = this.root;
            let parent = null;
            while (true) {
                parent = current;
                if (data < current.data) {
                    current = current.left;
                    if (current === null) {
                        parent.left = node;
                        break;
                    }
                } else {
                    current = current.right;
                    if (current === null) {
                        parent.right = node;
                        break;
                    }
                }
            }
        }
    } 
    //先序
    preOrder (node) {
        if (!(node == null)) {
            this.showData += node.show() + ' ';
            this.preOrder(node.left);
            this.preOrder(node.right);
        }
    }
    //中序
    inOrder (node) {
        if (!(node == null)) {
            this.inOrder(node.left);
            this.showData += node.show() + ' ';
            this.inOrder(node.right);
        }
    } 
    //后序
    postOrder (node) {
        if (!(node == null)) {
            this.postOrder(node.left);
            this.postOrder(node.right);
            this.showData += node.show() + ' ';
        }
    }
    //分层遍历
    layerOrder (node) {
        let arr = [];
        arr.push(node);
        while (arr.length) {
            let parentNode = arr.pop;
            this.showData += parentNode.show() + ' ';
            if (parentNode.right !== null) {
                arr.push(parentNode.right);
            }
            if (parentNode.left !== null) {
                arr.push(parentNode.left);
            }
        }
    }
    //查找最小值
    getMin () {
        let current = this.root;
        while (current.left !== null) {
            current = current.left;
        }
        return current.data;
    }
    //查找最大值
    getMax () {
        let current = this.root;
        while (current.right !== null) {
            current = current.right;
        }
        return current.data;
    }
    //查找指定值
    find (data) {
        let current = this.root;
        while (current !== null) {
            if (current.data === data) {
                return current;
            } else if (data < current.left) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return null;
    }
    
    remove (data) {
        return this.removeNode(this.root, data);
    }
    //删除节点
    removeNode (node, data) {
        if (node === null) {
            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.getSmallest(node.right);
            node.data = tempNode.data;
            node.right = removeNode(node.right, tempNode.data);
            return node;
        } else if (data < node.data) {
            node.left = removeNode(node.left, data);
            return node;
        } else {
            node.right = removeNode(node.right, data);
            return node;
        }
    }
    //查找左边最小节点
    getSmallest (node) {
        let current = node;
        while (current.left !== null) {
            current = current.left;
        }
        return current;
    }
    
 }


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);
// nums.inOrder(nums.root);    // 3 16 22 23 37 45 99
// nums.preOrder(nums.root);   //23 16 3 22 45 37 99
nums.postOrder(nums.root);     //3 22 16 37 99 45 23
var min = nums.getMin();       //3
var findValue = nums.find(99); //{data: 99, left: null, right: null}