定義
- 二叉樹
二叉樹在圖論中是這樣定義的：二叉樹是一個連通的無環(huán)圖沃于，并且每一個頂點的度不大于3乍构。有根二叉樹還要滿足根結(jié)點的度不大于2。有了根結(jié)點之后汁针，每個頂點定義了唯一的父結(jié)點干签，和最多2個子結(jié)點津辩。然而，沒有足夠的信息來區(qū)分左結(jié)點和右結(jié)點容劳。如果不考慮連通性喘沿，允許圖中有多個連通分量，這樣的結(jié)構(gòu)叫做森林竭贩。
- 二叉查找樹
二叉排序樹或者是一棵空樹蚜印，或者是具有下列性質(zhì)的二叉樹：
（1）若左子樹不空，則左子樹上所有結(jié)點的值均小于或等于它的根結(jié)點的值娶视；
（2）若右子樹不空晒哄，則右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值睁宰；
（3）左、右子樹也分別為二叉排序樹寝凌；
實現(xiàn)二叉查找樹
BST 的基本方法
要實現(xiàn)二叉查找樹柒傻，首先實現(xiàn) Node 類，Node 類定義如下：
function Node(data, left, right) {
this.data = data;
this.left = left;
this.right = right;
this.show = show;
}
我們可以定義一個二叉查找樹類（BST）如下：
// BST類
function BST() {
this.root = null;
this.insert = insert; // 插入數(shù)據(jù)方法
}
接著我們實現(xiàn)一個 insert 方法较木，實現(xiàn)這個方法的思路：
首先檢查 BST 是否有根節(jié)點红符，如果沒有，則這是一個新樹伐债，這個需要插入的數(shù)據(jù)就成為了根節(jié)點预侯，這個方法就完成了；否則峰锁，進入下一步萎馅。
設(shè)置根節(jié)點為當(dāng)前節(jié)點。
如果待插入數(shù)據(jù)小于當(dāng)前節(jié)點的數(shù)據(jù)虹蒋，則設(shè)置新的當(dāng)前節(jié)點為原節(jié)點的左節(jié)點糜芳；反之，執(zhí)行第4步魄衅。
如果當(dāng)前節(jié)點的左節(jié)點為null峭竣，那么就將新的節(jié)點插入這個位置，退出循環(huán)晃虫；反之皆撩，繼續(xù)執(zhí)行下一次循環(huán)。
設(shè)置新的當(dāng)前節(jié)點為原節(jié)點的右節(jié)點哲银。
如果當(dāng)前節(jié)點的右節(jié)點為null扛吞，那么就將新的節(jié)點插入這個位置，退出循環(huán)盘榨；反之喻粹，繼續(xù)執(zhí)行下一次循環(huán)。
所以草巡，我們現(xiàn)在可以實現(xiàn) insert 方法如下：
function insert(data) {
var n = new Node(data, null, null);
var parent;
if(this.root == null) {
this.root = n;
} else {
while(true) {
parent = current;
if (data < current.data ) {
current = current.left;
if (!current) {
parent.left = n;
break;
}
} else {
current = current.right;
if (!current) {
parent.right = n;
break;
}
}
}
}
}
遍歷二叉查找樹
BST 類目前已經(jīng)初步成型，我們已經(jīng)可以插入數(shù)據(jù)型酥，現(xiàn)在我們還需要有能力遍歷
BST 山憨， 我們有三種遍歷 BST 的方式： 中序、先序和后序弥喉。
前序遍歷：根節(jié)點->左子樹->右子樹
中序遍歷：左子樹->根節(jié)點->右子樹
后序遍歷：左子樹->右子樹->根節(jié)點
則 BST 類現(xiàn)在可以寫成如下：
// BST類
function BST() {
this.root = null;
this.insert = insert; // 插入數(shù)據(jù)方法
this.inOrder = inOrder; // 中序遍歷
this.preOrder = preOrder; // 先序遍歷
this.postOrder = postOrder; // 后序遍歷
}
現(xiàn)在我們首先實現(xiàn)中序遍歷方法如下：
function inOrder(node) {
if(node) {
inOrder(node.left);
console.log(node.show() + " ");
inOrder(node.right);
}
}
先序遍歷如下：
// 先序遍歷
function preOrder (node) {
if (node) {
console.log(node.show()+"");
preOrder(node.left);
preOrder(node.right);
}
}
后序遍歷如下：
// 后序遍歷
function postOrder(node) {
if (node) {
postOrder(node.left);
postOrder(node.right);
console.log(node.show()+"");
}
}
