数据结构6.2:二叉树的前中后序遍历

二叉树前中后序遍历代码实现

二叉树的遍历

二叉树的前序遍历

先输出父节点,再遍历左子树和右子树

二叉树的中序遍历

先遍历左子树,再输出父节点,再遍历右子树

二叉树的后序遍历

先遍历左子树,再遍历右子树,最后输出父节点

代码实现

每个节点中包含一个数据域和两个地址域,感觉像多了一根指针的链表

public class BinaryTreeNode {
    private BinaryTreeNode left;
    private BinaryTreeNode right;
    private int num;
}
1
2
3
4
5

创建二叉树,并创建一个节点作为根节点

public class BinaryTree {
    private BinaryTreeNode root;//创建根节点

    public void setRoot(BinaryTreeNode root){
        this.root = root;
    }
}
1
2
3
4
5
6
7

二叉树的前序遍历

从父节点开始分别向左侧和右侧递归遍历

 public void preorder() {//前序遍历
        System.out.println("节点数据:" + getNum());
        if (this.getLeft() != null) {
            this.getLeft().preorder();
        }
        if (this.getRight() != null) {
            this.getRight().preorder();
        }
    }
1
2
3
4
5
6
7
8
9

在树中调用根节点进行前序遍历

public void preOrder(){
    if(this.root != null){
        this.root.preorder(root);
    }else{
        System.out.println("二叉树为空");
    }
}
1
2
3
4
5
6
7

二叉树的中序遍历

public void midorder() {//中序遍历
        if (this.getLeft() != null) {
            this.getLeft().midorder();
        }
        System.out.println("节点数据:" + getNum());
        if (this.getRight() != null) {
            this.getRight().midorder();
        }
    }
1
2
3
4
5
6
7
8
9

在树中调用根节点进行中序遍历

public void midOrder(){
    if(this.root != null){
        this.root.midorder(root);
    }else{
        System.out.println("二叉树为空");
    }
}
1
2
3
4
5
6
7

二叉树的后序遍历

public void backorder() {//后序遍历
        if (this.getLeft() != null) {
            this.getLeft().backorder();
        }
        if (this.getRight() != null) {
            this.getRight().backorder();
        }
        System.out.println("节点数据:" + getNum());
    }
1
2
3
4
5
6
7
8
9

在树中调用根节点进行后序遍历

public void backOrder(){
    if(this.root != null){
        this.root.backorder(root);
    }else{
        System.out.println("二叉树为空");
    }
}
1
2
3
4
5
6
7

手动创建二叉树(后续使用递归方式添加)

public static void main(String[] args) {
       BinaryTree tree = new BinaryTree();
        BinaryTreeNode node1 = new BinaryTreeNode(1);
        BinaryTreeNode node2 = new BinaryTreeNode(2);
        BinaryTreeNode node3 = new BinaryTreeNode(3);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node5 = new BinaryTreeNode(5);
        tree.setRoot(node1);
        node1.setLeft(node2);
        node1.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

二叉树的遍历结果

我这里创建的二叉树应该是一个如下图所示的一棵树

1,前序遍历

因为每次都是先输出再遍历,所以顺序为1,2,4,5,3

2,中序遍历

先遍历左侧,再输出,最后遍历右侧,所以顺序为4,2,5,1,3

3,后序遍历

因为是先遍历左侧,再遍历右侧,最后才会输出,所以顺序为4,5,2,3,1