1.創建對象

package com.zl;

public class TreeNode {
private String vlaue;
private TreeNode leftTreeNode;
private TreeNode rightTreeNode;


public TreeNode(String vlaue, TreeNode leftTreeNode, TreeNode rightTreeNode) {
this.vlaue = vlaue;
this.leftTreeNode = leftTreeNode;
this.rightTreeNode = rightTreeNode;
}

public String getVlaue() {
return vlaue;
}

public void setVlaue(String vlaue) {
this.vlaue = vlaue;
}

public TreeNode getLeftTreeNode() {
return leftTreeNode;
}

public void setLeftTreeNode(TreeNode leftTreeNode) {
this.leftTreeNode = leftTreeNode;
}

public TreeNode getRightTreeNode() {
return rightTreeNode;
}

public void setRightTreeNode(TreeNode rightTreeNode) {
this.rightTreeNode = rightTreeNode;
}
} ?

?

2.遍歷算法實現

package com.zl;

import java.util.LinkedList;
import java.util.Stack;

public class BinaryTree {

/* 迭代方式 先序遍歷二叉樹 */
public static void preOrderIteration(TreeNode tree) {
Stack<TreeNode> stack = new Stack<>();
while (true) {
while (tree != null) {
System.out.printf(tree.getVlaue() + "\t");
stack.push(tree);
tree = tree.getLeftTreeNode();
}
if (stack.empty()) {
break;
}
TreeNode popTreeNode = stack.pop();
tree = popTreeNode.getRightTreeNode();
}
}

/* 迭代方式 中序遍歷二叉樹 */
public static void midOrderIteration(TreeNode tree) {
Stack<TreeNode> stack = new Stack<>();
while (true) {
while (tree != null) {
stack.push(tree);
tree = tree.getLeftTreeNode();
}
if (stack.empty()) {
break;
}
TreeNode popTreeNode = stack.pop();
System.out.printf(popTreeNode.getVlaue() + "\t");
tree = popTreeNode.getRightTreeNode();
}
}

/* 迭代方式 后序遍歷二叉樹 */
public static void postOrderIteration(TreeNode tree) {
TreeNode hasPrintTree = null;
Stack<TreeNode> stack = new Stack<>();
while (true) {
while (tree != null) {
stack.push(tree);
tree = tree.getLeftTreeNode();
}
if (stack.empty()) {
break;
}
if (stack.lastElement().getRightTreeNode() == null) {
//1.右子樹為空
TreeNode treeNode = stack.pop();
hasPrintTree = treeNode;
System.out.print(treeNode.getVlaue() + "\t");
tree = null;
} else if (stack.lastElement().getRightTreeNode() == hasPrintTree) {
//2.右子樹不為空,且已經打印過了
TreeNode treeNode = stack.pop();
hasPrintTree = treeNode;
System.out.print(treeNode.getVlaue() + "\t");
tree = null;
} else {
//3.右子樹不為空 沒有打印過
TreeNode rightTreeNode = stack.lastElement().getRightTreeNode();
tree = rightTreeNode;
}

}
}

/* 迭代方式層序遍歷二叉樹 */
public static void levelOrderIteration(TreeNode tree) {
if (tree == null) return;
LinkedList<TreeNode> treeNodeList = new LinkedList<>();
treeNodeList.add(tree);

while (!treeNodeList.isEmpty()) {
TreeNode pushTree = treeNodeList.removeFirst();
System.out.print(pushTree.getVlaue() + "\t");
if (pushTree.getLeftTreeNode() != null) {
treeNodeList.addLast(pushTree.getLeftTreeNode());
}
if (pushTree.getRightTreeNode() != null) {
treeNodeList.addLast(pushTree.getRightTreeNode());
}

}


}

public static void main(String[] args) {
//測試二叉樹形式
/*
1
/ \
2 3
/ / \
4 5 6
/ \
7 8
\
9
*/

//構建二叉樹
TreeNode treeNode9 = new TreeNode("9", null, null);
TreeNode treeNode4 = new TreeNode("4", null, null);
TreeNode treeNode7 = new TreeNode("7", null, null);
TreeNode treeNode6 = new TreeNode("6", null, null);
TreeNode treeNode8 = new TreeNode("8", null, treeNode9);
TreeNode treeNode2 = new TreeNode("2", treeNode4, null);
TreeNode treeNode5 = new TreeNode("5", treeNode7, treeNode8);
TreeNode treeNode3 = new TreeNode("3", treeNode5, treeNode6);
TreeNode tree = new TreeNode("1", treeNode2, treeNode3);


System.out.print("遞歸先序遍歷tree:");
preOrderRecursive(tree);
System.out.print(System.lineSeparator());

System.out.print("迭代先序遍歷tree:");
preOrderIteration(tree);
System.out.print(System.lineSeparator());
System.out.print(System.lineSeparator());

System.out.print("遞歸中序遍歷tree:");
midOrderRecursive(tree);
System.out.print(System.lineSeparator());

System.out.print("迭代中序遍歷tree:");
midOrderIteration(tree);
System.out.print(System.lineSeparator());
System.out.print(System.lineSeparator());

System.out.print("遞歸后序遍歷tree:");
postOrderRecursive(tree);
System.out.print(System.lineSeparator());

System.out.print("迭代后序遍歷tree:");
postOrderIteration(tree);
System.out.print(System.lineSeparator());
System.out.print(System.lineSeparator());

System.out.print("迭代層序遍歷tree:");
levelOrderIteration(tree);
System.out.print(System.lineSeparator());
System.out.print(System.lineSeparator());


}


/* 遞歸方式先序遍歷二叉樹 */
public static void preOrderRecursive(TreeNode tree) {
if (null == tree) {
return;
} else {
System.out.print(tree.getVlaue() + "\t");
preOrderRecursive(tree.getLeftTreeNode());
preOrderRecursive(tree.getRightTreeNode());
}
}


/* 遞歸方式中序遍歷二叉樹 */
public static void midOrderRecursive(TreeNode tree) {
if (null == tree) {
return;
} else {
midOrderRecursive(tree.getLeftTreeNode());
System.out.print(tree.getVlaue() + "\t");
midOrderRecursive(tree.getRightTreeNode());
}
}

/* 遞歸方式后序遍歷二叉樹 */
public static void postOrderRecursive(TreeNode tree) {
if (null == tree) {
return;
} else {
postOrderRecursive(tree.getLeftTreeNode());
postOrderRecursive(tree.getRightTreeNode());
System.out.print(tree.getVlaue() + "\t");
}
}

} ?

?

轉載于:https://www.cnblogs.com/codeLei/p/10615687.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的二叉树的遍历学习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。