色婷婷狠狠18禁久久YY,CHINESE性内射高清国产,国产女人18毛片水真多1,国产AV在线观看

javascript中序遍歷

魏秀燕1年前6瀏覽0評論

在Javascript中,二叉樹是一種十分常見的數據結構,其中樹的遍歷是核心操作之一。對于二叉樹的遍歷,可以分為三種:先序遍歷、中序遍歷和后序遍歷。而其中序遍歷是指先訪問左子樹,再訪問根節點,最后訪問右子樹。本文將著重介紹Javascript中序遍歷的相關知識。

為了更好的理解中序遍歷,我們可以通過代碼來模擬一顆二叉樹。

/**
* 構造一個簡單的二叉樹
*         1
*       /   \
*      2     3
*     / \   / \
*    4   5 6   7
*/
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);

以上代碼中,我們構建了一顆包含七個節點的二叉樹。接下來我們來通過中序遍歷的方式,來遍歷這顆二叉樹。

/**
* 二叉樹中序遍歷
* @param {TreeNode} root
* @return {number[]}
*/
function inorderTraversal(root) {
var result = [];
var stack = [];
var node = root;
while(node || stack.length > 0) {
while(node) {
stack.push(node);
node = node.left;
}
node = stack.pop();
result.push(node.val);
node = node.right;
}
return result;
}
console.log(inorderTraversal(root)); // [4, 2, 5, 1, 6, 3, 7]

以上代碼中,我們定義了一個inorderTraversal函數,接收一顆二叉樹的根節點root,然后返回一個數組result,數組中包含了中序遍歷后的節點值。

接下來讓我們一步一步來看代碼中發生了什么。

首先定義了三個變量,result、stack和node,其中result是保存遍歷后的節點值的數組,stack是一個數組模擬的堆棧結構,node是要遍歷的當前節點。

var result = [];
var stack = [];
var node = root;

然后通過while循環不斷地循環遍歷所有的節點。

while(node || stack.length > 0) {
while(node) {
stack.push(node);
node = node.left;
}
node = stack.pop();
result.push(node.val);
node = node.right;
}

在while循環里,首先是判斷當前節點是否為null,如果當前節點不為null,則將當前節點入棧,并將當前節點的左子節點設置為當前節點。

while(node) {
stack.push(node);
node = node.left;
}

如果當前節點為null,說明已經過了最左邊的節點,需要將棧中的節點彈出來,同時將該節點的值放入result數組中保存,并將其右子節點設為當前節點,進行下一輪遍歷。

node = stack.pop();
result.push(node.val);
node = node.right;

綜合以上內容,我們就可以將一顆二叉樹通過中序遍歷的方式,依次輸出每個節點值。代碼的具體實現過程也很好理解,是通過模擬棧的方式,來保存節點順序的。

總結一下,在Javascript中序遍歷二叉樹的過程中,我們需要遍歷根節點的左子樹,然后遍歷根節點,最后遍歷根節點的右子樹。代碼的實現過程中,我們使用了模擬棧的方式,來保存了節點遍歷的順序。對于樹這種數據結構的遍歷算法,需要多加理解和實踐,才能夠真正掌握。