博客

package com.structure.binarytree;

import com.structure.link.ArrayList;
import com.structure.stack.Stack;

import data.TreeNode;

public class Main {

    public static void main(String[] args) {
        TreeNode root = new TreeNode("A");
        root.left = new TreeNode("B");
        root.right = new TreeNode("C");
        root.left.left = new TreeNode("D");
        root.left.right = new TreeNode("E");
        root.right.left = new TreeNode("F");
        root.right.right = new TreeNode("G");
        root.left.left.left = new TreeNode("H");
        root.left.left.right = new TreeNode("I");
        root.left.right.right = new TreeNode("J");
        root.right.left.right = new TreeNode("K");
//      pre_traverse(root);
//      System.out.println();
//      pre_traverse2(root);
//      System.out.println();

//      in_traverse(root);
//      System.out.println();
//      in_traverse2(root);
//      System.out.println();

        post_traverse(root);
        System.out.println();
//      in_traverse2(root);
//      System.out.println();
    }

    //前序遍历
    public static void pre_traverse(TreeNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+",");
        pre_traverse(root.left);
        pre_traverse(root.right);
    }

    //前序遍历
    public static void pre_traverse2(TreeNode root){
        if(root==null){
            return;
        }
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();      
        while(cur!=null || !stack.isEmpty()){
            while(cur!=null){
                System.out.print(cur.val+",");
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode treeNode = stack.pop();
            if(treeNode!=null){
                cur = treeNode.right;
            }
        }       
    }

    //中序遍历
    public static void in_traverse(TreeNode root){
        if(root==null){
            return;
        }
        in_traverse(root.left);
        System.out.print(root.val+",");
        in_traverse(root.right);
    }

    //中序遍历
    public static void in_traverse2(TreeNode root){
        if(root==null){
            return;
        }
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();      
        while(cur!=null || !stack.isEmpty()){
            while(cur!=null){               
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode treeNode = stack.pop();
            System.out.print(treeNode.val+",");
            if(treeNode!=null){
                cur = treeNode.right;
            }
        }       
    }

    //后续遍历
    public static void post_traverse(TreeNode root){
        if(root==null){
            return;
        }       
        post_traverse(root.left);
        post_traverse(root.right);
        System.out.print(root.val+",");
    }

    //后续遍历
    public static void post_traverse2(TreeNode root){
        if(root==null){
            return;
        }
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();      
        while(cur!=null || !stack.isEmpty()){
            while(cur!=null){               
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode treeNode = stack.top();

            System.out.print(treeNode.val+",");
            if(treeNode!=null){
                cur = treeNode.right;
            }
        }           
    }
}