資訊專欄INFORMATION COLUMN
摘要：實現二叉排序樹實現二叉排序樹初始化二叉樹只接受一個數組作為參數根節點接受傳入的參數數組初始化每個樹節點當前節點的值左子樹右子樹構建二叉樹請選擇一個數組參數插入節點當前需要插入的節點根節點不存在值時插入節點到根節點當前節點的小于父節點時當
JS實現二叉排序樹
JS實現二叉排序樹
1. 初始化二叉樹 function BinaryTree (arr) {
if (Object.prototype.toString.call(arr).slice(8, -1) !== "Array") {
throw new TypeError("只接受一個數組作為參數")
}
this.root = null; //根節點
this.arr = arr || []; //接受傳入的參數-數組
//初始化每個樹節點
var TreeNode = function (key) {
this.key = key; //當前節點的值
this.left = null; //左子樹
this.right = null; //右子樹
}
//構建二叉樹
this.init = function () {
if (!this.arr) {
console.warn("請選擇一個數組參數");
}
for (var i = 0, len = this.arr.length; i < len; i++) {
this.insert(this.arr[i])
}
}
//插入節點
this.insert = function (key) {
var newNode = new TreeNode(key) //當前需要插入的節點
if (this.root === null) { //根節點不存在值時, 插入節點到根節點
this.root = newNode;
}else{
this.insertNode(this.root, newNode)
}
}
this.insertNode = function (rootNode, newNode) {
if (rootNode.key > newNode.key) { // 當前節點的key小于父節點時, 當前節點應該插入左子樹
if (rootNode.left === null) { //如果左子樹不存在節點時, 把當前節點放進去
rootNode.left = newNode;
return;
}
this.insertNode(rootNode.left, newNode) //左子樹存在節點, 再次遞歸與該左節點進行比較
}else{ // 當前節點的key大于或等于父節點時, 當前節點應該插入右子樹
if (rootNode.right === null) { //如果右子樹不存在節點時, 把當前節點放進去
rootNode.right = newNode;
return;
}
this.insertNode(rootNode.right, newNode) //右子樹存在節點, 再次遞歸與該右節點進行比較
}
}
}
var arr = [8, 13,3,7,19,21,15];
var tree = new BinaryTree(arr);
tree.init();
console.log(tree)
結構圖如下
/*
前序遍歷：根節點->左子樹->右子樹
中序遍歷：左子樹->根節點->右子樹
后序遍歷：左子樹->右子樹->根節點
*/
前序遍歷
//前序遍歷
this.preorderTraversal = function (callback) {
if (this.root === null) { //傳入根節點
console.warn("請先初始化二叉排序樹");
return;
}
var fn = function (node, callback) {
if (node !== null) { //當前節點不等于空的時候,先遍歷自身節點, 再遍歷左子樹節點, 最后遍歷右子樹節點
callback(node); //自身
fn(node.left, callback); //左子樹
fn(node.right, callback) //右子樹
}
}
fn(this.root, callback)
}
中序遍歷
//中序遍歷
this.orderTraversal = function (callback) { //從小到大
callback = callback || function () {};
if (this.root === null) { //傳入根節點
console.warn("請先初始化二叉排序樹");
return;
}
var fn = function (node, callback) {
if (node !== null) { //當前節點不等于空的時候,先遍歷左子樹節點, 再遍歷自身節點, 最后遍歷右子樹節點
fn(node.left, callback); //左子樹
callback(node); //自身
fn(node.right, callback); //右子樹
}
}
fn(this.root, callback)
}
后序遍歷
//后序遍歷
this.postorderTraversal = function (callback) {
if (this.root === null) { //傳入根節點
console.warn("Please initialize first");
return;
}
var fn = function (node, callback) {
if (node !== null) { //當前節點不等于空的時候,先遍歷左子樹節點, 再遍歷右子樹節點, 最后遍歷自身節點
fn(node.left, callback); //左子樹
fn(node.right, callback); //右子樹
callback(node); //自身
}
}
fn(this.root, callback)
}
4.查找最小值
this.min = function () { //查找最小值就一直往左邊查找就行了,直到左邊沒有節點為止,那就證明已經到最小值了
var fn = function (node) {
if (node == null) { //傳入根節點
console.warn("請先初始化二叉排序樹");
return null;
}
if (node.left) { //查找當前左子樹有沒有節點, 有點話繼續遞歸查找該左節點存不存在左節點
return fn(node.left);
}else{ //直到當前節點不在存在左節點,證明取到最小值了
return node;
}
}
return fn(this.root)
}
5.查找最大值
//查找最大值
this.max = function () { //跟查找最小值一樣, 查找最大值就一直往右邊查找就行了
var fn = function (node) {
if (node == null) { //傳入根節點
console.warn("請先初始化二叉排序樹");
return null;
}
if (node.right) {
return fn(node.right);
}else{
return node;
}
}
return fn(this.root)
}
6.刪除節點
//刪除節點
this.remove = function (key) {
var fn = function (node, key) {
if (node === null) { //傳入初始節點
console.warn("請先初始化二叉排序樹");
return null;
}
if (node.key > key) { //初始節點的值大于我要刪除節點的值, 說明我要刪除的節點在初始節點的左邊
node.left = fn(node.left, key) //遞歸一直尋找左邊的子節點,直到找到null 為止
return node;
}else if (node.key < key) {//初始節點的值小于我要刪除節點的值, 說明我要刪除的節點在初始節點的右邊
node.right = fn(node.right, key);
return node;
}else { //當前節點的值等于我要刪除節點的值,說明找到要刪除的節點了
//當前節點的左右兩邊分支都為空時,直接把當前節點置為null,返回出去
if (node.left === null && node.right === null) {
node = null;
return node;
}
//當前節點只有左邊為空時, 直接引入右邊的分支替換成當前分支
if (node.left === null) {
node = node.right;
return node;
}
//當前節點只有右邊為空時, 直接引入左邊的分支替換成當前分支
if (node.right == null) {
node = node.left;
return node;
}
//當左右兩邊節點都不為空時, 就需要找一個值來替換當前的值, 為了結構的完整性,最好是大于左邊的值,
//而且小于右邊的, 這個值的最佳選擇就是當前節點右邊的最小值, 這樣就能比左邊的大, 比右邊的小
//去右邊尋找最小值, 而且最小值應該在左子樹上
var minNode = rightMinNode(node.right);
// 那我們就要刪除右邊最小值的那個分支, 然后把值賦值到當前節點上
fn(node, minNode.key) //執行右邊最小值刪除操作
node.key = minNode.key
return node;
}
}
var rightMinNode = function (node) {
if (node.left === null) { //如果第一個右子樹的左子樹上為空的話, 那他就是最小值, 如果存在那就往左子樹上在進行查詢,知道左子樹為null時, 那就是最小值
return node;
}
return rightMinNode(node.left)
}
fn(this.root, key)
}
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/89722.html
摘要：代碼實現創建一個排序二叉樹節點類根節點插入節點以上便是創建排序二叉樹的實現方式重點在于插入節點的具體實現，即注釋的代碼片段。 排序二叉樹 showImg(https://segmentfault.com/img/bVbfdbp?w=1047&h=472); 如上圖為典型的排序二叉樹，左孩子的值比節點的值小，右孩子的值比節點的值大，關于具體的樹的定義及二叉樹的定義可以百度或查閱相關資料。...
摘要：桶排序與計數排序的區別桶排序中一個桶可以放一個范圍內的多個數據，在各個桶中又可以用其他方法排序，其快速之處在于只用對比同一個桶內的數字而無需與其他桶的數字作對比。與計數排序相比，桶排序需要作二次對比，但可省略桶的個數。 哈希表（Hash Table） 所有符合鍵值對即key-value的結構就是哈希。數組其實也是一種哈希。 計數排序（復雜度(n+max)）無法統計負數和小數，需要一個...
閱讀 2690·2021-11-08 13:16
閱讀 2367·2021-10-18 13:30
閱讀 2237·2021-09-27 13:35
閱讀 1993·2019-08-30 15:55
閱讀 2442·2019-08-30 13:22
閱讀 576·2019-08-30 11:24
閱讀 2077·2019-08-29 12:33
閱讀 1813·2019-08-26 12:10
