Java二叉树及其三种遍历方式的递归实现

今天面试遇到一道题目，大概的意思就是要用Java面向对象的特性实现二叉树节点，并实现其遍历，因为是笔试，担心出错我居然直接没做，现在想起来我真是个*！话不多说，进入正题，上代码：

第一部分，节点对象(考察数据结构)

public class Node {
    private Integer data;//节点数据
    private Node leftNode;//左节点
    private Node rightNode;//右节点
    public Integer getData() {
        return data;
    }
    public void setData(Integer data) {
        this.data = data;
    }
    public Node getLeftNode() {
        return leftNode;
    }
    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }
    public Node getRightNode() {
        return rightNode;
    }
    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }
    //前序遍历
    public static void NLR(Node node) {
        if(node==null)return;
        System.out.println(node.getData());
        NLR(node.getLeftNode());
        NLR(node.getRightNode());
    }
    //中序遍历
    public static void LNR(Node node) {
        if(node==null)return;
        LNR(node.getLeftNode());
        System.out.println(node.getData());
        LNR(node.getRightNode());
    }
    //后序遍历
    public static void LRN(Node node) {
        if(node==null)return;
        LRN(node.getLeftNode());
        LRN(node.getRightNode());
        System.out.println(node.getData());
    }
}

第二部分，测试，二叉树结构图我就不画了，看懂很简单，看不懂，面壁思过去

public class NodeTest {
    public static void main(String[] args) {
        Node root=new Node();
        root.setData(0);
        
        Node A=new Node();
        A.setData(1);
        root.setLeftNode(A);
        
        Node B=new Node();
        B.setData(2);
        root.setRightNode(B);
        
        Node C=new Node();
        C.setData(3);
        A.setRightNode(C);
        
        Node D=new Node();
        D.setData(4);
        B.setLeftNode(D);
        
        Node E=new Node();
        E.setData(5);
        A.setLeftNode(E);
        
        Node F=new Node();
        F.setData(6);
        B.setRightNode(F);
        
        Node.NLR(root);
        System.out.println("NLR End...");
        Node.LNR(root);
        System.out.println("LNR End...");
        Node.LRN(root);
        System.out.println("LRN End...");
    }
}

再来看看运行效果

0
1
5
3
2
4
6
NLR End...
5
1
3
0
4
2
6
LNR End...
5
3
1
4
6
2
0
LRN End...

这里我们需要记住，二叉树的前中后序遍历是指根节点和各个父节点与它们的子节点的访问顺序，前中后序形容的是根节点和各个父节点的访问顺序。

转载于：https://blog.csdn.net/zc_25/article/details/89222412

END

Java二叉树及其三种遍历方式的递归实现

相关推荐