怎么实现python二叉树的遍历分析

这篇文章给大家介绍怎么实现python二叉树的遍历分析，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。

成都创新互联成立于2013年，是专业互联网技术服务公司，拥有项目做网站、成都网站制作网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元四子王做网站,已为上家服务,为四子王各地企业和个人服务,联系电话:18980820575

/**
 * 先序遍历：按照“根左右”的顺序，先遍历根节点，再遍历左子树，再遍历右子树
 * 中序遍历：按照“左根右“的顺序，先遍历左子树，再遍历根节点，最后遍历右子树
 * 后续遍历：按照“左右根”的顺序，先遍历左子树，再遍历右子树，最后遍历根节点
 * 

 * 说明：
 *		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 list = new ArrayList();

/**
 * 先序遍历
 */
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 stack = new Stack();

    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 stack = new Stack();

    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 stack = new Stack();

    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 resultList = new ArrayList();
    for (BinaryTree node : list) {
        resultList.add(node.value);
    }
    System.out.println("遍历的结果：" + resultList);
    System.out.println("树的高度：" + getTreeDepth(root));

 }
}

关于怎么实现python二叉树的遍历分析就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。