2024-05-05 23:31:00 +08:00
<!DOCTYPE HTML>
< html lang = "en" class = "sidebar-visible no-js coal" >
< head >
<!-- Book generated using mdBook -->
< meta charset = "UTF-8" >
< title > binary search tree - Andrew' s Blog< / title >
<!-- Custom HTML head -->
< meta name = "description" content = "Andrew Ryan's Blog" >
< meta name = "viewport" content = "width=device-width, initial-scale=1" >
< meta name = "theme-color" content = "#ffffff" / >
< link rel = "icon" href = "../../favicon.svg" >
< link rel = "shortcut icon" href = "../../favicon.png" >
< link rel = "stylesheet" href = "../../css/variables.css" >
< link rel = "stylesheet" href = "../../css/general.css" >
< link rel = "stylesheet" href = "../../css/chrome.css" >
<!-- Fonts -->
< link rel = "stylesheet" href = "../../FontAwesome/css/font-awesome.css" >
< link rel = "stylesheet" href = "../../fonts/fonts.css" >
<!-- Highlight.js Stylesheets -->
< link rel = "stylesheet" href = "../../highlight.css" >
< link rel = "stylesheet" href = "../../tomorrow-night.css" >
< link rel = "stylesheet" href = "../../ayu-highlight.css" >
<!-- Custom theme stylesheets -->
< link rel = "stylesheet" href = "../../src/style/custom.css" >
<!-- MathJax -->
< script async src = "https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML" > < / script >
< / head >
< body >
< div id = "body-container" >
<!-- Provide site root to javascript -->
< script >
var path_to_root = "../../";
var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "coal" : "coal";
< / script >
<!-- Work around some values being stored in localStorage wrapped in quotes -->
< script >
try {
var theme = localStorage.getItem('mdbook-theme');
var sidebar = localStorage.getItem('mdbook-sidebar');
if (theme.startsWith('"') & & theme.endsWith('"')) {
localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
}
if (sidebar.startsWith('"') & & sidebar.endsWith('"')) {
localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
}
} catch (e) { }
< / script >
<!-- Set the theme before any content is loaded, prevents flash -->
< script >
var theme;
try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
if (theme === null || theme === undefined) { theme = default_theme; }
var html = document.querySelector('html');
html.classList.remove('no-js')
html.classList.remove('coal')
html.classList.add(theme);
html.classList.add('js');
< / script >
<!-- Hide / unhide sidebar before it is displayed -->
< script >
var html = document.querySelector('html');
var sidebar = null;
if (document.body.clientWidth >= 1080) {
try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
sidebar = sidebar || 'visible';
} else {
sidebar = 'hidden';
}
html.classList.remove('sidebar-visible');
html.classList.add("sidebar-" + sidebar);
< / script >
< nav id = "sidebar" class = "sidebar" aria-label = "Table of contents" >
< div class = "sidebar-scrollbox" >
2024-05-09 21:02:15 +08:00
< ol class = "chapter" > < li class = "chapter-item affix " > < a href = "../../index.html" > Andrew's Blog< / a > < / li > < li class = "chapter-item " > < a href = "../../posts/linux/linux.html" > < strong aria-hidden = "true" > 1.< / strong > Linux< / a > < a class = "toggle" > < div > ❱< / div > < / a > < / li > < li > < ol class = "section" > < li class = "chapter-item " > < a href = "../../posts/linux/install_linux.html" > < strong aria-hidden = "true" > 1.1.< / strong > install linux< / a > < / li > < li class = "chapter-item " > < a href = "../../posts/linux/bash_profile.html" > < strong aria-hidden = "true" > 1.2.< / strong > bash profile< / a > < / li > < li class = "chapter-item " > < a href = "../../posts/linux/command_list.html" > < strong aria-hidden = "true" > 1.3.< / strong > command list< / a > < / li > < li class = "chapter-item " > < a href = "../../posts/linux/git_guide.html" > < strong aria-hidden = "true" > 1.4.< / strong > git guide< / a > < / li > < li class = "chapter-item " > < a href = "../../posts/linux/tar.html" > < strong aria-hidden = "true" > 1.5.< / strong > tar< / a > < / li > < li class = "chapter-item " > < a href = "../../posts/linux/git_cheatsheet.html" > < strong aria-hidden = "true" > 1.6.< / strong > Git Cheatsheet< / a > < / li > < li class = "chapter-item " > < a href = "../../posts/linux/bash_cheatsheet.html" > < strong aria-hidden = "true" > 1.7.< / strong > Bash Cheatsheet< / a > < / li > < / ol > < / li > < li class = "chapter-item " > < a href = "../../posts/macos/mac.html" > < strong aria-hidden = "true" > 2.< / strong > MacOS< / a > < a class = "toggle" > < div > ❱< / div > < / a > < / li > < li > < ol class = "section" > < li class = "chapter-item " > < a href = "../../posts/macos/macos_profiles.html" > < strong aria-hidden = "true" > 2.1.< / strong > macos profiles< / a > < / li > < li class = "chapter-item " > < a href = "../../posts/macos/macos_pwn_env_setup.html" > < strong aria-hidden = "true" > 2.2.< / strong > macos pwn env setup< / a > < / li > < / ol > < / li > < li class = "chapter-item " > < a href = "../../posts/windows/windows.html" > < strong aria-hidden = "true" > 3.< / strong > Windows< / a > < a class = "toggle" > < div > ❱< / div > < / a > < / li > < li > < ol class = "section" > < li class = "chapter-item " > < a href = "../../posts/windows/windows.html" > < strong aria-hidden = "true" > 3.1.< / strong > Windows< / a > < / li > < li class = "chapter-item " > < a href = "../../posts/windows/windows10_use_powershell_dedup_redundent_path.html" > < strong aria-hidden = "true" > 3.2.< / strong > Windows10 use PowerShell dedup redundent PATH< / a > < / li > < / ol > < / li > < li class = "chapter-item " > < a href = "../../posts/cs/cs.html" > < strong aria-hidden = "true" > 4.< / strong > C#< / a > < a class = "toggle" > < div > ❱< / div > < / a > < / li > < li > < ol class = "section" > < li class = "chapter-item " > < a href = "../../posts/cs/learn_cs_basics.html" > < strong aria-hidden = "true" > 4.1.< / strong > Learn C# Basics< / a > < / li > < / ol > < / li > < li class = "chapter-item " > < a href = "../../posts/swift/swift.html" > < strong aria-hidden = "true" > 5.< / strong > Swift< / a > < a class = "toggle" > < div > ❱< / div > < / a > < / li > < li > < ol class = "section" > < li class = "chapter-item " > < a href = "../../posts/swift/learn_swift.html" > < strong aria-hidden = "true" > 5.1.< / strong > learn swift basics< / a > < / li > < li class = "chapter-item " > < a href = "../../posts/swift/swift_extensions.html" > < strong aria-hidden = "true" > 5.2.< / strong > Swift extensions< / a > < / li > < li class = "chapter-item " > < a href = "../../posts/swift/swiftui_extension.html" > < strong aria-hidden = "true" > 5.3.< / strong > SwiftUI extensions< / a > < / li > < li class = "chapter-item " > < a href = "../../posts/swift/install_swift.html" > < strong aria-hidden = "true" > 5.4.< / strong > install swift< / a > < / li > < li class = "chapter-item " > < a href = "../../posts/swift/task_planner.html" > < strong aria-hidden = "true" > 5.5.< / strong > implment task panner app with SwiftUI< / a > < / li > < li class = "chapter-item " > < a href = "../../posts/swift/swift_cheat_sheet.html" > < strong aria-hidden = "true" > 5.6.< / strong > Swift Cheat Sheet< / a > < / li > < li class = "chapter-item " > < a href = "../../posts/swift/yinci_url.html" > < strong aria-hidden = "true" > 5.7.< / strong > Personal privacy protocol< / a > < / li > < li class = "chapter-item " > < a href = "../../posts/swift/swift_regular_exressions.html" > < strong aria-hidden = "true" > 5.8.< / strong > Swift regular exressions< / a > < / li > < li class = "chapter-item " > < a href = "../../posts/ios/how_to_create_beautiful_ios_charts_in_swift.html" > < strong aria-hidden = "true" > 5.9.< / strong > How to Create Beautiful iOS Charts in < / a > < / li > < li class = "cha
2024-05-05 23:31:00 +08:00
< / div >
< div id = "sidebar-resize-handle" class = "sidebar-resize-handle" > < / div >
< / nav >
<!-- Track and set sidebar scroll position -->
< script >
var sidebarScrollbox = document.querySelector('#sidebar .sidebar-scrollbox');
sidebarScrollbox.addEventListener('click', function(e) {
if (e.target.tagName === 'A') {
sessionStorage.setItem('sidebar-scroll', sidebarScrollbox.scrollTop);
}
}, { passive: true });
var sidebarScrollTop = sessionStorage.getItem('sidebar-scroll');
sessionStorage.removeItem('sidebar-scroll');
if (sidebarScrollTop) {
// preserve sidebar scroll position when navigating via links within sidebar
sidebarScrollbox.scrollTop = sidebarScrollTop;
} else {
// scroll sidebar to current active section when navigating via "next/previous chapter" buttons
var activeSection = document.querySelector('#sidebar .active');
if (activeSection) {
activeSection.scrollIntoView({ block: 'center' });
}
}
< / script >
< div id = "page-wrapper" class = "page-wrapper" >
< div class = "page" >
< div id = "menu-bar-hover-placeholder" > < / div >
< div id = "menu-bar" class = "menu-bar sticky" >
< div class = "left-buttons" >
< button id = "sidebar-toggle" class = "icon-button" type = "button" title = "Toggle Table of Contents" aria-label = "Toggle Table of Contents" aria-controls = "sidebar" >
< i class = "fa fa-bars" > < / i >
< / button >
< button id = "theme-toggle" class = "icon-button" type = "button" title = "Change theme" aria-label = "Change theme" aria-haspopup = "true" aria-expanded = "false" aria-controls = "theme-list" >
< i class = "fa fa-paint-brush" > < / i >
< / button >
< ul id = "theme-list" class = "theme-popup" aria-label = "Themes" role = "menu" >
< li role = "none" > < button role = "menuitem" class = "theme" id = "light" > Light< / button > < / li >
< li role = "none" > < button role = "menuitem" class = "theme" id = "rust" > Rust< / button > < / li >
< li role = "none" > < button role = "menuitem" class = "theme" id = "coal" > Coal< / button > < / li >
< li role = "none" > < button role = "menuitem" class = "theme" id = "navy" > Navy< / button > < / li >
< li role = "none" > < button role = "menuitem" class = "theme" id = "ayu" > Ayu< / button > < / li >
< / ul >
< button id = "search-toggle" class = "icon-button" type = "button" title = "Search. (Shortkey: s)" aria-label = "Toggle Searchbar" aria-expanded = "false" aria-keyshortcuts = "S" aria-controls = "searchbar" >
< i class = "fa fa-search" > < / i >
< / button >
< / div >
< h1 class = "menu-title" > Andrew' s Blog< / h1 >
< div class = "right-buttons" >
< a href = "https://gitee.com/dnrops/dnrops" title = "Git repository" aria-label = "Git repository" >
< i id = "git-repository-button" class = "fa fa-github" > < / i >
< / a >
< / div >
< / div >
< div id = "search-wrapper" class = "hidden" >
< form id = "searchbar-outer" class = "searchbar-outer" >
< input type = "search" id = "searchbar" name = "searchbar" placeholder = "Search this book ..." aria-controls = "searchresults-outer" aria-describedby = "searchresults-header" >
< / form >
< div id = "searchresults-outer" class = "searchresults-outer hidden" >
< div id = "searchresults-header" class = "searchresults-header" > < / div >
< ul id = "searchresults" >
< / ul >
< / div >
< / div >
<!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
< script >
document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
});
< / script >
< div id = "content" class = "content" >
< main >
< h1 id = "binary-search-tree" > < a class = "header" href = "#binary-search-tree" > Binary Search Tree< / a > < / h1 >
< h2 id = "implement-with-javascript" > < a class = "header" href = "#implement-with-javascript" > Implement with Javascript< / a > < / h2 >
< pre > < code class = "language-js" > // Node class
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// Binary Search tree class
class BinarySearchTree {
constructor() {
// root of a binary search tree
this.root = null;
}
// function to be implemented
// insert(data)
// helper method which creates a new node to
// be inserted and calls insertNode
insert(data) {
// Creating a node and initialising
// with data
var newNode = new Node(data);
// root is null then node will
// be added to the tree and made root.
if (this.root === null) {
this.root = newNode;
} // find the correct position in the
// tree and add the node
else {
this.insertNode(this.root, newNode);
}
}
// Method to insert a node in a tree
// it moves over the tree to find the location
// to insert a node with a given data
insertNode(node, newNode) {
// if the data is less than the node
// data move left of the tree
if (newNode.data < node.data) {
// if left is null insert node here
if (node.left === null) {
node.left = newNode;
} // if left is not null recur until
// null is found
else {
this.insertNode(node.left, newNode);
}
} // if the data is more than the node
// data move right of the tree
else {
// if right is null insert node here
if (node.right === null) {
node.right = newNode;
} // if right is not null recur until
// null is found
else {
this.insertNode(node.right, newNode);
}
}
}
// remove(data)
// helper method that calls the
// removeNode with a given data
remove(data) {
// root is re-initialized with
// root of a modified tree.
this.root = this.removeNode(this.root, data);
}
// Method to remove node with a
// given data
// it recur over the tree to find the
// data and removes it
removeNode(node, key) {
// if the root is null then tree is
// empty
if (node === null) {
return null;
} // if data to be delete is less than
// roots data then move to left subtree
else if (key < node.data) {
node.left = this.removeNode(node.left, key);
return node;
} // if data to be delete is greater than
// roots data then move to right subtree
else if (key > node.data) {
node.right = this.removeNode(node.right, key);
return node;
} // if data is similar to the root's data
// then delete this node
else {
// deleting node with no children
if (node.left === null & & node.right === null) {
node = null;
return node;
}
// deleting node with one children
if (node.left === null) {
node = node.right;
return node;
} else if (node.right === null) {
node = node.left;
return node;
}
// Deleting node with two children
// minimum node of the right subtree
// is stored in aux
var aux = this.findMinNode(node.right);
node.data = aux.data;
node.right = this.removeNode(node.right, aux.data);
return node;
}
}
// Helper function
// findMinNode()
// finds the minimum node in tree
// searching starts from given node
findMinNode(node) {
// if left of a node is null
// then it must be minimum node
if (node.left === null) {
return node;
} else {
return this.findMinNode(node.left);
}
}
// getRootNode()
// returns root of the tree
getRootNode() {
return this.root;
}
// inorder(node)
// Performs inorder traversal of a tree
inorder(node) {
if (node !== null) {
this.inorder(node.left);
console.log(node.data);
this.inorder(node.right);
}
}
// preorder(node)
// Performs preorder traversal of a tree
preorder(node) {
if (node !== null) {
console.log(node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
// postorder(node)
// Performs postorder traversal of a tree
postorder(node) {
if (node !== null) {
this.postorder(node.left);
this.postorder(node.right);
console.log(node.data);
}
}
// search(node, data)
// search for a node with given data
search(node, data) {
// if trees is empty return null
if (node === null) {
return null;
} // if data is less than node's data
// move left
else if (data < node.data) {
return this.search(node.left, data);
} // if data is less than node's data
// move left
else if (data > node.data) {
return this.search(node.right, data);
} // if data is equal to the node data
// return node
else {
return node;
}
}
}
// create an object for the BinarySearchTree
var BST = new BinarySearchTree();
// Inserting nodes to the BinarySearchTree
BST.insert(15);
BST.insert(25);
BST.insert(10);
BST.insert(7);
BST.insert(22);
BST.insert(17);
BST.insert(13);
BST.insert(5);
BST.insert(9);
BST.insert(27);
// 15
// / \
// 10 25
// / \ / \
// 7 13 22 27
// / \ /
// 5 9 17
var root = BST.getRootNode();
// prints 5 7 9 10 13 15 17 22 25 27
BST.inorder(root);
// Removing node with no children
BST.remove(5);
// 15
// / \
// 10 25
// / \ / \
// 7 13 22 27
// \ /
// 9 17
var root = BST.getRootNode();
// prints 7 9 10 13 15 17 22 25 27
BST.inorder(root);
// Removing node with one child
BST.remove(7);
// 15
// / \
// 10 25
// / \ / \
// 9 13 22 27
// /
// 17
var root = BST.getRootNode();
// prints 9 10 13 15 17 22 25 27
BST.inorder(root);
// Removing node with two children
BST.remove(15);
// 17
// / \
// 10 25
// / \ / \
// 9 13 22 27
var root = BST.getRootNode();
console.log(" inorder traversal" );
// prints 9 10 13 17 22 25 27
BST.inorder(root);
console.log(" postorder traversal" );
BST.postorder(root);
console.log(" preorder traversal" );
BST.preorder(root);
< / code > < / pre >
< / main >
< nav class = "nav-wrapper" aria-label = "Page navigation" >
<!-- Mobile navigation buttons -->
< a rel = "prev" href = "../../posts/javascript/getting_started_with_ajax.html" class = "mobile-nav-chapters previous" title = "Previous chapter" aria-label = "Previous chapter" aria-keyshortcuts = "Left" >
< i class = "fa fa-angle-left" > < / i >
< / a >
< a rel = "next" href = "../../posts/javascript/goole_zx.html" class = "mobile-nav-chapters next" title = "Next chapter" aria-label = "Next chapter" aria-keyshortcuts = "Right" >
< i class = "fa fa-angle-right" > < / i >
< / a >
< div style = "clear: both" > < / div >
< / nav >
< / div >
< / div >
< nav class = "nav-wide-wrapper" aria-label = "Page navigation" >
< a rel = "prev" href = "../../posts/javascript/getting_started_with_ajax.html" class = "nav-chapters previous" title = "Previous chapter" aria-label = "Previous chapter" aria-keyshortcuts = "Left" >
< i class = "fa fa-angle-left" > < / i >
< / a >
< a rel = "next" href = "../../posts/javascript/goole_zx.html" class = "nav-chapters next" title = "Next chapter" aria-label = "Next chapter" aria-keyshortcuts = "Right" >
< i class = "fa fa-angle-right" > < / i >
< / a >
< / nav >
< / div >
< script >
window.playground_line_numbers = true;
< / script >
< script >
window.playground_copyable = true;
< / script >
< script src = "../../ace.js" > < / script >
< script src = "../../editor.js" > < / script >
< script src = "../../mode-rust.js" > < / script >
< script src = "../../theme-dawn.js" > < / script >
< script src = "../../theme-tomorrow_night.js" > < / script >
< script src = "../../elasticlunr.min.js" > < / script >
< script src = "../../mark.min.js" > < / script >
< script src = "../../searcher.js" > < / script >
< script src = "../../clipboard.min.js" > < / script >
< script src = "../../highlight.js" > < / script >
< script src = "../../book.js" > < / script >
<!-- Custom JS scripts -->
< script src = "../../src/js/custom.js" > < / script >
< / div >
< / body >
< / html >
