怎么實現(xiàn)python二叉樹的遍歷分析

這篇文章給大家介紹怎么實現(xiàn)python二叉樹的遍歷分析，內(nèi)容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

/**
 * 先序遍歷：按照“根左右”的順序，先遍歷根節(jié)點，再遍歷左子樹，再遍歷右子樹
 * 中序遍歷：按照“左根右“的順序，先遍歷左子樹，再遍歷根節(jié)點，最后遍歷右子樹
 * 后續(xù)遍歷：按照“左右根”的順序，先遍歷左子樹，再遍歷右子樹，最后遍歷根節(jié)點
 * <p>
 * 說明：
 *		1)這里的'先/中/后'是指每次遍歷的時候，根節(jié)點被遍歷的順序。
 * 		2)每個節(jié)點都可以看做一個跟節(jié)點。
 * 		3)遍歷的時候，我們會將當前節(jié)點作為一個根節(jié)點來看待。
 */

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;
}


// 存放遍歷后的節(jié)點
static ArrayList<BinaryTree> list = new ArrayList<BinaryTree>();

/**
 * 先序遍歷
 */
public static void preOrder(BinaryTree root) {

    if (root == null) return;

    list.add(root);                 // 1.將當前節(jié)點(根節(jié)點)存入list
    if (root.leftChild != null) {   // 2.當前節(jié)點的左子樹不為空時，繼續(xù)往左找
        preOrder(root.leftChild);
    }                               // 3.當前節(jié)點的左子樹為空時，說明根節(jié)點和左孩子已經(jīng)遍歷完畢了，則接下來遍歷右孩子

    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.將當前節(jié)點(根節(jié)點)存在棧中
            currentNode = currentNode.leftChild;    // 2.當前節(jié)點的左子樹不為空時，將當前節(jié)點的左子樹作為根節(jié)點，繼續(xù)執(zhí)行循環(huán)。 注：這里與遞歸式的先序遍歷類似。
        }                                           // 3.當前節(jié)點的左子樹為空時，說明根節(jié)點和左孩子已經(jīng)遍歷完畢了，則接下來遍歷右孩子

        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為空時，說明已經(jīng)到達左子樹最下邊，這時需要出棧了
        if (!stack.empty()) {
            currentNode = stack.pop();
            list.add(currentNode);
            currentNode = currentNode.rightChild;
        }

    }
}

/**
 * 后序遍歷 非遞歸
 *  要點：
 *      1)后序遍歷需要判斷上次訪問的節(jié)點是位于左子樹，還是右子樹。
 *      2)  若是位于左子樹，則需跳過根節(jié)點，先進入右子樹，再回頭訪問根節(jié)點；
 *      3)  若是位于右子樹，則直接訪問根節(jié)點。
 *
 * [@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;   // 當前訪問的節(jié)點
    BinaryTree lastVisitNode = null; // 上次訪問的節(jié)點

    // 把currentNode移到當前節(jié)點的左子樹的最左邊
    while (currentNode != null) {
        stack.push(currentNode);
        currentNode = currentNode.leftChild;
    }

    while (!stack.empty()) {
        currentNode = stack.pop();

        // 后續(xù)遍歷中，一個根節(jié)點被訪問的前提是：當前節(jié)點(可以看成根節(jié)點)無右子樹 或 當前節(jié)點的右子樹剛剛被訪問過。
        if (currentNode.rightChild != null && currentNode.rightChild != lastVisitNode) {

            stack.push(currentNode); // 當前節(jié)點的右子樹不為空且沒有被訪問過，故根節(jié)點(當前節(jié)點)再次入棧。

            // 進入右子樹，把currentNode移到當前節(jié)點的右子樹的最左邊
            currentNode = currentNode.rightChild;
            while (currentNode != null) {
                stack.push(currentNode);
                currentNode = currentNode.leftChild;
            }
        } else {
            // 訪問
            list.add(currentNode);
            lastVisitNode = currentNode;
        }
    }

}


/**
 * 返回當前數(shù)的深度
 * 1.如果一棵樹只有一個結(jié)點，它的深度為1
 * 2.如果根結(jié)點只有左子樹而沒有右子樹，那么樹的深度是其左子樹的深度加1
 * 3.如果根結(jié)點只有右子樹而沒有左子樹，那么樹的深度應該是其右子樹的深度加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;
}

/**
 * 樹的初始化：先從葉子節(jié)點開始，由葉到根
 */
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("遍歷的結(jié)果：" + resultList);
    System.out.println("樹的高度：" + getTreeDepth(root));

 }
}

關(guān)于怎么實現(xiàn)python二叉樹的遍歷分析就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。