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