玩透二叉树(Binary-Tree)及前序（先序）、中序、后序【递归和非递归】遍历

class TreeNode {
    int val;
    //左子树
    TreeNode left;
    //右子树
    TreeNode right;
    //构造方法
    TreeNode(int x) {
        val = x;
    }
}

// 递归先序遍历
public static void recursionPreorderTraversal(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + " ");
        recursionPreorderTraversal(root.left);
        recursionPreorderTraversal(root.right);
    }
}

// 非递归先序遍历
public static void preorderTraversal(TreeNode root) {
    // 用来暂存节点的栈
    Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
    // 新建一个游标节点为根节点
    TreeNode node = root;
    // 当遍历到最后一个节点的时候，无论它的左右子树都为空，并且栈也为空
    // 所以，只要不同时满足这两点，都需要进入循环
    while (node != null || !treeNodeStack.isEmpty()) {
        // 若当前考查节点非空，则输出该节点的值
        // 由考查顺序得知，需要一直往左走
        while (node != null) {
            System.out.print(node.val + " ");
            // 为了之后能找到该节点的右子树，暂存该节点
            treeNodeStack.push(node);
            node = node.left;
        }
        // 一直到左子树为空，则开始考虑右子树
        // 如果栈已空，就不需要再考虑
        // 弹出栈顶元素，将游标等于该节点的右子树
        if (!treeNodeStack.isEmpty()) {
            node = treeNodeStack.pop();
            node = node.right;
        }
    }
}

// 递归中序遍历
public static void recursionMiddleorderTraversal(TreeNode root) {
    if (root != null) {
        recursionMiddleorderTraversal(root.left);
        System.out.print(root.val + " ");
        recursionMiddleorderTraversal(root.right);
    }
}

// 非递归中序遍历
public static void middleorderTraversal(TreeNode root) {
    Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
    TreeNode node = root;
    while (node != null || !treeNodeStack.isEmpty()) {
        while (node != null) {
            treeNodeStack.push(node);
            node = node.left;
        }
        if (!treeNodeStack.isEmpty()) {
            node = treeNodeStack.pop();
            System.out.print(node.val + " ");
            node = node.right;
        }
    }
}

// 递归后序遍历
public static void recursionPostorderTraversal(TreeNode root) {
    if (root != null) {
        recursionPostorderTraversal(root.left);
        recursionPostorderTraversal(root.right);
        System.out.print(root.val + " ");
    }
}

// 非递归后序遍历
public static void postorderTraversal(TreeNode root) {
    Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
    TreeNode node = root;
    TreeNode lastVisit = root;
    while (node != null || !treeNodeStack.isEmpty()) {
        while (node != null) {
            treeNodeStack.push(node);
            node = node.left;
        }
        //查看当前栈顶元素
        node = treeNodeStack.peek();
        //如果其右子树也为空，或者右子树已经访问
        //则可以直接输出当前节点的值
        if (node.right == null || node.right == lastVisit) {
            System.out.print(node.val + " ");
            treeNodeStack.pop();
            lastVisit = node;
            node = null;
        } else {
            //否则，继续遍历右子树
            node = node.right;
        }
    }
}

package main

import "fmt"

type Node struct {
    V int
    L *Node
    R *Node
}
//前序
func forwardLook(root *Node)  {
    if root == nil {
        return
    }
    //输出行的位置在最前面
    fmt.Printf("node %v ", root.V)
    forwardLook(root.L)
    forwardLook(root.R)
}
//var i int
func forwardLoop(root *Node) {
    //需要一个堆保存走过的路径
    nodes:=[]*Node{}
    for len(nodes) != 0 || root != nil {
        //一直往左走
        for root != nil{
            nodes=append(nodes, root)
            fmt.Printf("node %v ",root.V)
            root = root.L
        }
        //说明左子结点为空，那么就看右结点
        if len(nodes) >0 {
            root=nodes[len(nodes)-1]
            //用完最近一个结点后，删除它，删除后最后的结点一定是父结点
            nodes=nodes[:len(nodes)-1]
            //左子结点遍历完了，所以这里只看当看结点的右子结点
            root=root.R
        }else{
            root = nil
        }
    }
}
//中序
func middleLook(root *Node)  {
    if root == nil {
        return
    }
    middleLook(root.L)
    //输出行的位置在中间
    fmt.Printf("node %v ", root.V)
    middleLook(root.R)
}
//后序
func backwardLook(root *Node)  {
    if root == nil {
        return
    }
    //输出行的位置在后面
    backwardLook(root.L)
    backwardLook(root.R)
    fmt.Printf("node %v ", root.V)
}

func main(){
    tree:=&Node{1,
        &Node{2,
            &Node{4, nil, nil}, &Node{5, nil, nil},
            },
        &Node{3,
            &Node{6, nil, nil}, &Node{7, nil, nil},
            },
    }
    fmt.Println("\nforwardLook ")
    forwardLook(tree)
    fmt.Println("\nforwardLoop ")
    forwardLoop(tree)
    fmt.Println("\nmiddleLook ")
    middleLook(tree)
    fmt.Println("\nbackwardLook ")
    backwardLook(tree)


    tree=&Node{1,
        &Node{2,
            nil,
            &Node{4,
                nil,
                &Node{6,
                    &Node{7, nil, nil},
                    &Node{8, nil, nil},
                    },
                },
            },
        &Node{3,
            nil, &Node{5, nil, nil},
            },
    }
    fmt.Println("\nforwardLook ")
    forwardLook(tree)
    fmt.Println("\nforwardLoop ")
    forwardLoop(tree)
    fmt.Println("\nmiddleLook ")
    middleLook(tree)
    fmt.Println("\nbackwardLook ")
    backwardLook(tree)
}