Java面试--二叉树

╰+哭是因爲堅強的太久メ 2021-09-27 07:52 296阅读 0赞

> **面试题:讲一下二叉树的遍历**

**一、二叉树遍历方式**  
1、前序遍历：按照“根左右”,先遍历根节点，再遍历左子树 ，再遍历右子树  
![这里写图片描述][70]  
2、中序遍历：按照“左根右“,先遍历左子树，再遍历根节点，最后遍历右子树  
![这里写图片描述][70 1]  
3、后续遍历：按照“左右根”，先遍历左子树，再遍历右子树，最后遍历根节点  
![这里写图片描述][70 2]  
**二、二叉树的java实现**  
定义节点类：

public class Node {
        public long data;
        public String sData;
        public Node leftChild;
        public Node rightChild;
    
        public Node(long value,String sData){
            this.data = value;
            this.sData = sData;
        }
    }

定义树：

public class Tree {
        public Node root;
        public void insert(long value,String sData){
            Node newNode = new Node(value,sData);   //封装节点
            Node current = root;  //引用当前节点
            Node parent;          //引用父节点
            //如果root为null , 也就是第一次插入的时候
            if( root == null ){
                root = newNode;
                return;
            }
            else{
                while(true) {
                    parent = current;
                    if (current.data > value) {
                        current = current.leftChild;
                        if( current == null ) {
                            parent.leftChild = newNode;
                            return;
                        }
                    } else {
                        current = current.rightChild;
                        if( current == null ){
                            parent.rightChild = newNode;
                            return;
                        }
                    }
                }
            }
        }
        //查找节点
        public Node find(long value){
            Node current = root;
            while(current.data != value){
                if( current.data > value ){
                    current = current.leftChild;
                }
                else{
                    current = current.rightChild;
                }
                if(current == null){
                    return null;
                }
            }
            return current;
        }
        //删除节点
    }

**三、二叉树遍历的java实现**  
1、前序遍历：

public static void preOrder(BinNode node) {
        public void preOrder(Node localLoad) {
            if( localLoad != null ){
                System.out.println(localLoad.data + "," + localLoad.sData);
                preOrder(localLoad.leftChild);
                preOrder(localLoad.rightChild);
            }
        }
    }

测试：

public class TestTree {
        public static void main(String[] args) {
            Tree tree = new Tree();
            tree.insert(10,"James");
            tree.insert(20,"Tom");
            tree.insert(15,"Marry");
            tree.insert(3,"Kobe");
            tree.insert(4,"Naruto");
            tree.insert(90,"LiSi");
            tree.preOrder(tree.root);
        }
    }
    //插入之后的状态：
          10
     3          20
       4     15     90
    //输出结果：
    10,James
    3,Kobe
    4,Naruto
    20,Tom
    15,Marry
    90,LiSi

2、中序遍历：

public void inOrder(Node localNode) {
        if( localNode != null ) {
            inOrder(localNode.leftChild);
            System.out.println(localNode.data + "," + localNode.sData);
            inOrder(localNode.rightChild);
        }
    }

测试：

public class TestTree {
        public static void main(String[] args) {
            Tree tree = new Tree();
            tree.insert(10,"James");
            tree.insert(20,"Tom");
            tree.insert(15,"Marry");
            tree.insert(3,"Kobe");
            tree.insert(4,"Naruto");
            tree.insert(90,"LiSi");
            tree.inOrder(tree.root);
        }
    }
    //插入之后的状态：
          10
     3          20
       4     15     90
    //输出结果：
    3,Kobe
    4,Naruto
    10,James
    15,Marry
    20,Tom
    90,LiSi

3、后序遍历：

public void postOrder(Node localNode) {
       if( localNode != null ) {
            postOrder(localNode.leftChild);
            postOrder(localNode.rightChild);
            System.out.println(localNode.data + "," + localNode.sData);
        }
    }

测试：

public class TestTree {
        public static void main(String[] args) {
            Tree tree = new Tree();
            tree.insert(10,"James");
            tree.insert(20,"Tom");
            tree.insert(15,"Marry");
            tree.insert(3,"Kobe");
            tree.insert(4,"Naruto");
            tree.insert(90,"LiSi");
            postOrder(tree.root);
        }
    }
    //插入之后的状态：
          10
     3          20
       4     15     90
    //输出结果：
    4,Naruto
    3,Kobe
    15,Marry
    90,LiSi
    20,Tom
    10,James

--------------------

**Java面试的完整博客目录如下：[Java笔试面试目录][Java]**

> **转载请标明出处，原文地址：[https://blog.csdn.net/weixin\_41835916][https_blog.csdn.net_weixin_41835916] 如果觉得本文对您有帮助，请点击顶支持一下，您的支持是我写作最大的动力，谢谢。  
> ![这里写图片描述][70 3]**

[70]: /images/20210923/64ff9a4b3f4b4f73a1d7555e8d8df67b.png
[70 1]: /images/20210923/aba09db88d704981998895f760439e47.png
[70 2]: /images/20210923/24216610394b49fb8478030d22c2245f.png
[Java]: https://blog.csdn.net/weixin_41835916/article/details/81413498
[https_blog.csdn.net_weixin_41835916]: https://blog.csdn.net/weixin_41835916
[70 3]: /images/20210923/ca0f5a5662f44ad3a95fd6b7385f346e.png