二叉树遍历

# 二叉树

## 前序遍历

```java
public void preOrder(BTree bt){
    Node node = bt.root;
    if(ndoe == null){
        System.out.println("二叉树为空");
        return;
    }else{
        Stack<Node> s = new Stack<>();//临时栈
        s.push(node);
        while(s.size()>0){
            node = s.pop();
            System.out.println(node.data);//退栈输出结点信息
            if(node.right!=null){
                s.push(node.right);
            }
            if(node.left!=null){
                s.push(node.left);
            }
        }
    }
}
```

## 中序遍历

```java
public void infixOrder(BTree bt){
    Node node = bt.root;
    if(node == null){
        System.out.println("二叉树为空");
        return;
    }else{
        Stack<Node> s = new Stack<>();//临时栈
        while(s.size()>0 || node != null){
            if(node!=null){
                s.push(node);
                node = node.left;
            }else{
                node = s.pop();
                System.out.println(node.data);//退栈输出结点信息
                node = node.right;
            }
        }		
    }
}
```

## 后序遍历

```java
public void postOrder(BTree bt){
    Node node = bt.root;
    if(node == null){
        System.out.println("二叉树为空");
        return;
    }else{
        Stack<Node> s1 = new Stack<>();//临时栈
        Stack<Node> s2 = new Stack<>();//最终结果栈
        s1.push(node);
        while(s1.size()>0){
            node = s1.pop();
            s2.push(node);
            if(node.left!=null){
                s1.push(node.left);
            }
            if(node.right!=null){
                s1.push(node.right);
            }
        }
    }
    while(s2.size()>0){
        System.out.println(s2.pop().data);//退栈输出结点信息
    }
}
```

## 层次遍历

```java
public void levelOrder(BTree bt){
    Node node = bt;
    if(node == null){
        System.out.println("二叉树为空");
        return;
    }else{
        Queue<Node> queue = new ArrayList<>();
        queue.offer(node);
        while(!queue.isEmpty()){
            node = queue.poll();
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
        }
    }
}
```

Last modification：September 23rd, 2020 at 08:27 am

二叉树遍历