这篇文章给大家介绍怎么实现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进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
