Tree

一、什么是树？

1.树有什么特点，什么是二叉树和二叉搜索树？

特点：一个树结构包含一系列存在父子关系的节点，每个节点都有一个父节点（根节点除外），或者0到多个子节点。

二叉树：二叉树中的节点最多有2个子节点

二叉搜索树：一种特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点中。

2.生活中常见的例子有哪些？

网盘文件夹树结构

二、请实现二叉搜索树（BST），并实现以下方法：

• insert(key)：向树中插入一个新的键；
• search(key)：树中查找一个键，如果节点存在返回true，不存在返回false；
• min()：返回树中最小的值/键；
• max()：返回树中最大的值/键；

• remove(key)：移除某个键；

• 􏳗 inOrderTraverse􏰞􏶣􏱖中序遍历方式遍历􏰼􏱨􏰳􏰊􏰦

• 􏳗 preOrderTraverse􏰞􏶣􏱖先序遍历方式遍历􏰼􏱨􏰳􏰊􏰦
• 􏳗 postOrderTraverse􏰞􏶣􏱖􏱘后序遍历方式遍历􏰼􏱨􏰳􏰊􏰦

function Node(key) {
    this.key = key;
    this.left = null;
    this.right = null;
};
class BinarySearchTree {
    constructor() {
        this.root = null;
    }
    //插入节点辅助函数
    insertNode(node, newNode) {
        if (node.key > newNode.key) {
            if (node.left == null) {
                node.left = newNode
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right == null) {
                node.right = newNode
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }

    //中序辅助函数
    inOrderTraverseNode(node, cb = function (node) { console.log(node) }) {
        if (node != null) {
            this.inOrderTraverseNode(node.left);
            cb(node);
            this.inOrderTraverseNode(node.right);
        }
    }
    //先序辅助函数
    preOrderTraverseNode(node, cb = function (node) { console.log(node) }) {
        if (node != null) {
            cb(node);
            this.preOrderTraverseNode(node.left);
            this.preOrderTraverseNode(node.right);
        }
    }
    //后序辅助函数
    postOrderTraverseNode(node, cb = function (node) { console.log(node) }) {
        if (node != null) {
            this.postOrderTraverseNode(node.left);
            this.postOrderTraverseNode(node.right);
            cb(node);
        }
    }

    //最大值辅助函数
    getMax(node) {
        if (node) {
            while (node.right) {
                node = node.right;
            }
            return node.key;
        }
        return null;
    }

    //最小值辅助函数
    getMin(node) {
        if (node) {
            while (node.left) {
                node = node.left;
            }
            return node.key;
        }
        return null;
    }

    //搜索辅助函数
    searchNode(node, key) {
        if (node == null) return false;
        if (node.key > key) {
            this.searchNode(node.right, key);
        } else if (node.key < key) {
            this.searchNode(node.left, key);
        } else {
            return true;
        }
    }
    //删除辅助函数
    removeNode(node, key) {
        if (node === null) {
            return null;
        }
        if (key < node.key) {
            node.left = this.removeNode(node.left, key);
            return node;
        } else if (key > node.key) {
            node.right = this.removeNode(node.right, key);
            return node;
        } else {
            if (node.left === null && node.right === null) {
                node = null;
                return node;
            }
            if (node.left === null) {
                node = node.right;
                return node;
            } else if (node.right === null) {
                node = node.left;
                return node;
            }
            var aux = this.findMinNode(node.right);
            node.key = aux.key;
            node.right = this.removeNode(node.right, aux.key);
            return node;
        }
    };

    findMinNode(node) {
        while (node && node.left !== null) {
            node = node.left;
        }
        return node;
    };

    //后序
    postOrderTraverse() {
        this.postOrderTraverseNode(this.root);
    }
    //先序
    preOrderTraverse() {
        this.preOrderTraverseNode(this.root);
    }
    //中序
    inOrderTraverse() {
        this.inOrderTraverseNode(this.root);
    }
    remove(key) {
        this.root = this.removeNode(this.root, key);
    };
    insert(key) {
        var newNode = new Node(key);
        if (this.root === null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }
    search(key) {
        return this.searchNode(this.root, key);
    }
    max() {
        return this.getMax(this.root);
    }
    min() {
        return this.getMin(this.root);
    }
}
let bst = new BinarySearchTree();
bst.insert(11);
bst.insert(7);
bst.insert(15);
bst.insert(5);
bst.insert(6);
bst.insert(3);
bst.insert(9);
bst.insert(8);
bst.insert(10);
bst.insert(13);
bst.insert(12);
bst.insert(14);
bst.insert(20);
bst.insert(18);
bst.insert(25);

DFS 深度优先

先序遍历方式遍历􏰼􏱨􏰳􏰊􏰦：

中序遍历方式遍历􏰼􏱨􏰳􏰊􏰦 （从最小到最大顺序访问所有节点）：

后序遍历方式遍历􏰼􏱨􏰳􏰊􏰦 ：

BFS 广度优先

function TreeNode(val) {
	this.val = val;
	this.left = this.right = null;
}
let root = new TreeNode(1)
let node2 = new TreeNode(2)
let node3 = new TreeNode(3)
let node4 = new TreeNode(4)
let node5 = new TreeNode(5)
let node6 = new TreeNode(6)
let node7 = new TreeNode(7)
root.left = node2
root.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
node3.right = node7



function levelOrder(root) {
	var queue = [root];
	let arr = [];
	while(queue.length){
		const len = queue.length;
		for(let i = 0; i < len; i++){
		    const item = queue.shift();
            arr.push(item.val);
            item.left && (queue.push(item.left));
            item.right && (queue.push(item.right));
		}
	}
	return arr;
}
levelOrder(root);// [1, 2, 3, 4, 5, 6, 7]