資訊專欄INFORMATION COLUMN
摘要：使用實現(xiàn)排序二叉樹排序二叉樹的定義二叉樹的基礎(chǔ)上，左節(jié)點比父節(jié)點要小，右節(jié)點比父節(jié)點要大的二叉樹，叫排序二叉樹。下期內(nèi)容實現(xiàn)排序二叉樹的中序前序后續(xù)遍歷實現(xiàn)二叉樹的節(jié)點查找功能實現(xiàn)排序二叉樹的刪除節(jié)點功能應(yīng)用排序二叉樹實現(xiàn)一個小游戲
使用javascript實現(xiàn)排序二叉樹（1）
排序二叉樹的定義： 二叉樹的基礎(chǔ)上，左節(jié)點比父節(jié)點要小，右節(jié)點比父節(jié)點要大的二叉樹，叫排序二叉樹。
下面直接進入到我們的javascript代碼 定義 排序二叉樹的過程
/*
分析二叉樹的結(jié)構(gòu)得出，二叉樹由節(jié)點構(gòu)成，每個節(jié)點又有自己的左右子樹。
并且有一個根節(jié)點
*/
function BinaryTree(){
var root = null; //根節(jié)點默認為null
/*
1.節(jié)點類型的構(gòu)造函數(shù),默認左右子樹都為空
*/
function Node(key){
this.key = key;
this.left = null;
this.right = null;
}
/*
2.根據(jù)排序二叉樹的規(guī)律，我們定義一個插入節(jié)點的方法，去填充排序二叉樹。該方法是BinaryTree的一個方法，需要綁定在this上讓其他調(diào)用者能調(diào)用。而不是作為內(nèi)部方法。
*/
this.insert = function(key){
var newNode = new Node(key);
if(root === null){
root = newNode;
}else{
insertNode(root,newNode)
}
}
var insertNode = function(node,newNode){
if(newNode.key < node.key){
if(node.left === null){
node.left = newNode;
}else{
insertNode(node.left,newNode)
}
}else{
if(newNode.key > node.key){
if(node.right === null){
node.right = newNode;
}else{
insertNode(node.right,newNode)
}
}
}
}
}
/*
測試：查看是否報錯，具體的流程邏輯可以通過打斷點來判斷是否與自己設(shè)想的一樣。
8
7 9
3 12
2 4
6
5
*/
var nodes = [8,7,3,4,6,5,2,9,12]
var binaryTree = new BinaryTree();
nodes.forEach((item)=>{
binaryTree.insert(item)
})
通過斷點調(diào)試，最后得到的一個二叉樹應(yīng)該是這樣的。也是符合二叉排序樹的定義的。
重點
分析數(shù)據(jù)結(jié)構(gòu)的一個規(guī)律，從而能夠定義出節(jié)點類型中有哪些屬性
方法不要都綁定在 this 上面，因為有些函數(shù)是不需要暴露出去的，而是內(nèi)部使用的。
我覺得讓我收獲比較大的是這里的 insert 這個函數(shù)中又調(diào)用一個 insertNode 的函數(shù)，因為事實上真正的插入節(jié)點是需要兩個參數(shù)的，一個父節(jié)點，一個要插入的節(jié)點。所以會需要遞歸調(diào)用，如果不依靠 insertNode 直接用 insert方法 去遞歸是沒法遞歸的。因為外部壓根獲取不到 root 。之前還想著 只用 一個方法就實現(xiàn)插入遞歸 ，但是確實不行。
下期內(nèi)容
實現(xiàn)排序二叉樹的 中序 前序 后續(xù) 遍歷
實現(xiàn)二叉樹的節(jié)點查找功能
實現(xiàn)排序二叉樹的 刪除節(jié)點功能
應(yīng)用排序二叉樹實現(xiàn)一個小游戲
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/97034.html
摘要：使用實現(xiàn)排序二叉樹上一篇文章我們構(gòu)造了基本的一個排序二叉樹的數(shù)據(jù)結(jié)構(gòu)，但是僅僅是定義了一個方法去創(chuàng)建二叉排序樹，今天我們來給我們的數(shù)據(jù)結(jié)構(gòu)添加一些遍歷的功能。 使用javascript實現(xiàn)排序二叉樹（2） 上一篇文章我們構(gòu)造了基本的一個排序二叉樹的數(shù)據(jù)結(jié)構(gòu)，但是僅僅是定義了一個insert方法去創(chuàng)建二叉排序樹，今天我們來給我們的數(shù)據(jù)結(jié)構(gòu)添加一些遍歷的功能。 二叉樹的三種遍歷方式（以根節(jié)...
摘要：筆者寫的數(shù)據(jù)結(jié)構(gòu)與算法之美系列用的語言是，旨在入門數(shù)據(jù)結(jié)構(gòu)與算法和方便以后復(fù)習(xí)。非線性表中的樹堆是干嘛用的其數(shù)據(jù)結(jié)構(gòu)是怎樣的希望大家?guī)е@兩個問題閱讀下文。其中，前中后序，表示的是節(jié)點與它的左右子樹節(jié)點遍歷訪問的先后順序。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 想學(xué)好前端，先練好內(nèi)功，內(nèi)功不行，...
摘要：原文博客地址學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)四樹知乎專欄簡書專題前端進擊者知乎前端進擊者簡書博主博客地址的個人博客人之所能，不能兼?zhèn)洌瑮壠渌?，取其所長。通常子樹被稱作左子樹和右子樹。敬請期待數(shù)據(jù)結(jié)構(gòu)篇最后一篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)五圖參考文章樹數(shù)據(jù)結(jié)構(gòu)二叉樹 前言 總括： 本文講解了數(shù)據(jù)結(jié)構(gòu)中的[樹]的概念，盡可能通俗易懂的解釋樹這種數(shù)據(jù)結(jié)構(gòu)的概念，使用javascript實現(xiàn)了樹，如有紕漏，歡迎批評指正。 ...
摘要：因此，根據(jù)題目給出的先序遍歷和中序遍歷，可以畫出二叉樹選參考數(shù)據(jù)結(jié)構(gòu)與算法描述實現(xiàn)二叉樹算法淺談數(shù)據(jù)結(jié)構(gòu)二叉樹慕課網(wǎng)實現(xiàn)二叉樹算法前端樹控件騰訊軟件開發(fā)面試題 內(nèi)容銜接上一章 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法 內(nèi)容提要 什么是樹 - 為什么使用樹 二叉樹 二叉查找樹 紅黑樹 Ｂ、Ｂ＋樹 堆 伸展樹 樹 可以點擊鏈接感受下筆者用d3.js畫的tree https://codepen...
摘要：二叉查找樹二叉查找樹也叫二叉搜索樹它只允許我們在左節(jié)點存儲比父節(jié)點更小的值，右節(jié)點存儲比父節(jié)點更大的值，上圖展示的就是一顆二叉查找樹。 前兩天接到了螞蟻金服的面試電話，面試官很直接，上來就拋出了三道算法題。。。 其中有一道關(guān)于二叉樹實現(xiàn)中序遍歷的，當(dāng)時沒回答好，所以特意學(xué)習(xí)了一把二叉樹的知識，行文記錄總結(jié)。 二叉樹&二叉查找樹 showImg(https://segmentfault....
閱讀 3167·2021-11-22 09:34
閱讀 2806·2021-09-22 15:28
閱讀 835·2021-09-10 10:51
閱讀 1865·2019-08-30 14:22
閱讀 2332·2019-08-30 14:17
閱讀 2746·2019-08-30 11:01
閱讀 2306·2019-08-29 17:19
閱讀 3674·2019-08-29 13:17
