JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹遍歷算法詳解【先序、中序、后序】

2019-11-19 12:05:10

字體：大中小

供稿：網(wǎng)友

本文實(shí)例講述了JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹遍歷算法。分享給大家供大家參考，具體如下：

javascript數(shù)據(jù)結(jié)構(gòu)與算法--二叉樹遍歷（先序）

先序遍歷先訪問根節(jié)點(diǎn)，然后以同樣方式訪問左子樹和右子樹

代碼如下：

/* *二叉樹中，相對(duì)較小的值保存在左節(jié)點(diǎn)上，較大的值保存在右節(jié)點(diǎn)中 * * * *//*用來生成一個(gè)節(jié)點(diǎn)*/function Node(data, left, right) {  this.data = data;//節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)  this.left = left;  this.right = right;  this.show = show;}function show() {  return this.data;}/*用來生成一個(gè)二叉樹*/function BST() {  this.root = null;  this.insert = insert;}/*將數(shù)據(jù)插入二叉樹 （1）設(shè)根節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)。 （2）如果待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)；反 之，執(zhí)行第4步。 （3）如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù) 執(zhí)行下一次循環(huán)。 （4）設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的右節(jié)點(diǎn)。 （5）如果當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù) 執(zhí)行下一次循環(huán)。 * */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;//待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)        if (current == null) {//如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù)執(zhí)行下一次while循環(huán)。          parent.left = n;          break;        }      }      else {        current = current.right;//待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)        if (current == null) {          parent.right = n;          break;        }      }    }  }}/*先序遍歷 *用遞歸的方法 */function preOrder(node) {  if (!(node == null)) {    console.log(node.show() + " ");    preOrder(node.left);    preOrder(node.right);  }}/* 測(cè)試代碼 */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);

運(yùn)行結(jié)果：

javascript數(shù)據(jù)結(jié)構(gòu)與算法--二叉樹遍歷（中序）

中序遍歷按照節(jié)點(diǎn)上的鍵值，以升序訪問BST上的所有節(jié)點(diǎn)

代碼如下：

/* *二叉樹中，相對(duì)較小的值保存在左節(jié)點(diǎn)上，較大的值保存在右節(jié)點(diǎn)中 * * * *//*用來生成一個(gè)節(jié)點(diǎn)*/function Node(data, left, right) {  this.data = data;//節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)  this.left = left;  this.right = right;  this.show = show;}function show() {  return this.data;}/*用來生成一個(gè)二叉樹*/function BST() {  this.root = null;  this.insert = insert;}/*將數(shù)據(jù)插入二叉樹 （1）設(shè)根節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)。 （2）如果待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)；反 之，執(zhí)行第4步。 （3）如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù) 執(zhí)行下一次循環(huán)。 （4）設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的右節(jié)點(diǎn)。 （5）如果當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù) 執(zhí)行下一次循環(huán)。 * */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;//待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)        if (current == null) {//如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù)執(zhí)行下一次while循環(huán)。          parent.left = n;          break;        }      }      else {        current = current.right;//待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)        if (current == null) {          parent.right = n;          break;        }      }    }  }}/*中序遍歷*用遞歸的方法*/function inOrder(node) {  if (!(node == null)) {    inOrder(node.left);    console.log(node.show() + " ");    inOrder(node.right);  }}/* 測(cè)試代碼 */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);

運(yùn)行結(jié)果：

javascript數(shù)據(jù)結(jié)構(gòu)與算法--二叉樹遍歷（后序）

后序遍歷先訪問葉子節(jié)點(diǎn)，從左子樹到右子樹，再到根節(jié)點(diǎn)。

/* *二叉樹中，相對(duì)較小的值保存在左節(jié)點(diǎn)上，較大的值保存在右節(jié)點(diǎn)中 * * * *//*用來生成一個(gè)節(jié)點(diǎn)*/function Node(data, left, right) {  this.data = data;//節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)  this.left = left;  this.right = right;  this.show = show;}function show() {  return this.data;}/*用來生成一個(gè)二叉樹*/function BST() {  this.root = null;  this.insert = insert;}/*將數(shù)據(jù)插入二叉樹 （1）設(shè)根節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)。 （2）如果待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)；反 之，執(zhí)行第4步。 （3）如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù) 執(zhí)行下一次循環(huán)。 （4）設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的右節(jié)點(diǎn)。 （5）如果當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù) 執(zhí)行下一次循環(huán)。 * */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;//待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)        if (current == null) {//如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為null，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù)執(zhí)行下一次while循環(huán)。          parent.left = n;          break;        }      }      else {        current = current.right;//待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)        if (current == null) {          parent.right = n;          break;        }      }    }  }}/*后序遍歷 *用遞歸的方法 */function postOrder(node) {  if (!(node == null)) {    postOrder(node.left);    postOrder(node.right);    console.log(node.show() + " ");  }}/* 測(cè)試代碼 */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);

運(yùn)行結(jié)果：