樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，以分層的方式存儲(chǔ)數(shù)據(jù)。樹被用來(lái)存儲(chǔ)具有層級(jí)關(guān)系的結(jié)構(gòu)芦圾，比如文件系統(tǒng)中的文件；樹還被用來(lái)存儲(chǔ)有序列表俄认。
二叉樹與二叉查找樹
二叉樹是一種特殊的樹个少，它的子節(jié)點(diǎn)個(gè)數(shù)不超過(guò)兩個(gè)；一個(gè)父節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)分別稱為左節(jié)點(diǎn)和右節(jié)點(diǎn)眯杏。
二叉查找樹(BST)是一種特殊的二叉樹夜焦；相對(duì)較小的值保持在左節(jié)點(diǎn)中，較大的值保存在右節(jié)點(diǎn)中役拴。js代碼實(shí)現(xiàn)二叉查找樹
- 首先我們先定義一個(gè)Node對(duì)象糊探，用于保存數(shù)據(jù)(data)，也保存和其他節(jié)點(diǎn)的鏈接（left和right）河闰。
function Node(data,left,right) {
this.data = data;
this.left = left;
this.right = right;
this.show = show;
}
- 定義show方法
function show() {
return this.data;
}
- 創(chuàng)建一個(gè)類，用來(lái)表示二叉查找樹(BST)
function BST() {
//將根節(jié)點(diǎn)初始化為null
this.root = null;
//insert方法用來(lái)向樹中加入新節(jié)點(diǎn)
this.insert = insert;
//inOrder方法用來(lái)遍歷樹
this.inOrder = inOrder;
}
- 定義insert方法
function insert(data) {
//首先實(shí)例化一個(gè)新的Node對(duì)象
var n = new Node(data,null,null);
//檢查BST是否有根節(jié)點(diǎn)褥紫，如果沒(méi)有姜性，那么是顆新樹，傳入的該節(jié)點(diǎn)就是根節(jié)點(diǎn)
if(this.root == null) {
this.root = n;
}else {
//反之就定義一個(gè)current變量用于保存當(dāng)前節(jié)點(diǎn)（根節(jié)點(diǎn)）
var current = this.root;
var parent;
while(true) {
parent = current;
//如果插入的節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)髓考，且當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為null部念，就將這個(gè)新的節(jié)點(diǎn)插入到這個(gè)位置
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;
}
}
}
}
}
- 遍歷二叉查找樹
有三種遍歷BST的方式
中序：中序遍歷按照節(jié)點(diǎn)上的鍵值氨菇，以升序訪問(wèn)BST上的所有節(jié)點(diǎn)儡炼。
先序：先序遍歷先訪問(wèn)根節(jié)點(diǎn)，然后以同樣的方式訪問(wèn)左子樹和右子樹查蓉。
后序：后序遍歷先訪問(wèn)葉子節(jié)點(diǎn)(沒(méi)有任何子節(jié)點(diǎn)的節(jié)點(diǎn))乌询，從左子樹到右子樹，再到根節(jié)點(diǎn)豌研。
這三種遍歷理解了一種的實(shí)現(xiàn)代碼妹田，其他的都好理解，所以我著重寫一下我對(duì)js代碼實(shí)現(xiàn)中序遍歷過(guò)程的具體理解鹃共。
- js代碼實(shí)現(xiàn)中序遍歷
中序遍歷使用遞歸的方式鬼佣，以升序訪問(wèn)樹中所有節(jié)點(diǎn)，先訪問(wèn)左子樹霜浴，在訪問(wèn)根節(jié)點(diǎn)晶衷，最后訪問(wèn)右子樹。
function inOrder(node) {
if(!(node == null)) {
inOrder(node.left);
console.log(node.show());
inOrder(node.right);
}
}
//比如：
var nums = new BST();
nums.insert(56);
nums.insert(22);
nums.insert(81);
nums.insert(10);
nums.insert(30);
nums.insert(77);
nums.insert(92);
inOrder(nums.root); //10 22 30 56 81 77 92
①先遞歸遍歷左子樹到盡頭，將每一項(xiàng)push到一個(gè)數(shù)組中晌纫，先是得到這樣的一個(gè)結(jié)果[56,22,10]税迷。
②遞歸完成了，現(xiàn)在pop出第一項(xiàng)即10開始遍歷右子樹,為undefined缸匪。
③然后pop出第二項(xiàng)即22翁狐，遍歷右子樹，得30凌蔬，因?yàn)閏onsole是在先遞歸左子樹后打印的露懒，所以把30插到(push)56和22中間，結(jié)果為[56,30,22,10]砂心。
④然后pop出第三項(xiàng)即30懈词，undefined。
⑤然后pop出第四項(xiàng)即56辩诞，遍歷該右子樹坎弯，得結(jié)果[92,81,56,30,22,10]
⑥然后pop出第五項(xiàng)即81，發(fā)現(xiàn)有左子樹77译暂，所以push進(jìn)去抠忘，又因?yàn)閏onsole代碼在中間，所以要放到92和81中間外永，結(jié)果[92,81,77,56,30,22,10]所以最后打印結(jié)果為10,22,30,56,77,81,92
理解了一個(gè)崎脉，后面的先序遍歷和后序遍歷就沒(méi)問(wèn)題了，只是console代碼放置的位置不同伯顶。主要是理解遞歸囚灼。
- 先序遍歷
function inOrder(node) {
if(!(node == null)) {
console.log(node.show());
inOrder(node.left);
inOrder(node.right);
}
}
inOrder(nums.root);
- 后序遍歷
function inOrder(node) {
if(!(node == null)) {
inOrder(node.left);
inOrder(node.right);
console.log(node.show());
}
}
inOrder(nums.root);
參考學(xué)習(xí)：
《數(shù)據(jù)結(jié)構(gòu)與算法JavaScript描述》
《高程》
