您好,登錄后才能下訂單哦!
這篇文章給大家介紹怎么實現python二叉樹的遍歷分析,內容非常詳細,感興趣的小伙伴們可以參考借鑒,希望對大家能有所幫助。
/** * 先序遍歷:按照“根左右”的順序,先遍歷根節點,再遍歷左子樹,再遍歷右子樹 * 中序遍歷:按照“左根右“的順序,先遍歷左子樹,再遍歷根節點,最后遍歷右子樹 * 后續遍歷:按照“左右根”的順序,先遍歷左子樹,再遍歷右子樹,最后遍歷根節點 * <p> * 說明: * 1)這里的'先/中/后'是指每次遍歷的時候,根節點被遍歷的順序。 * 2)每個節點都可以看做一個跟節點。 * 3)遍歷的時候,我們會將當前節點作為一個根節點來看待。 */ public class BinaryTree { Integer value; BinaryTree leftChild; BinaryTree rightChild; public BinaryTree(Integer value, BinaryTree leftChild, BinaryTree rightChild) { this.value = value; this.leftChild = leftChild; this.rightChild = rightChild; } // 存放遍歷后的節點 static ArrayList<BinaryTree> list = new ArrayList<BinaryTree>(); /** * 先序遍歷 */ public static void preOrder(BinaryTree root) { if (root == null) return; list.add(root); // 1.將當前節點(根節點)存入list if (root.leftChild != null) { // 2.當前節點的左子樹不為空時,繼續往左找 preOrder(root.leftChild); } // 3.當前節點的左子樹為空時,說明根節點和左孩子已經遍歷完畢了,則接下來遍歷右孩子 if (root.rightChild != null) { preOrder(root.rightChild); } } /** * 中序遍歷 */ public static void inOrder(BinaryTree root) { if (root == null) return; if (root.leftChild != null) { inOrder(root.leftChild); } list.add(root); if (root.rightChild != null) { inOrder(root.rightChild); } } /** * 后序遍歷 */ public static void postOrder(BinaryTree root) { if (root == null) return; if (root.leftChild != null) { postOrder(root.leftChild); } if (root.rightChild != null) { postOrder(root.rightChild); } list.add(root); } /** * 先序遍歷 非遞歸 * * [@param](https://my.oschina.net/u/2303379) root */ public static void preOrderNonRecursion(BinaryTree root) { if (root == null) return; Stack<BinaryTree> stack = new Stack<BinaryTree>(); BinaryTree currentNode = root; while (!stack.empty() || currentNode != null) { while (currentNode != null) { list.add(currentNode); stack.push(currentNode); // 1.將當前節點(根節點)存在棧中 currentNode = currentNode.leftChild; // 2.當前節點的左子樹不為空時,將當前節點的左子樹作為根節點,繼續執行循環。 注:這里與遞歸式的先序遍歷類似。 } // 3.當前節點的左子樹為空時,說明根節點和左孩子已經遍歷完畢了,則接下來遍歷右孩子 if (!stack.empty()) { currentNode = stack.pop(); currentNode = currentNode.rightChild; } } } /** * 中序遍歷 非遞歸 * * [@param](https://my.oschina.net/u/2303379) root */ public static void inOrderNonRecursion(BinaryTree root) { if (root == null) return; Stack<BinaryTree> stack = new Stack<BinaryTree>(); BinaryTree currentNode = root; while (!stack.empty() || currentNode != null) { while (currentNode != null) { stack.push(currentNode); currentNode = currentNode.leftChild; } // 當root為空時,說明已經到達左子樹最下邊,這時需要出棧了 if (!stack.empty()) { currentNode = stack.pop(); list.add(currentNode); currentNode = currentNode.rightChild; } } } /** * 后序遍歷 非遞歸 * 要點: * 1)后序遍歷需要判斷上次訪問的節點是位于左子樹,還是右子樹。 * 2) 若是位于左子樹,則需跳過根節點,先進入右子樹,再回頭訪問根節點; * 3) 若是位于右子樹,則直接訪問根節點。 * * [@param](https://my.oschina.net/u/2303379) root */ public static void postOrderNonRecursion(BinaryTree root) { if (root == null) return; Stack<BinaryTree> stack = new Stack<BinaryTree>(); BinaryTree currentNode = root; // 當前訪問的節點 BinaryTree lastVisitNode = null; // 上次訪問的節點 // 把currentNode移到當前節點的左子樹的最左邊 while (currentNode != null) { stack.push(currentNode); currentNode = currentNode.leftChild; } while (!stack.empty()) { currentNode = stack.pop(); // 后續遍歷中,一個根節點被訪問的前提是:當前節點(可以看成根節點)無右子樹 或 當前節點的右子樹剛剛被訪問過。 if (currentNode.rightChild != null && currentNode.rightChild != lastVisitNode) { stack.push(currentNode); // 當前節點的右子樹不為空且沒有被訪問過,故根節點(當前節點)再次入棧。 // 進入右子樹,把currentNode移到當前節點的右子樹的最左邊 currentNode = currentNode.rightChild; while (currentNode != null) { stack.push(currentNode); currentNode = currentNode.leftChild; } } else { // 訪問 list.add(currentNode); lastVisitNode = currentNode; } } } /** * 返回當前數的深度 * 1.如果一棵樹只有一個結點,它的深度為1 * 2.如果根結點只有左子樹而沒有右子樹,那么樹的深度是其左子樹的深度加1 * 3.如果根結點只有右子樹而沒有左子樹,那么樹的深度應該是其右子樹的深度加1 * 4.如果既有右子樹又有左子樹,那該樹的深度就是其左、右子樹深度的較大值加1 * * [@param](https://my.oschina.net/u/2303379) root * [@return](https://my.oschina.net/u/556800) */ public static int getTreeDepth(BinaryTree root) { int left = 0, right = 0; if (root.leftChild == null && root.rightChild == null) { return 1; } if (root.leftChild != null) { left = getTreeDepth(root.leftChild); } if (root.rightChild != null) { right = getTreeDepth(root.rightChild); } return left > right ? left + 1 : right + 1; } /** * 樹的初始化:先從葉子節點開始,由葉到根 */ public static BinaryTree getBinaryTree() { BinaryTree leaf1 = new BinaryTree(11, null, null); BinaryTree leaf2 = new BinaryTree(12, null, null); BinaryTree firstMidNode1 = new BinaryTree(21, leaf1, leaf2); BinaryTree leaf3 = new BinaryTree(13, null, null); BinaryTree leaf4 = new BinaryTree(14, null, null); BinaryTree firstMidNode2 = new BinaryTree(22, leaf3, leaf4); BinaryTree secondMidNode1 = new BinaryTree(31, firstMidNode1, firstMidNode2); BinaryTree leaf5 = new BinaryTree(32, null, null); BinaryTree root = new BinaryTree(41, secondMidNode1, leaf5); return root; } public static void main(String[] args) { BinaryTree root = getBinaryTree(); // preOrder(root); // inOrder(root); // postOrder(root); preOrderNonRecursion(root); // inOrderNonRecursion(root); // postOrderNonRecursion(root); ArrayList<Integer> resultList = new ArrayList<Integer>(); for (BinaryTree node : list) { resultList.add(node.value); } System.out.println("遍歷的結果:" + resultList); System.out.println("樹的高度:" + getTreeDepth(root)); } }
關于怎么實現python二叉樹的遍歷分析就分享到這里了,希望以上內容可以對大家有一定的幫助,可以學到更多知識。如果覺得文章不錯,可以把它分享出去讓更多的人看到。
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。