這篇文章給大家介紹怎么實現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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
