前言：

成都一家集口碑和實力的網(wǎng)站建設(shè)服務(wù)商，擁有專業(yè)的企業(yè)建站團隊和靠譜的建站技術(shù)，十年企業(yè)及個人網(wǎng)站建設(shè)經(jīng)驗 ,為成都近1000家客戶提供網(wǎng)頁設(shè)計制作,網(wǎng)站開發(fā),企業(yè)網(wǎng)站制作建設(shè)等服務(wù),包括成都營銷型網(wǎng)站建設(shè)，成都品牌網(wǎng)站建設(shè)，同時也為不同行業(yè)的客戶提供成都網(wǎng)站建設(shè)、成都做網(wǎng)站的服務(wù),包括成都電商型網(wǎng)站制作建設(shè),裝修行業(yè)網(wǎng)站制作建設(shè)，傳統(tǒng)機械行業(yè)網(wǎng)站建設(shè),傳統(tǒng)農(nóng)業(yè)行業(yè)網(wǎng)站制作建設(shè)。在成都做網(wǎng)站,選網(wǎng)站制作建設(shè)服務(wù)商就選成都創(chuàng)新互聯(lián)公司。

緊接著上篇 二叉樹的javascript實現(xiàn) ，來說一下二叉樹的遍歷。

本次一本正經(jīng)的胡說八道，以以下這個二叉樹為例子進行遍歷：

接著是要引入二叉樹實現(xiàn)的代碼：

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;
      }
     }
   }
  }
}

二叉樹遍歷的分類

二叉樹的遍歷分為先序、中序、后序遍歷。這里說到的先序、中序、后序是相對于父節(jié)點來說。父節(jié)點的值先輸出就是先序，三者間它在中間輸出就是中序，最后輸出就是后序。至于那個是父節(jié)點是相對而言的，因為除了葉子節(jié)點（最底下一層節(jié)點），其他每個節(jié)點都可以是父節(jié)點。

先序遍歷

先序遍歷就是，先打印父節(jié)點，然后是左子節(jié)點（左子樹），然后再打印右子節(jié)點（子樹）。

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函數(shù)是遞歸實現(xiàn)的，應(yīng)該說二叉樹的遍歷都是遞歸實現(xiàn)的。可能有些人會因為先序遍歷的特征：“先打印父節(jié)點，然后是左子節(jié)點（左子樹），然后再打印右子節(jié)點（子樹）” 而陷入一個錯誤的想法，這想法是什么請看下圖：

注意紅框部分，父節(jié)點是10，左子節(jié)點是3，右子節(jié)點是18，因為上面的結(jié)論，可能會錯誤地認為打印的順序是10 → 3 → 18，然而事實并非如此[捂臉]，真是的順序是：先打印10，然后是打印左子樹，打印完左子樹的全部節(jié)點后，才開始打印以10位父節(jié)點的右子樹：

這個時候，你的腦海就該這樣想：

然后是這樣想：

如此類推打印完以10為父節(jié)點的左子樹，然后也是以這樣的方式打印以10為父節(jié)點的右子樹，按著這種 拆分代替的思想 來理解會更好明白二叉樹的遍歷。

然后最終，先序遍歷改二叉樹的順序是：

按圖的輸出順序是：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);

這里強調(diào)一下，輸出順序和插入順序有關(guān)的，因為你插入順序不同生成的二叉樹也是不同的。有疑問的可以去 二叉樹的javascript實現(xiàn) 細看一下，有比較明白的說明了二叉樹，也可以實驗一下：

中序遍歷

看完先序遍歷，已經(jīng)可以類推到很多和中序、后序遍歷相關(guān)的知識點。中序遍歷的特征是：先打印左子樹（左子節(jié)點），接著打印父節(jié)點，最后打印右子樹（右子節(jié)點）。

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

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持創(chuàng)新互聯(lián)。

標題名稱：javascript實現(xiàn)二叉樹遍歷的代碼
文章地址：http://vcdvsql.cn/article40/pehdho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站營銷、品牌網(wǎng)站設(shè)計、虛擬主機、小程序開發(fā)、搜索引擎優(yōu)化、全網(wǎng)營銷推廣

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)