这篇文章给大家介绍怎么实现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二叉树的遍历分析就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。