一、生成二叉树
生成目标
新建一个类：
public class BinaryNode {
public int value = 0;
public BinaryNode left;
public BinaryNode right;
public BinaryNode(int value) {
this.value = value;
}
}
生成二叉树方法：
public class BinaryTreeUtils {
public static void createBinaryTree(BinaryNode root, int[] array) {
root.value = array.length > 0 ? array[0] : -1;
for (int i = 1; i < array.length; i++) {
insertBinaryTreeNode(root, array[i]);
}
}
private static void insertBinaryTreeNode(BinaryNode root, int value) {
if (root.value >= value) {
if (root.left == null) {
root.left = new BinaryNode(value);
return;
} else {
insertBinaryTreeNode(root.left, value);
}
} else {
if (root.right == null) {
root.right = new BinaryNode(value);
return;
} else {
insertBinaryTreeNode(root.right, value);
}
}
}
}
生成二叉树：
public static void main(String[] args) {
int [] array = {8,3,5,20,15,2,29,1,4,6,13,16,21,30};
BinaryNode root = new BinaryNode(0);
BinaryTreeUtils.createBinaryTree(root,array);
}
二、前序遍历
前序遍历：访问顺序是【根节点】-【左孩子】-【右孩子】
1、递归实现：
//recursion递归前序遍历
public static void printBinaryTreePreOrder(BinaryNode root){
if (root == null) return;
System.out.print(root.value + " ");
printBinaryTreePreOrder(root.left);
printBinaryTreePreOrder(root.right);
}
2、非递归实现
访问顺序是【根节点】-【左孩子】-【右孩子】，二叉树上的任何一个节点都可以当成【根节点】，和连接在【根节点】上的“孩子们”又组成了一颗新的树，然后再按照【根节点】-【左孩子】-【右孩子】的顺序访问，重复这个过程访问完整颗树，就完成了遍历。
比如：第一次访问时8作为根节点，根据前序遍历的顺序（【根节点】-【左孩子】-【右孩子】），接下来该访问3，【右孩子】20压入栈中，继续把3作为【根节点】，访问3的【左孩子】2，把【右孩子】5压入栈中，依次类推，直到【左孩子】为空，再把之前压入栈的节点取出来，把它作为【根节点】继续访问他的【左孩子】.....直到把整颗树访问完。
//非递归前序遍历
public static void printBinaryTreePreOrder1(BinaryNode root)
{
if (root == null) {
return;
}
Stack<BinaryNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty())
{
root = stack.pop();
System.out.print(root.value + " ");
while(root.left != null)
{
System.out.print(root.left.value + " ");
if (root.right != null) {
stack.push(root.right);
}
root = root.left;
}
}
}
三、中序遍历
中序遍历：访问顺序是【左节点】-【根节点】-【右孩子】，
1、递归实现
//recursion:递归中序遍历
public static void printBinaryTreeMidOrder(BinaryNode root){
if (root == null) return;
printBinaryTreeMidOrder(root.left);
System.out.print(root.value + " ");
printBinaryTreeMidOrder(root.right);
}
2、非递归实现
访问顺序是【左节点】-【根节点】-【右孩子】,当访问节点8的时候，先把8节点作为根节点压栈，按照中序遍历的访问顺序继续访问左孩子3，这时候再把3节点作为根节点压栈继续访问左孩子，如此循环直到左孩子为空，然后依次从栈中取出刚才压入栈的数据，把取出的节点作为根节点，依次访问其右孩子，把右孩子作为根，新成一颗新树，继续上面的循环，直到右孩子为空。
//非递归中序遍历
public static void printBinaryTreeMidOrder1(BinaryNode root)
{
if (root == null) {
return;
}
Stack<BinaryNode> stack = new Stack<>();
BinaryNode tmp = root;
while(!stack.isEmpty() || tmp != null)
{
while(tmp != null)
{
stack.push(tmp);
tmp = tmp.left;
}
if (!stack.isEmpty()) {
tmp = stack.pop();
System.out.print(tmp.value + " ");
tmp = tmp.right;
}
}
}
四、后序遍历
1、递归实现
后序遍历：访问顺序是【左孩子】-【右孩子】-【根节点】
//递归后序遍历
public static void printBinaryTreeBackOrder(BinaryNode root){
if (root == null) return;
printBinaryTreeBackOrder(root.left);
printBinaryTreeBackOrder(root.right);
System.out.print(root.value + " ");
}
2、非递归实现
后序遍历的非递归实现稍微麻烦些，按照后序遍历的顺序，访问完左孩子后就访问右孩子，这样就牵涉到一个根节点状态保存的问题，访问完右孩子后还需要回到根节点。
所以我们可以这么实现：
保证出栈的顺序是左孩子，右孩子，根节点。
//非递归后序遍历
public static void printBinaryTreeBackOrder1(BinaryNode root){
if (root == null) return;
Stack<BinaryNode> stack = new Stack<>();
BinaryNode tmp = root;
stack.push(tmp);
stack.push(tmp);
while(!stack.isEmpty())
{
tmp = stack.pop();
if (!stack.empty() && tmp == stack.peek()) {
if(tmp.right != null)
{
stack.push(tmp.right);
stack.push(tmp.right);
}
if(tmp.left != null)
{
stack.push(tmp.left);
stack.push(tmp.left);
}
}else {
System.out.print(tmp.value + " ");
}
}
}
对于每个节点，都压入两遍，在循环体中，每次弹出一个节点赋给tmp，如果tmp仍然等于栈的头结点，说明tmp的孩子们还没有被操作过，应该把它的孩子们加入栈中，否则，访问tmp。也就是说，第一次弹出，将tmp的孩子压入栈中，第二次弹出，访问tmp
还有一种方式，可以把复杂的问题简单化：
我们希望最后打印的顺序是 左孩子-右孩子-根节点，那么我们可以新建一个栈，压栈的顺序为 根节点-右孩子-左孩子 ，我们就可以直接打印栈中的数据就可以了。
//非递归后序遍历2
public static void printBinaryTreeBackOrder2(BinaryNode root)
{
if (root == null)
{
return;
}
//我们希望出栈的方式是：左孩子-右孩子-根节点
//那么我们可以新建一个栈，压栈方式按照：根 - 右孩子 - 左孩子的压栈
//依次打印栈中的内容，便遍历结束
Stack<BinaryNode> stackOut = new Stack<>();
Stack<BinaryNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
root = stack.pop();
stackOut.push(root);
if (root.left != null)
{
stack.push(root.left);
}
if (root.right != null)
{
stack.push(root.right);
}
}
while (!stackOut.isEmpty())
{
BinaryNode node = stackOut.pop();
System.out.print(node.value + " ");
}
}
完整代码：
public class BinaryTreeUtils {
public static void createBinaryTree(BinaryNode root, int[] array) {
root.value = array.length > 0 ? array[0] : -1;
for (int i = 1; i < array.length; i++) {
insertBinaryTreeNode(root, array[i]);
}
}
private static void insertBinaryTreeNode(BinaryNode root, int value) {
if (root.value >= value) {
if (root.left == null) {
root.left = new BinaryNode(value);
return;
} else {
insertBinaryTreeNode(root.left, value);
}
} else {
if (root.right == null) {
root.right = new BinaryNode(value);
return;
} else {
insertBinaryTreeNode(root.right, value);
}
}
}
//recursion递归前序遍历
public static void printBinaryTreePreOrder(BinaryNode root){
if (root == null) return;
System.out.print(root.value + " ");
printBinaryTreePreOrder(root.left);
printBinaryTreePreOrder(root.right);
}
//非递归前序遍历
public static void printBinaryTreePreOrder1(BinaryNode root)
{
if (root == null) {
return;
}
Stack<BinaryNode> stack = new Stack<>();
stack.push(root);
BinaryNode tmp = root;
while(!stack.isEmpty())
{
tmp = root = stack.pop();
System.out.print(root.value + " ");
while(tmp != null)
{
if (tmp.left != null) {
System.out.print(tmp.left.value + " ");
}
if (tmp.right != null) {
stack.push(tmp.right);
}
tmp = tmp.left;
}
}
}
//递归中序遍历
public static void printBinaryTreeMidOrder(BinaryNode root){
if (root == null) return;
printBinaryTreeMidOrder(root.left);
System.out.print(root.value + " ");
printBinaryTreeMidOrder(root.right);
}
//非递归中序遍历
public static void printBinaryTreeMidOrder1(BinaryNode root)
{
if (root == null) {
return;
}
Stack<BinaryNode> stack = new Stack<>();
BinaryNode tmp = root;
while(!stack.isEmpty() || tmp != null)
{
while(tmp != null)
{
stack.push(tmp);
tmp = tmp.left;
}
if (!stack.isEmpty()) {
tmp = stack.pop();
System.out.print(tmp.value + " ");
tmp = tmp.right;
}
}
}
//递归后序遍历
public static void printBinaryTreeBackOrder(BinaryNode root){
if (root == null) return;
printBinaryTreeBackOrder(root.left);
printBinaryTreeBackOrder(root.right);
System.out.print(root.value + " ");
}
//非递归后序遍历
public static void printBinaryTreeBackOrder1(BinaryNode root){
if (root == null) return;
Stack<BinaryNode> stack = new Stack<>();
BinaryNode tmp = root;
stack.push(tmp);
stack.push(tmp);
while(!stack.isEmpty())
{
tmp = stack.pop();
if (!stack.empty() && tmp == stack.peek()) {
if(tmp.right != null)
{
stack.push(tmp.right);
stack.push(tmp.right);
}
if(tmp.left != null)
{
stack.push(tmp.left);
stack.push(tmp.left);
}
}else {
System.out.print(tmp.value + " ");
}
}
}
//非递归后序遍历2
public static void printBinaryTreeBackOrder2(BinaryNode root)
{
if (root == null)
{
return;
}
//我们希望出栈的方式是：左孩子-右孩子-根节点
//那么我们可以新建一个栈，压栈方式按照：根 - 右孩子 - 左孩子的压栈
//依次打印栈中的内容，便遍历结束
Stack<BinaryNode> stackOut = new Stack<>();
Stack<BinaryNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
root = stack.pop();
stackOut.push(root);
if (root.left != null)
{
stack.push(root.left);
}
if (root.right != null)
{
stack.push(root.right);
}
}
while (!stackOut.isEmpty())
{
BinaryNode node = stackOut.pop();
System.out.print(node.value + " ");
}
}
}
打印代码：
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] array = {8,3,5,20,15,2,29,1,4,6,13,16,21,30};
BinaryNode root = new JavaTest.BinaryNode(0);
BinaryTreeUtils.createBinaryTree(root,array);
System.out.println("前序：");
BinaryTreeUtils.printBinaryTreePreOrder(root);
System.out.println("");
BinaryTreeUtils.printBinaryTreePreOrder1(root);
System.out.println("");
System.out.println("中序：");
BinaryTreeUtils.printBinaryTreeMidOrder(root);
System.out.println("");
BinaryTreeUtils.printBinaryTreeMidOrder1(root);
System.out.println("");
System.out.println("后序：");
BinaryTreeUtils.printBinaryTreeBackOrder(root);
System.out.println("");
BinaryTreeUtils.printBinaryTreeBackOrder1(root);
System.out.println("");
BinaryTreeUtils.printBinaryTreeBackOrder2(root);
}
}
结果：
结果
