二叉樹的特點:
- 二叉樹是一種數(shù)據(jù)結(jié)構(gòu)。
- 由一系列節(jié)點組成助泽，具有層級結(jié)構(gòu)。每個節(jié)點的特性包含有節(jié)點值嚎京，關(guān)系指針嗡贺。節(jié)點之間存在對應(yīng)關(guān)系。
- 樹中存在一個沒有父節(jié)點的節(jié)點鞍帝，叫做根節(jié)點诫睬。樹的末尾存在一系列沒有子節(jié)點的節(jié)點，成為葉子節(jié)點帕涌。其他可以叫做中間節(jié)點摄凡。
- 樹的根節(jié)點位于第一層，層級數(shù)越大蚓曼，節(jié)點位置越深亲澡，層基數(shù)也叫做樹高。
二叉樹排序是二叉樹的一種類型纫版，特點是:
- 節(jié)點分為左右子樹床绪。
- 在不為空的情況下，左子樹子節(jié)點的值都小于父節(jié)點的值。
-
在不為空的情況下癞己，右子樹子節(jié)點的值都大于父節(jié)點得值膀斋。
二叉排序樹.png
代碼實現(xiàn)
節(jié)點用對象來描述，節(jié)點特性用對象屬性來描述末秃。
//創(chuàng)建節(jié)點類
class Node {
constructor(key) {
this.key = key;//節(jié)點值
this.left = null;//左指針
this.right = null;//右指針
}
}
二叉樹結(jié)構(gòu)用對象來描述概页。
class BinaryTree {
constructor() {
this.root = null;
}
}
插入值
//插入
insert(key) {
const newNode = new Node(key);
if (this.root === null) {//設(shè)置根節(jié)點
this.root = newNode;
}
this.insertNode(this.root, newNode);
}
insertNode(node, newNode) {
if (newNode.key < node.key) {//插值小于節(jié)點值進入左子樹
if (node.left === null) {//直到左子樹為空
node.left = newNode
} else {//左子樹已存在
this.insertNode(node.left, newNode)
}
} else if (newNode.key > node.key){//插入值大于節(jié)點值進入右子樹
if (node.right === null) {//直到右子樹為空
node.right = newNode
} else {//右子樹已存在
this.insertNode(node.right, newNode)
}
}
}
使用方法
// 實例化二叉樹
const binaryTree = new BinaryTree();
// key值
const keys = [19, 8, 15, 24, 45, 12, 5];
// 生成二叉排序樹
keys.forEach(key => binaryTree.insert(key));
二叉排序樹的遍歷
中序遍歷
- 總是先遍歷左子樹，然后訪問根節(jié)點练慕，接著遍歷右子樹
//中序遍歷
inorderTraversal() {
let info = [];
this.inorderTraversalNode(this.root, ({key}) => {
info.push(key)
});
return info;
}
inorderTraversalNode(node, callback) {
if (node) {//當(dāng)前節(jié)點
this.inorderTraversalNode(node.left, callback);//遍歷左子樹
callback(node);//訪問節(jié)點
this.inorderTraversalNode(node.right, callback);//遍歷右子樹
}
}
//遍歷結(jié)果：[5, 8, 12, 15, 19, 24, 45]
前序遍歷
- 總是先訪問根節(jié)點惰匙，然后遍歷左子樹，接著遍歷右子樹铃将。
//前序遍歷
preOrderTraversal() {
let info = [];
this.preOrderTraversalNode(this.root, ({key}) => {
info.push(key)
});
return info;
}
preOrderTraversalNode(node, callback) {
if (node) {//當(dāng)前節(jié)點
callback(node);//訪問節(jié)點
this.preOrderTraversalNode(node.left, callback);//遍歷左子樹
this.preOrderTraversalNode(node.right, callback);//遍歷右子樹
}
}
//遍歷結(jié)果：[19, 8, 5, 15, 12, 24, 45]
后序遍歷
- 總是先遍歷左子樹项鬼，接著遍歷右子樹，最后訪問根節(jié)點劲阎。
//后序遍歷
postOrderTraversal() {
let info = [];
this.postOrderTraversalNode(this.root, ({key}) => {
info.push(key)
});
return info;
}
postOrderTraversalNode(node, callback){
if (node) {//當(dāng)前節(jié)點
this.postOrderTraversalNode(node.left, callback);//遍歷左子樹
this.postOrderTraversalNode(node.right, callback);//遍歷右子樹
callback(node);//訪問節(jié)點
}
}
//遍歷結(jié)果：[5, 12, 15, 8, 45, 24, 19]
二叉排序樹的查找
查找最大值
- 根據(jù)二叉排序樹的特點绘盟，右子樹的值都大于父節(jié)點得值。只需要進入節(jié)點的右子樹查找悯仙，當(dāng)某個節(jié)點的右子樹為空時龄毡，該節(jié)點就是最大值。
//最大值
max() {
return this.maxNode(this.root)
}
maxNode(node) {
if (node) {
while (node.right !== null) {//右子樹不為空時
node = node.right;
}
return node.key
}
return null
}
查找最小值
- 根據(jù)二叉排序樹的特點锡垄，左子樹的值都小于父節(jié)點的值沦零。只需要進入節(jié)點的左子樹查找，當(dāng)某個節(jié)點的左子樹為空時货岭，該節(jié)點就是最小值
//最小值
min() {
return this.minNode(this.root)
}
minNode(node) {
if (node) {
while (node.left !== null) {//左子樹不為空時
node = node.left;
}
return node.key
}
return null
}
查找指定值路操。
- 在二叉排序樹中查找有沒有節(jié)點對應(yīng)的值與給定值相同。
- 根據(jù)排序二叉樹的特點千贯，比較給定值與節(jié)點值屯仗，小于時進入節(jié)點左子樹。大于時進入節(jié)點右子樹搔谴。等于時返回真魁袜。層層對比，最后如果子樹為空己沛，則表示沒找到慌核。
//查找
search(key) {
return this.searchNode(this.root, key)
}
searchNode(node, key) {
if (node === null) {
return false
}
if (key < node.key) {//進入左子樹
return this.searchNode(node.left, key)
} else if (key > node.key) {//進入右子樹
return this.searchNode(node.right, key)
} else {//相等
return true
}
}
二叉排序樹的刪除
- 當(dāng)刪除的節(jié)點為葉子節(jié)點，關(guān)系指針為空申尼，直接把葉子節(jié)點設(shè)置成空。
- 當(dāng)刪除的節(jié)點存在左子樹垫桂，把父節(jié)點的關(guān)系指針直接指向左子樹师幕。存在右子樹同理。
- 當(dāng)刪除的節(jié)點存在左右子樹時，先去右子樹找最小值霹粥，然后用最小值替換節(jié)點值灭将，最后進入右子樹刪除最小值對應(yīng)的節(jié)點。
//刪除
remove(key) {
this.root = this.removeNode(this.root, key)
}
removeNode(node, key) {
if (node === null) {//沒有找到值對應(yīng)節(jié)點
return null
}
if (key < node.key) {//給定值小于當(dāng)前節(jié)點值
node.left = this.removeNode(node.left, key);
return node
} else if (key > node.key) {//給定值大于當(dāng)前節(jié)點值
node.right = this.removeNode(node.right, key);
return node
} else {//找到對應(yīng)的節(jié)點
if (node.left === null && node.right === null) {//節(jié)點為葉子節(jié)點
node = null;
return node
}
if (node.right === null) {//節(jié)點存在左子樹
node = node.left;
return node
} else if (node.left === null) {//節(jié)點存在右子樹
node = node.right;
return node
}
//節(jié)點存在左右子樹時后控，先去右子樹找最小值
const minKey = this.minNode(node.right);
//用最小值替換節(jié)點值
node.key = minKey;
//進入右子樹刪除最小值對應(yīng)的節(jié)點庙曙。
this.removeNode(node.right, minKey);
return node;
}
}
