自我測驗
本篇文章的測驗用例及除錯方法見前言
圖
樹的相關術語
根節點: 位于樹頂部的節點叫作根節點
內部節點: 至少有一個子節點的節點稱為內部節點（7、5、9、15、13和20是內部節點）
外部節點(葉節點):沒有子元素的節點稱為外部節點或葉節點（3、6、8、10、12、14、18和25是葉節點）
子樹:由節點和它的后代構成，例如，節點13、12和14構成了上圖中樹的一棵子樹
深度:節點的深度取決于它的祖先節點的數量，比如，節點3有3個祖先節點（5、7和11），它的深度為3
高度:樹的高度取決于所有節點深度的最大值，一棵樹也可以被分解成層級，根節點在第0層，它的子節點在第1層，以此類推，上圖中的樹的高度為3（最大高度已在圖中表示——第3層）
一個節點可以有祖先和后代，一個節點（除了根節點）的祖先包括父節點、祖父節點、曾祖父節點等，一個節點的后代包括子節點、孫子節點、曾孫節點等，例如，節點5的祖先有節點7和節點11，后代有節點3和節點6，
二叉樹和二叉搜索樹
二叉樹中的節點最多只能有兩個子節點：一個是左側子節點，另一個是右側子節點，這些定義有助于我們寫出更高效的向/從樹中插入、查找和洗掉節點的演算法，二叉樹在計算機科學中的應用非常廣泛，
二叉搜索樹（BST）是二叉樹的一種，但是它只允許你在左側節點存盤（比父節點）小的值，在右側節點存盤（比父節點）大（或者等于）的值，上圖中就展現了一棵二叉搜索樹，
圖例
基礎方法
insert(key): 向二叉搜索樹插入一個新的鍵
search(key): 在樹中搜索一個鍵.如果存在該節點,就回傳true;不存在就回傳false
inOrderTraverse():通過中序遍歷的方式遍歷所有節點
preOrderTraverse():通過先序遍歷的方式遍歷所有節點
postOrderTraverse():通過后序遍歷的方式遍歷所有的節點
min():回傳樹中最小的值/鍵
max():回傳樹中最大的值/鍵
remove(key):從樹中移除某個鍵
基礎了解
root:表示根節點,在鏈表中使用head
節點:這里的樹節點會有三個屬性
left:表示其左側節點
? key:存放當前節點資料
? right: 表示其右側節點
代碼實作
enum Compare {
LESS_THAN = -1,
BIGGER_THAN = 1,
EQUALS = 0
}
class TreeNode<T> {
key: T;
left: TreeNode<T> | undefined;
right: TreeNode<T> | undefined;
constructor(key: T) {
this.key = key;
this.left = undefined;
this.right = undefined;
}
}
function defaultCompareFn<T>(parent: TreeNode<T>, child: TreeNode<T>) {
if (parent === child) {
return Compare.EQUALS
}
return parent > child ? Compare.BIGGER_THAN : Compare.LESS_THAN;
}
export class BinarySearchTree<T> {
root: TreeNode<T> | undefined;
compareFn: Function;
count: number;
constructor(compareFn: Function = defaultCompareFn) {
this.root = undefined;
this.count = 0;
this.compareFn = compareFn;
}
//向二叉搜索樹插入一個新的鍵
insert(key: T) {
// 當root沒有值的時候
if (this.root == null) {
this.root = new TreeNode<T>(key);
} else {
// 當root有值時,判斷當前key比root大(right)還是小(left)
return this.insertTreeNode(this.root, key);
}
}
//節點插入
insertTreeNode(cNode: TreeNode<T>, key: T) {
// 新值小于node
if (this.compareFn(cNode.key, key) === Compare.BIGGER_THAN) {
// left節點為null
if (cNode.left == null) {
cNode.left = new TreeNode<T>(key);
} else {
//left節點不為null就繼續在左節點插入
this.insertTreeNode(cNode.left, key)
}
}
// 新值大于node right節點為null
else {
if (cNode.right == null) {
cNode.right = new TreeNode<T>(key);
} else {
// 新值沒有插入又沒有跳過就是插入right
this.insertTreeNode(cNode.right, key);
}
}
}
// 搜索節點值
search(key: T) {
this.searchTreeNode(this.root, key);
}
// 搜索某個節點
searchTreeNode(node: TreeNode<T> | null, key: T): Boolean {
//如果node沒有值,則回傳false,表示沒有找到
if (node == null) {
return false;
}
switch (this.compareFn(node.key, key)) {
//父節點等于子節點
case Compare.EQUALS:
return true;
break;
// 父節點小于當前資料 所以要在right節點上找
case Compare.LESS_THAN:
return this.searchTreeNode(node.right, key)
break;
// 父節點大于當前資料 所以應該在左節點上找
default:
return this.searchTreeNode(node.left, key)
break;
}
}
//通過中序遍歷的方式遍歷所有節點
inOrderTraverse(callBack: Function) {
this.inOrderTraverseNode(this.root, callBack);
}
inOrderTraverseNode(node: TreeNode<T> | null, callBack: Function) {
if (node == null) {
return;
}
this.inOrderTraverseNode(node.left, callBack);
callBack(node.key);
this.inOrderTraverseNode(node.right, callBack);
}
//通過先序遍歷的方式遍歷所有節點
preOrderTraverse(callBack: Function) {
this.preOrderTraverseNode(this.root, callBack);
}
preOrderTraverseNode(node: TreeNode<T> | null, callBack: Function) {
if (node == null) {
return;
}
callBack(node.key);
this.inOrderTraverseNode(node.left, callBack);
this.inOrderTraverseNode(node.right, callBack);
}
//通過后序遍歷的方式遍歷所有的節點
postOrderTraverse(callBack: Function) {
this.postOrderTraverseNode(this.root, callBack);
}
postOrderTraverseNode(node: TreeNode<T> | null, callBack: Function) {
if (node == null) {
return;
}
this.inOrderTraverseNode(node.left, callBack);
this.inOrderTraverseNode(node.right, callBack);
callBack(node.key);
}
//回傳樹中最小的值/鍵
min(): TreeNode<T> {
if (this.root == null) {
return undefined;
}
if (this.root.left == null) {
return this.root;
}
return this.minNode(this.root);
}
minNode(node: TreeNode<T> | null): TreeNode<T> {
if (node) {
if (node.left == null) {
return node;
} else {
return this.minNode(node.left);
}
}
return undefined;
}
//回傳樹中最大的值/鍵
max(): TreeNode<T> {
if (this.root == null) {
return undefined;
}
if (this.root.right == null) {
return this.root;
}
return this.maxNode(this.root);
}
maxNode(node: TreeNode<T> | null): TreeNode<T> {
if (node) {
if (node.right == null) {
return node;
} else {
return this.maxNode(node.right);
}
} else {
return undefined;
}
}
getRoot() {
return this.root;
}
//移除一個節點
remove(key: T) {
this.root = this.removeNode(this.root, key);
}
removeNode(node: TreeNode<T>, key: T): TreeNode<T> {
//判斷這個樹上是否有節點
if (node == undefined) {
return undefined;
}
//樹上是有節點的,這個時候就要判斷當前節點是否與洗掉的元素相同
switch (this.compareFn(node.key, key)) {
//父節點等于子節點
case Compare.EQUALS:
node = this.removeCurrentNode(node);
return node;
break;
// 父節點小于當前資料 所以要在right節點上找
case Compare.LESS_THAN:
node.right = this.removeNode(node.right, key)
return node
break;
// 父節點大于當前資料 所以應該在左節點上找
default:
node.left = this.removeNode(node.left, key)
return node
break;
}
}
removeCurrentNode(node: TreeNode<T>): TreeNode<T> {
//分成三種情況
//一:葉結點(沒有左右子節點),那么我們直接將該節點賦值為undefined
if (node.left == null && node.right == null) {
node = undefined;
return node;
}
//二:只有一個左節點或一個右節點
//左節點不存在,將父節點的右節點指標指向移除節點的右節點
if (node.left == null) {
node = node.right;
return node;
} else if(node.right == null){
node = node.left;
return node;
}
//三:有兩個節點的元素
const aux = this.minNode(node.right);
node.key = aux.key;
node.right = this.removeNode(node.right,aux.key);
return node;
}
}
輔助分析:
遞回遍歷部分圖解分析(這里只分析了左半部分):
從下向上看"呼叫堆疊"
從下向上看"呼叫堆疊"
從上向下看"呼叫堆疊"
書中代碼
export enum Compare {
LESS_THAN = -1,
BIGGER_THAN = 1,
EQUALS = 0
}
type ICompareFunction<T> = (a: T, b: T) => number;
function defaultCompare<T>(a: T, b: T): number {
if (a === b) {
return Compare.EQUALS;
}
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
class Node<K> {
left: Node<K>;
right: Node<K>;
constructor(public key: K) {}
toString() {
return `${this.key}`;
}
}
export default class BinarySearchTree<T> {
protected root: Node<T>;
constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {}
insert(key: T) {
// special case: first key
if (this.root == null) {
this.root = new Node(key);
} else {
this.insertNode(this.root, key);
}
}
protected insertNode(node: Node<T>, key: T) {
if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
if (node.left == null) {
node.left = new Node(key);
} else {
this.insertNode(node.left, key);
}
} else if (node.right == null) {
node.right = new Node(key);
} else {
this.insertNode(node.right, key);
}
}
getRoot() {
return this.root;
}
search(key: T) {
return this.searchNode(this.root, key);
}
private searchNode(node: Node<T>, key: T): boolean {
if (node == null) {
return false;
}
if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
return this.searchNode(node.left, key);
} else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
return this.searchNode(node.right, key);
}
// key is equal to node.item
return true;
}
inOrderTraverse(callback: Function) {
this.inOrderTraverseNode(this.root, callback);
}
private inOrderTraverseNode(node: Node<T>, callback: Function) {
if (node != null) {
this.inOrderTraverseNode(node.left, callback);
callback(node.key);
this.inOrderTraverseNode(node.right, callback);
}
}
preOrderTraverse(callback: Function) {
this.preOrderTraverseNode(this.root, callback);
}
private preOrderTraverseNode(node: Node<T>, callback: Function) {
if (node != null) {
callback(node.key);
this.preOrderTraverseNode(node.left, callback);
this.preOrderTraverseNode(node.right, callback);
}
}
postOrderTraverse(callback: Function) {
this.postOrderTraverseNode(this.root, callback);
}
private postOrderTraverseNode(node: Node<T>, callback: Function) {
if (node != null) {
this.postOrderTraverseNode(node.left, callback);
this.postOrderTraverseNode(node.right, callback);
callback(node.key);
}
}
min() {
return this.minNode(this.root);
}
protected minNode(node: Node<T>) {
let current = node;
while (current != null && current.left != null) {
current = current.left;
}
return current;
}
max() {
return this.maxNode(this.root);
}
protected maxNode(node: Node<T>) {
let current = node;
while (current != null && current.right != null) {
current = current.right;
}
return current;
}
remove(key: T) {
this.root = this.removeNode(this.root, key);
}
protected removeNode(node: Node<T>, key: T) {
if (node == null) {
return null;
}
if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
node.left = this.removeNode(node.left, key);
return node;
} else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
node.right = this.removeNode(node.right, key);
return node;
} else {
// key is equal to node.item
// handle 3 special conditions
// 1 - a leaf node
// 2 - a node with only 1 child
// 3 - a node with 2 children
// case 1
if (node.left == null && node.right == null) {
node = null;
return node;
}
// case 2
if (node.left == null) {
node = node.right;
return node;
} else if (node.right == null) {
node = node.left;
return node;
}
// case 3
const aux = this.minNode(node.right);
node.key = aux.key;
node.right = this.removeNode(node.right, aux.key);
return node;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/226408.html
標籤：其他
上一篇：第九章 遞回