javascript實現(xiàn)二叉樹的代碼
更新時間：2017年06月08日 11:25:57 作者：issac_寶華
本篇文章主要介紹了javascript實現(xiàn)二叉樹的代碼，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
前言：
二叉樹的特點(例圖只是二叉樹的一種情況，不要嘗試用例圖推理以下結論)
- 除了最下面一層，每個節(jié)點都是父節(jié)點，每個節(jié)點都有且最多有兩個子節(jié)點；
- 除了嘴上面一層，每個節(jié)點是子節(jié)點，每個節(jié)點都會有一個父節(jié)點；
- 最上面一層的節(jié)點（即例圖中的節(jié)點50）為根節(jié)點；
最下面一層的節(jié)點稱為葉子節(jié)點，他們沒有子節(jié)點；
左子節(jié)點的值 < 父節(jié)點的值 <= 右節(jié)點的值
1 節(jié)點的javascript實現(xiàn)
// 節(jié)點對象
function Node(data, left, right) {
this.data = data; // 節(jié)點值
this.left = left; // 當前節(jié)點的左子節(jié)點
this.right = right; // 當前節(jié)點的右子節(jié)點
this.show = show; // 輔助function
}
function show() {
return this.data;
}
感受下上面實現(xiàn)節(jié)點的代碼，感覺和鏈表有點相似不是嗎，存著當前值，又存著下個節(jié)點（左、右子節(jié)點）的引用，下面是一張偽代碼的草圖：
2 二叉樹的實現(xiàn)
實現(xiàn)二叉樹，當然就是要插入節(jié)點構成二叉樹，先看看實現(xiàn)二叉樹的js代碼
function BST() {
this.root = null;
this.insert = insert;
}
function insert(data) {
var n = new Node(data, null, null);
if (this.root == null) {
this.root = n;
}
else {
var current = this.root;
var parent;
while (true) {
parent = current;
if (data < current.data) {
current = current.left;
if (current == null) {
parent.left = n;
break;
}
}
else {
current = current.right;
if (current == null) {
parent.right = n;
break;
}
}
}
}
}
然后是看一下偽代碼：
function BST() {
this.root = null; // 根節(jié)點
this.insert = insert;
}
function insert(data) {
// 初始化一個節(jié)點，為什么要將左右子節(jié)點的引用初始化為空呢，因為可能是葉子節(jié)點，加入他有子節(jié)點，會在下面的代碼添加
var n = new Node(data, null, null);
if (該二叉樹是否為空，是空則根節(jié)點為空，因此可以用根節(jié)點判斷二叉樹是否為空) {
// 將當前節(jié)點存為根節(jié)點
this.root = n;
}
else {
// 來到這里就表示，該二叉樹不為空，這里關鍵的是兩句代碼：
// 0.while (true);
// 1.parent = current；
// 2.current = current.left;/current = current.right;
// 3.break;
var current = this.root;
var parent;
while (true) {
parent = current; // 獲得父節(jié)點，第一次循環(huán)，那么父節(jié)點就是根節(jié)點
if (data < current.data) { // 當前節(jié)點值小于父節(jié)點的值就是存左邊，記得二叉樹的特點吧，如果真是小于父節(jié)點，那么就說明該節(jié)點屬于，該父節(jié)點的左子樹。
current = current.left;
if (current == null) {
parent.left = n;
break;
}
// 其實上面這樣寫不好理解，可以等價于下面的代碼：
// start
if(current.left == null){ // 若果左節(jié)點空，那么這個空的節(jié)點就是我們要插入的位置
current.left = n;
break;
}else{
// 不空則繼續(xù)往下一層找空節(jié)點（插入的位置）
current = current.left;
}
// end
}
else {
// 右節(jié)點的邏輯代碼個左節(jié)點的一樣的
current = current.right;
if (current == null) {
parent.right = n;
break;
}
}
}
}
}
下面是一個更好理解的插入函數(shù)
function insert(data) {
var n = new Node(data, null, null);
if (this.root == null) {
this.root = n;
}
else {
var current = this.root;
// start change
while (true) {
if (data < current.data) {
if (current.left == null) {
current.left = n;
break;
}else{
current = current.left;
}
}else {
if (current.right == null) {
current.right = n;
break;
}else{
current = current.right;
}
}
}
}
}
小結：
二叉樹的實現(xiàn)的三個部件
Node對象
function Node(data, left, right) { ... }
BST對象
function BST() { ... }
插入節(jié)點函數(shù)
function insert(data) { ... }
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
最近在移動端上面看到不同于菊花圖的加載方式，就是這篇文章需要分享的Skeleton Screen，中文稱之為"骨架屏"，下面我們來簡單了解一下吧2019-05-05
下面小編就為大家?guī)硪黄猨s 獲取經緯度的實現(xiàn)方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-06-06
比較了下Bootstrap的popover和一些其它的開源項目，覺得Bootstrap的還算不錯。在使用過程中遇到了一系列問題，下面小編給大家分享Bootstrap彈出框（Popover）被擠壓的問題小結，需要的朋友參考下吧2017-07-07
這篇文章主要介紹了微信小程序學習筆記之目錄結構、基本配置,結合實例形式詳細分析了微信小程序的相關注冊、配置及基本使用方法,并配以圖片加以說明,需要的朋友可以參考下2019-03-03
在使用try catch處理iframe跨域產生的異常時，chrome和safari瀏覽器似乎不能正常運作：他們直接拋出了錯誤而沒有拋出可供JS截獲的異常。2011-09-09
通過JS的事件循環(huán)機制,可以更清楚JS代碼的執(zhí)行流,下面這篇文章主要給大家介紹了關于如何通過一篇文章讓你搞清楚JavaScript事件循環(huán)的相關資料,需要的朋友可以參考下2022-06-06
使用Axios函數(shù)庫進行網(wǎng)絡請求的操作指南
在現(xiàn)代的前端開發(fā)中,API調用是實現(xiàn)前后端數(shù)據(jù)交互的重要環(huán)節(jié),而在眾多的HTTP庫中,Axios以其簡潔的語法、豐富的功能和易于擴展的特性,成為了開發(fā)者的首選,本篇文章將深入介紹Axios的使用方法,2024-11-11
這篇文章主要介紹了Javascript節(jié)點關系,實例分析了javascript操作父子節(jié)點及兄弟節(jié)點的相關技巧,需要的朋友可以參考下2015-05-05
這篇文章主要介紹了對JavaScript中this指針的新理解分享,本文講解了方法調用模式、函數(shù)調用模式、構造函數(shù)調用模式、Apply調用模式中的this指針理解,需要的朋友可以參考下2015-01-01
javascript跨域方法、原理以及出現(xiàn)問題解決方法（詳解）
javascript出于安全方面的考慮，不允許跨域調用其他頁面的對象。但是在安全限制的同時也給注入iframe或是ajax應用上帶來了不少麻煩?？缬蚝唵蔚睦斫饩褪且驗閖avascript同源策略的限制，a.com域名下的js無法操作b.com 或者是c.a.com域名下的對象2015-08-08