溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
前言：
緊接著上篇 二叉樹的javascript實現 ，來說一下二叉樹的遍歷。
本次一本正經的胡說八道，以以下這個二叉樹為例子進行遍歷：
接著是要引入二叉樹實現的代碼：
function Node(data, left, right) {
this.data = data;
this.left = left;
this.right = right;
this.show = show;
}
function show() {
return this.data;
}
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 preOrder(node) {
if (!(node == null)) {
console.log(node.show() + " ");
preOrder(node.left);
preOrder(node.right);
}
}
// 給BST類添加先序遍歷的成員方法
function BST() {
this.root = null;
this.insert = insert;
this.preOrder = preOrder;
}
preOrder函數是遞歸實現的，應該說二叉樹的遍歷都是遞歸實現的。可能有些人會因為先序遍歷的特征：“先打印父節點，然后是左子節點（左子樹），然后再打印右子節點（子樹）” 而陷入一個錯誤的想法，這想法是什么請看下圖：
注意紅框部分，父節點是10，左子節點是3，右子節點是18，因為上面的結論，可能會錯誤地認為打印的順序是10 → 3 → 18，然而事實并非如此[捂臉]，真是的順序是：先打印10，然后是打印左子樹，打印完左子樹的全部節點后，才開始打印以10位父節點的右子樹：
這個時候，你的腦海就該這樣想：
然后是這樣想：
如此類推打印完以10為父節點的左子樹，然后也是以這樣的方式打印以10為父節點的右子樹，按著這種 拆分代替的思想 來理解會更好明白二叉樹的遍歷。
然后最終，先序遍歷改二叉樹的順序是：
按圖的輸出順序是：10 -> 3 -> 2 -> 4 -> 9 -> 8 -> 9 -> 18 -> 13 -> 21
最后來實踐一下，先序遍歷：
var bst = new BST();
var nums = [10, 3, 18, 2, 4, 13, 21, 9, 8, 9];
for(var i = 0; i < nums.length; i++) {
bst.insert(nums[i]);
}
bst.preOrder(bst.root);
這里強調一下，輸出順序和插入順序有關的，因為你插入順序不同生成的二叉樹也是不同的。有疑問的可以去 二叉樹的javascript實現 細看一下，有比較明白的說明了二叉樹，也可以實驗一下：
中序遍歷
看完先序遍歷，已經可以類推到很多和中序、后序遍歷相關的知識點。中序遍歷的特征是：先打印左子樹（左子節點），接著打印父節點，最后打印右子樹（右子節點）。
function inOrder(node) {
if (!(node == null)) {
inOrder(node.left);
console.log(node.show() + " ");
inOrder(node.right);
}
}
// 給BST類添加該成員方法
function BST() {
this.root = null;
this.insert = insert;
this.preOrder = preOrder;
this.inOrder = inOrder;
}
中序遍歷的打印順序：
按上圖的輸出順序是：2 -> 3 -> 4 -> 8 -> 9 -> 9 -> 10 -> 13 -> 18 -> 21
接著是，實踐一下中序遍歷：
后序遍歷
function postOrder(node) {
if (!(node == null)) {
postOrder(node.left);
postOrder(node.right);
console.log(node.show() + " ");
}
}
// 給BST類添加該成員方法
function BST() {
this.root = null;
this.insert = insert;
this.preOrder = preOrder;
this.inOrder = inOrder;
this.postOrder = postOrder;
}
后序遍歷的打印順序
按上圖的輸出順序是：2 -> 8 -> 9 -> 9 -> 4 -> 3 -> 13 -> 21 -> 18 -> 10
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
