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) { ... }
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
javascript cookies 設置、讀取、刪除實例代碼
javascript cookies 存、取、刪除實例，也是不錯的文章，跟我們整理的有些補充。2010-04-04
這篇文章主要為大家詳細介紹了js仿京東放大鏡效果，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-08-08
highlight.js是一款輕量級的Web代碼語法高亮庫。下面通過實例代碼給大家分享JS庫之Highlight.js的用法詳解，感興趣的朋友跟隨腳本之家小編一起學習吧2017-09-09
這篇文章主要介紹了JS實現(xiàn)的Unicode編碼轉換操作,結合完整實例形式分析了javascript實現(xiàn)Unicode編碼轉換的具體操作技巧,需要的朋友可以參考下2017-04-04
這篇文章主要介紹了js圖片模糊切換顯示特效的方法,涉及js操作圖片特效的技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-02-02
這篇文章主要為大家介紹了webpack?loader使用的安裝配置詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-07-07
這篇文章主要介紹了基于JavaScript實現(xiàn)單例模式,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-10-10
今天組里的同事要寫一個屏保的效果，要求鼠標無操作N秒后進入屏幕保護，滑動鼠標的時候取消屏幕保護。我真是難倒了，糾結了半天，搞定了，下面給大家分享實現(xiàn)代碼2017-07-07
下面小編就為大家?guī)硪黄狫s 獲取、判斷瀏覽器版本信息的簡單方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-08-08
下面小編就為大家分享一篇js操作二進制數(shù)據(jù)方法，具有很好的參考價值，希望對的大家有所幫助。一起跟隨小編過來看看吧2018-03-03