目錄
一、二叉搜尋樹的概念
1、什麼是二叉搜尋樹?
2、二叉搜尋樹的操作
二、二叉搜尋樹的實作
1、建立二叉搜尋樹 向樹種插入資料
2、周遊二叉搜尋樹
1）先序周遊
2)中序周遊
3）後序周遊
一、二叉搜尋樹的概念
1、什麼是二叉搜尋樹?
二叉搜尋樹（BST，Binary Search Tree），也稱二叉排序樹或二叉查找樹
二叉搜尋樹是一顆二叉樹, 可以為空；如果不為空，滿足以下性質：
- 非空左子樹的所有鍵值小于其根結點的鍵值。
- 非空右子樹的所有鍵值大于其根結點的鍵值。
- 左、右子樹本身也都是二叉搜尋樹。
二叉搜尋樹的特點:
- 二叉搜尋樹的特點就是相對較小的值總是儲存在左結點上, 相對較大的值總是儲存在右結點上.
- 那麼利用這個特點, 我們可以做什麼事情呢?
- 查找效率非常高, 這也是二叉搜尋樹中, 搜尋的來源.
2、二叉搜尋樹的操作
- `insert(key)`：向樹中插入一個新的鍵。
- `search(key)`：在樹中查找一個鍵，如果結點存在，則傳回`true`；如果不存在，則傳回`false`。
- `preOrderTraverse`：通過先序周遊方式周遊所有結點。
- `inOrderTraverse`：通過中序周遊方式周遊所有結點。
- `postOrderTraverse`：通過後序周遊方式周遊所有結點。
- `min`：傳回樹中最小的值/鍵。
- `max`：傳回樹中最大的值/鍵。
- `remove(key)`：從樹中移除某個鍵。
二、二叉搜尋樹的實作
1、建立二叉搜尋樹 向樹種插入資料
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)
}
}
}
}
2、周遊二叉搜尋樹
1）先序周遊
周遊過程為：
- ①通路根結點；
- ②先序周遊其左子樹；
- ③先序周遊其右子樹。
資料結構——二叉樹搜尋樹（二叉搜尋樹的概念、實作、先序周遊、中序周遊、後序周遊）一、二叉搜尋樹的概念二、二叉搜尋樹的實作
2)中序周遊
周遊過程為:
- ①中序周遊其左子樹；
- ②通路根結點；
- ③中序周遊其右子樹。
資料結構——二叉樹搜尋樹（二叉搜尋樹的概念、實作、先序周遊、中序周遊、後序周遊）一、二叉搜尋樹的概念二、二叉搜尋樹的實作
3）後序周遊
周遊過程為：
- ①後序周遊其左子樹；
- ②後序周遊其右子樹；
- ③通路根結點。
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());