数据结构学习_01二叉树的三种遍历方式

1、二叉树遍历主要三种遍历 :

1、先序遍历;
2、中序遍历;
3、后序遍历;

2、三种遍历方式的流程 :

  先序遍历 :

先序遍历.png
  中序遍历 :
中序遍历.png
  后序遍历 :
后序遍历.png

3、代码实现三种遍历方式(递归) :

  基础代码:

public class TreeNode {
    public TreeNode left;
    public TreeNode right;
    public String name;
}

   1、先序遍历(递归):

public void preOrderTraversal(TreeNode node) {
    if (node != null){
        System.out.println(node.name);
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }
}

   2、中序遍历(递归):

public void preOrderTraversal(TreeNode node) {
    if (node != null){
        System.out.println(node.name);
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }
}

   3、后序遍历(递归):

public void preOrderTraversal(TreeNode node) {
    if (node != null){
        System.out.println(node.name);
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }
}

4、代码实现三种遍历方式(非递归) :

  基础代码:

public class Stack {
    private List<TreeNode> treeNodes = new ArrayList<>();

    public void push(TreeNode node) {
        treeNodes.add(node);
    }

    public TreeNode pop(){
        TreeNode node = treeNodes.get(treeNodes.size()-1);
        treeNodes.remove(node);
        return node;
    }

    public boolean isEmpty() {
        return treeNodes.isEmpty();
    }
}

   1、先序遍历(非递归):

public void preOrderTraversal(TreeNode node) {
    Stack stack = new Stack();
    while(true) {
        while(node != null) {
            System.out.println(node.name);
            stack.push(node);
            node = node.left;
        } 
        if(stack.isEmpty()) {
            break;
        }
        node = stack.pop();
        node = node.right;
    }
}

   2、中序遍历(非递归):

public void inOrderTraversal(TreeNode node) {
    Stack stack = new Stack();
    while(true) {
        while(node != null) {
            stack.push(node);
            node = node.left;
        }
        if(stack.isEmpty()) {
            break;
        }
        node = stack.pop();
        System.out.println(node.name);
        node = node.right;
    }
}

   3、后序遍历(非递归):

public void postOrderTraversal(TreeNode node) {
    Stack stack = new Stack();
    while(true) {
        while(node != null) {
            stack.push(node);
            node = node.left;
        }
        if(stack.isEmpty()) {
            break;
        }
        node = stack.pop();
        if (node.right == null){
            System.out.println(node.name);
        }
        node = node.right;  
    }
}

先序遍历的一种思路.png 中序遍历.png 后序遍历.png Paste_Image.png Paste_Image.png