JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹(shù)遍歷算法詳解【先序、中序、后序】
更新時(shí)間：2019年02月21日 14:17:06 作者：白楊-M
這篇文章主要介紹了JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹(shù)遍歷算法,結(jié)合實(shí)例形式詳細(xì)分析了javascript二叉樹(shù)的定義及先序遍歷、中序遍歷、后序遍歷等相關(guān)遍歷操作實(shí)現(xiàn)技巧,需要的朋友可以參考下
本文實(shí)例講述了JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹(shù)遍歷算法。分享給大家供大家參考，具體如下：
javascript數(shù)據(jù)結(jié)構(gòu)與算法--二叉樹(shù)遍歷（先序）
先序遍歷先訪(fǎng)問(wèn)根節(jié)點(diǎn)， 然后以同樣方式訪(fǎng)問(wèn)左子樹(shù)和右子樹(shù)
代碼如下：
/*
*二叉樹(shù)中，相對(duì)較小的值保存在左節(jié)點(diǎn)上，較大的值保存在右節(jié)點(diǎn)中
*
*
* */
/*用來(lái)生成一個(gè)節(jié)點(diǎn)*/
function Node(data, left, right) {
this.data = data;//節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)
this.left = left;
this.right = right;
this.show = show;
}
function show() {
return this.data;
}
/*用來(lái)生成一個(gè)二叉樹(shù)*/
function BST() {
this.root = null;
this.insert = insert;
}
/*將數(shù)據(jù)插入二叉樹(shù)
（1）設(shè)根節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)。
（2）如果待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)；反
之，執(zhí)行第4步。
（3）如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù)
執(zhí)行下一次循環(huán)。
（4）設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的右節(jié)點(diǎn)。
（5）如果當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù)
執(zhí)行下一次循環(huán)。
* */
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;//待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)
if (current == null) {//如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù)執(zhí)行下一次while循環(huán)。
parent.left = n;
break;
}
}
else {
current = current.right;//待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)
if (current == null) {
parent.right = n;
break;
}
}
}
}
}
/*先序遍歷
*用遞歸的方法
*/
function preOrder(node) {
if (!(node == null)) {
console.log(node.show() + " ");
preOrder(node.left);
preOrder(node.right);
}
}
/* 測(cè)試代碼 */
var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
console.log("先序遍歷: ");
preOrder(nums.root);
運(yùn)行結(jié)果：
javascript數(shù)據(jù)結(jié)構(gòu)與算法--二叉樹(shù)遍歷（中序）
中序遍歷按照節(jié)點(diǎn)上的鍵值，以升序訪(fǎng)問(wèn)BST上的所有節(jié)點(diǎn)
代碼如下：
/*
*二叉樹(shù)中，相對(duì)較小的值保存在左節(jié)點(diǎn)上，較大的值保存在右節(jié)點(diǎn)中
*
*
* */
/*用來(lái)生成一個(gè)節(jié)點(diǎn)*/
function Node(data, left, right) {
this.data = data;//節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)
this.left = left;
this.right = right;
this.show = show;
}
function show() {
return this.data;
}
/*用來(lái)生成一個(gè)二叉樹(shù)*/
function BST() {
this.root = null;
this.insert = insert;
}
/*將數(shù)據(jù)插入二叉樹(shù)
（1）設(shè)根節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)。
（2）如果待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)；反
之，執(zhí)行第4步。
（3）如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù)
執(zhí)行下一次循環(huán)。
（4）設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的右節(jié)點(diǎn)。
（5）如果當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù)
執(zhí)行下一次循環(huán)。
* */
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;//待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)
if (current == null) {//如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù)執(zhí)行下一次while循環(huán)。
parent.left = n;
break;
}
}
else {
current = current.right;//待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)
if (current == null) {
parent.right = n;
break;
}
}
}
}
}
/*中序遍歷
*用遞歸的方法
*/
function inOrder(node) {
if (!(node == null)) {
inOrder(node.left);
console.log(node.show() + " ");
inOrder(node.right);
}
}
/* 測(cè)試代碼 */
var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
console.log("中序遍歷: ");
inOrder(nums.root);
運(yùn)行結(jié)果：
javascript數(shù)據(jù)結(jié)構(gòu)與算法--二叉樹(shù)遍歷（后序）
后序遍歷先訪(fǎng)問(wèn)葉子節(jié)點(diǎn)，從左子樹(shù)到右子樹(shù)，再到根節(jié)點(diǎn)。
/*
*二叉樹(shù)中，相對(duì)較小的值保存在左節(jié)點(diǎn)上，較大的值保存在右節(jié)點(diǎn)中
*
*
* */
/*用來(lái)生成一個(gè)節(jié)點(diǎn)*/
function Node(data, left, right) {
this.data = data;//節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)
this.left = left;
this.right = right;
this.show = show;
}
function show() {
return this.data;
}
/*用來(lái)生成一個(gè)二叉樹(shù)*/
function BST() {
this.root = null;
this.insert = insert;
}
/*將數(shù)據(jù)插入二叉樹(shù)
（1）設(shè)根節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)。
（2）如果待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)；反
之，執(zhí)行第4步。
（3）如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù)
執(zhí)行下一次循環(huán)。
（4）設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的右節(jié)點(diǎn)。
（5）如果當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù)
執(zhí)行下一次循環(huán)。
* */
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;//待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)
if (current == null) {//如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù)執(zhí)行下一次while循環(huán)。
parent.left = n;
break;
}
}
else {
current = current.right;//待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)
if (current == null) {
parent.right = n;
break;
}
}
}
}
}
/*后序遍歷
*用遞歸的方法
*/
function postOrder(node) {
if (!(node == null)) {
postOrder(node.left);
postOrder(node.right);
console.log(node.show() + " ");
}
}
/* 測(cè)試代碼 */
var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
console.log("后序遍歷: ");
postOrder(nums.root);
運(yùn)行結(jié)果：
感興趣的朋友可以使用在線(xiàn)HTML/CSS/JavaScript代碼運(yùn)行工具：http://tools.jb51.net/code/HtmlJsRun測(cè)試上述代碼運(yùn)行效果。
更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題：《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》
希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。
相關(guān)文章
當(dāng)達(dá)到輸入長(zhǎng)度時(shí)表單自動(dòng)切換焦點(diǎn)
給每個(gè)字段限制輸入長(zhǎng)度，當(dāng)達(dá)到輸入長(zhǎng)度時(shí)自動(dòng)切換焦點(diǎn)，以增強(qiáng)表單的易用性,需要的朋友可以參考下2014-04-04
Taro小程序自定義頂部導(dǎo)航欄功能的實(shí)現(xiàn)
這篇文章主要介紹了Taro小程序自定義頂部導(dǎo)航欄功能的實(shí)現(xiàn),本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-12-12
JavaScript實(shí)現(xiàn)點(diǎn)擊自動(dòng)選擇TextArea文本的方法
這篇文章主要介紹了JavaScript實(shí)現(xiàn)點(diǎn)擊自動(dòng)選擇TextArea文本的方法,涉及javascript中focus()、select()方法的使用技巧,非常簡(jiǎn)單實(shí)用,需要的朋友可以參考下2015-07-07
獲取焦點(diǎn)時(shí),利用js定時(shí)器設(shè)定時(shí)間執(zhí)行動(dòng)作
網(wǎng)上有很多類(lèi)似的知識(shí)，并不是有什么難度的技巧，僅僅是開(kāi)發(fā)過(guò)程中的一點(diǎn)點(diǎn)積累而已。2010-04-04
這篇文章主要介紹了Js類(lèi)的構(gòu)建與繼承案例詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-09-09
微信小程序?qū)崿F(xiàn)購(gòu)物車(chē)功能
這篇文章主要為大家詳細(xì)介紹了微信小程序?qū)崿F(xiàn)購(gòu)物車(chē)功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-11-11
ajax提交并返回xml的實(shí)現(xiàn)代碼2008-11-11
javascript動(dòng)態(tài)生成樹(shù)形菜單的方法
這篇文章主要介紹了javascript動(dòng)態(tài)生成樹(shù)形菜單的方法,涉及JavaScript針對(duì)頁(yè)面元素與屬性的動(dòng)態(tài)操作技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-11-11
我見(jiàn)過(guò)最全的個(gè)人js加解密功能頁(yè)面
利用js進(jìn)行加解密是我們經(jīng)常會(huì)遇到的一個(gè)功能，本文給大家介紹的是我目前見(jiàn)到的最全的個(gè)人js加解密功能頁(yè)面，分享出來(lái)供大家參考學(xué)習(xí)，需要的朋友們隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2007-12-12
這篇文章主要為大家介紹了Three.js?PBR物理渲染屬性及使用介紹，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-04-04