JavaScritp中二叉樹遍歷算法的示例分析

這篇文章主要為大家展示了“JavaScritp中二叉樹遍歷算法的示例分析”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“JavaScritp中二叉樹遍歷算法的示例分析”這篇文章吧。

具體如下：

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;
}
/*將數據插入二叉樹
 （1）設根節點為當前節點。
 （2）如果待插入節點保存的數據小于當前節點，則設新的當前節點為原節點的左節點；反
 之，執行第4步。
 （3）如果當前節點的左節點為null，就將新的節點插入這個位置，退出循環；反之，繼續
 執行下一次循環。
 （4）設新的當前節點為原節點的右節點。
 （5）如果當前節點的右節點為null，就將新的節點插入這個位置，退出循環；反之，繼續
 執行下一次循環。
 * */
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) {//如果當前節點的左節點為null，就將新的節點插入這個位置，退出循環；反之，繼續執行下一次while循環。
          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);
  }
}
/* 測試代碼 */
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);

運行結果：

javascript數據結構與算法--二叉樹遍歷（中序）

中序遍歷按照節點上的鍵值，以升序訪問BST上的所有節點

代碼如下：

/*
 *二叉樹中，相對較小的值保存在左節點上，較大的值保存在右節點中
 *
 *
 * */
/*用來生成一個節點*/
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;
}
/*將數據插入二叉樹
 （1）設根節點為當前節點。
 （2）如果待插入節點保存的數據小于當前節點，則設新的當前節點為原節點的左節點；反
 之，執行第4步。
 （3）如果當前節點的左節點為null，就將新的節點插入這個位置，退出循環；反之，繼續
 執行下一次循環。
 （4）設新的當前節點為原節點的右節點。
 （5）如果當前節點的右節點為null，就將新的節點插入這個位置，退出循環；反之，繼續
 執行下一次循環。
 * */
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) {//如果當前節點的左節點為null，就將新的節點插入這個位置，退出循環；反之，繼續執行下一次while循環。
          parent.left = n;
          break;
        }
      }
      else {
        current = current.right;//待插入節點保存的數據小于當前節點，則設新的當前節點為原節點的左節點
        if (current == null) {
          parent.right = n;
          break;
        }
      }
    }
  }
}
/*中序遍歷
*用遞歸的方法
*/
function inOrder(node) {
  if (!(node == null)) {
    inOrder(node.left);
    console.log(node.show() + " ");
    inOrder(node.right);
  }
}
/* 測試代碼 */
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);

運行結果：

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;
}
/*將數據插入二叉樹
 （1）設根節點為當前節點。
 （2）如果待插入節點保存的數據小于當前節點，則設新的當前節點為原節點的左節點；反
 之，執行第4步。
 （3）如果當前節點的左節點為null，就將新的節點插入這個位置，退出循環；反之，繼續
 執行下一次循環。
 （4）設新的當前節點為原節點的右節點。
 （5）如果當前節點的右節點為null，就將新的節點插入這個位置，退出循環；反之，繼續
 執行下一次循環。
 * */
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) {//如果當前節點的左節點為null，就將新的節點插入這個位置，退出循環；反之，繼續執行下一次while循環。
          parent.left = n;
          break;
        }
      }
      else {
        current = current.right;//待插入節點保存的數據小于當前節點，則設新的當前節點為原節點的左節點
        if (current == null) {
          parent.right = n;
          break;
        }
      }
    }
  }
}
/*后序遍歷
 *用遞歸的方法
 */
function postOrder(node) {
  if (!(node == null)) {
    postOrder(node.left);
    postOrder(node.right);
    console.log(node.show() + " ");
  }
}
/* 測試代碼 */
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);

運行結果：

以上是“JavaScritp中二叉樹遍歷算法的示例分析”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！