91超碰碰碰碰久久久久久综合_超碰av人澡人澡人澡人澡人掠_国产黄大片在线观看画质优化_txt小说免费全本

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

怎么實現python二叉樹的遍歷分析

發布時間:2021-12-13 17:35:07 來源:億速云 閱讀:122 作者:柒染 欄目:云計算

這篇文章給大家介紹怎么實現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二叉樹的遍歷分析就分享到這里了,希望以上內容可以對大家有一定的幫助,可以學到更多知識。如果覺得文章不錯,可以把它分享出去讓更多的人看到。

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

阿鲁科尔沁旗| 博罗县| 海安县| 横峰县| 玛曲县| 西充县| 桦川县| 安化县| 微博| 漳浦县| 宜州市| 甘谷县| 宝丰县| 乳源| 庆安县| 潜山县| 昌邑市| 会泽县| 长白| 车致| 根河市| 呼伦贝尔市| 汝南县| 镇平县| 德化县| 五原县| 新乐市| 佛坪县| 年辖:市辖区| 合作市| 罗城| 南丹县| 阳谷县| 农安县| 大化| 定日县| 江门市| 武宁县| 隆林| 济南市| 庆阳市|