本篇文章為大家介紹使用javascript實作二元樹的創建和遍歷的方法。有一定的參考價值，有需要的朋友可以參考一下，希望對大家有幫助。
1、先說二元樹的遍歷，遍歷方式：
前序遍歷：先遍歷根結點，然後左子樹，再右子樹
中序遍歷：先遍歷左子樹，然後根結點，再右子樹
後續遍歷：先遍歷左子樹，然後右子樹，再根結點
上程式碼：主要還是利用遞迴
function TreeCode() {
let BiTree = function (ele) {
this.data = ele;
this.lChild = null;
this.rChild = null;
}
this.createTree = function () {
let biTree = new BiTree('A');
biTree.lChild = new BiTree('B');
biTree.rChild = new BiTree('C');
biTree.lChild.lChild = new BiTree('D');
biTree.lChild.lChild.lChild = new BiTree('G');
biTree.lChild.lChild.rChild = new BiTree('H');
biTree.rChild.lChild = new BiTree('E');
biTree.rChild.rChild = new BiTree('F');
biTree.rChild.lChild.rChild = new BiTree('I');
return biTree;
}
}
//前序遍历
function ProOrderTraverse(biTree) {
if (biTree == null) return;
console.log(biTree.data);
ProOrderTraverse(biTree.lChild);
ProOrderTraverse(biTree.rChild);
}
//中序遍历
function InOrderTraverse(biTree) {
if (biTree == null) return;
InOrderTraverse(biTree.lChild);
console.log(biTree.data);
InOrderTraverse(biTree.rChild);
}
//后续遍历
function PostOrderTraverse(biTree) {
if (biTree == null) return;
PostOrderTraverse(biTree.lChild);
PostOrderTraverse(biTree.rChild);
console.log(biTree.data);
}
let myTree = new TreeCode();
console.log(myTree.createTree());
console.log('前序遍历')
ProOrderTraverse(myTree.createTree());
console.log('中序遍历')
InOrderTraverse(myTree.createTree());
console.log('后续遍历')
PostOrderTraverse(myTree.createTree());登入後複製
二元樹的非遞迴遍歷
##深度優先遍歷（主要利用堆疊的先進後出）
廣度優先遍歷（主要利用佇列的先進後出）
//深度优先非递归
function DepthFirstSearch(biTree) {
let stack = [];
stack.push(biTree);
while (stack.length != 0) {
let node = stack.pop();
console.log(node.data);
if (node.rChild) {
stack.push(node.rChild);
}
if (node.lChild) {
stack.push(node.lChild);
}
}
}
//广度优先非递归
function BreadthFirstSearch(biTree) {
let queue = [];
queue.push(biTree);
while (queue.length != 0) {
let node = queue.shift();
console.log(node.data);
if (node.lChild) {
queue.push(node.lChild);
}
if (node.rChild) {
queue.push(node.rChild);
}
}
}登入後複製
深度優先主要利用棧，先壓右子樹，再壓左子樹
#廣度優先主要利用隊列，先入左子樹，再入右子樹
深度優先的遍歷結果與前序遍歷相同ABDGHCEIF，廣度優先的遍歷結果是ABCDEFGHI
2、創建二叉樹
###1中創建二元樹的方式過於笨拙，假入我們根據完全二元樹的模型建立自己的二元樹，空資料的地方用#表示，如下圖所示我們稱之為擴展二元樹，我們取其前序遍歷的序列AB#D##C##。 ###############上程式碼：也是利用遞歸###
//前序遍历得到的字符串
let strArr = 'AB#D##C##'.split('');
function BiTree(ele) {
this.data = ele;
this.lChild = null;
this.rChild = null;
}
var newTree = new BiTree('#');
function createBiTree(biTree) {
if (strArr.length == 0) return;
let str = strArr.shift();
if (str == '#') return;
biTree.data = str;
if (strArr[0] != '#') {
biTree.lChild = new BiTree('#')
}
createBiTree(biTree.lChild);
if (strArr[0] != '#') {
biTree.rChild = new BiTree('#')
}
createBiTree(biTree.rChild);
}
createBiTree(newTree);
console.log(newTree);
ProOrderTraverse(newTree)登入後複製
###你也可以用中序遍歷或後序遍歷實作二元樹的創建，程式碼裡產生結點和建構左右子樹的程式碼順序交換一下就行了######推薦教學：《###JavaScript影片教學###》###
以上是javascript如何實作二元樹的創建與遍歷？ （程式碼範例）的詳細內容。更多資訊請關注PHP中文網其他相關文章！
