目录
二叉搜索树(BST,Binary Search Tree),也称二叉排序树或二叉查找树
二叉搜索树是一颗二叉树, 可以为空;如果不为空,满足以下性质:
- 非空左子树的所有键值小于其根结点的键值。
- 非空右子树的所有键值大于其根结点的键值。
- 左、右子树本身也都是二叉搜索树。
二叉搜索树的特点:
- 二叉搜索树的特点就是相对较小的值总是保存在左结点上, 相对较大的值总是保存在右结点上.
- 那么利用这个特点, 我们可以做什么事情呢?
- 查找效率非常高, 这也是二叉搜索树中, 搜索的来源.
- `insert(key)`:向树中插入一个新的键。
- `search(key)`:在树中查找一个键,如果结点存在,则返回`true`;如果不存在,则返回`false`。
- `preOrderTraverse`:通过先序遍历方式遍历所有结点。
- `inOrderTraverse`:通过中序遍历方式遍历所有结点。
- `postOrderTraverse`:通过后序遍历方式遍历所有结点。
- `min`:返回树中最小的值/键。
- `max`:返回树中最大的值/键。
- `remove(key)`:从树中移除某个键。
- class Node {
- constructor(data) {
- this.left = null;
- this.data = data;
- this.right = null;
- }
- }
- class BST {
- constructor() {
- this.root = null;
- }
- insert(ele) {
- // 创建新节点
- let newnode = new Node(ele);
- // console.log(newnode);
- if (this.root == null) { // 空树
- this.root = newnode
- } else {
- this.insertNode(this.root, newnode)
- }
- }
- insertNode(root, newnode) {
- if (newnode.data < root.data) { // 放左边
- if (root.left == null) {
- root.left = newnode
- } else {
- this.insertNode(root.left, newnode)
- }
- } else { //放右边
- if (root.right == null) {
- root.right = newnode
- } else {
- this.insertNode(root.right, newnode)
- }
- }
- }
- }
遍历过程为:
- ①访问根结点;
- ②先序遍历其左子树;
- ③先序遍历其右子树。
遍历过程为:
- ①中序遍历其左子树;
- ②访问根结点;
- ③中序遍历其右子树。
遍历过程为:
- ①后序遍历其左子树;
- ②后序遍历其右子树;
- ③访问根结点。
- class Node {
- constructor(data) {
- this.left = null;
- this.data = data;
- this.right = null;
- }
- }
- class BST {
- constructor() {
- this.root = null;
- }
- insert(ele) {
- // 创建新节点
- let newnode = new Node(ele);
- // console.log(newnode);
- if (this.root == null) { // 空树
- this.root = newnode
- } else {
- this.insertNode(this.root, newnode)
- }
- }
- insertNode(root, newnode) {
- if (newnode.data < root.data) { // 放左边
- if (root.left == null) {
- root.left = newnode
- } else {
- this.insertNode(root.left, newnode)
- }
- } else { //放右边
- if (root.right == null) {
- root.right = newnode
- } else {
- this.insertNode(root.right, newnode)
- }
- }
-
- }
- // 前序遍历
- preOrderTraversal() {
- this.preOrderTraversalNode(this.root)
- }
- preOrderTraversalNode(root) {
- if (root != null) { // {left:node,data:11,right:node} != null
- // 1.根
- console.log(root.data); //11 7 15
- // 2.前序遍历左子树
- this.preOrderTraversalNode(root.left)
- // 3.前序遍历右子树
- this.preOrderTraversalNode(root.right)
- }
- }
- // 中序遍历
- inOrderTraversal(){
- this.inOrderTraversalNode(this.root)
- }
- inOrderTraversalNode(root){
- if(root !=null){
- // 1.中序遍历左子树
- this.inOrderTraversalNode(root.left)
- // 2.根
- console.log(root.data);
- // 3.中序遍历右子树
- this.inOrderTraversalNode(root.right)
- }
- }
- // 后序遍历
- postOrderTraversal(){
- this.postOrderTraversalNode(this.root)
- }
- postOrderTraversalNode(root){
- if(root !=null){
- // 1.后序遍历左子树
- this.postOrderTraversalNode(root.left)
-
- // 2.后序遍历右子树
- this.postOrderTraversalNode(root.right)
- // 3.根
- console.log(root.data);
- }
- }
- }
- let bst = new BST();
- bst.insert(11)
- bst.insert(7)
- bst.insert(15)
- bst.insert(5)
- 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)
- console.log(bst.postOrderTraversal());