Java_Binary tree 二叉树分享

向右看齐 2024-04-01 12:39 37阅读 0赞

## Java\_Binary tree 二叉树分享 ##

#### 文章目录 ####

*  Java\_Binary tree 二叉树分享
 *   *  代码实现
     *  运行结果
     *  心得分享

具体内容的解释都在注释里面

### 代码实现 ###

import java.util.LinkedList;
    import java.util.Queue;
    
    public class Extree {
        
        private String data;//声明数据域
        private Extree lchild;//声明左孩子
        private Extree rchild;//声明右孩子
    
        //getter和setter方法
        public String getData() {
        
            return data;
        }
    
        public void setData(String data) {
        
            this.data = data;
        }
    
        public Extree getLchild() {
        
            return lchild;
        }
    
        public void setLchild(Extree lchild) {
        
            this.lchild = lchild;
        }
    
        public Extree getRchild() {
        
            return rchild;
        }
    
        public void setRchild(Extree rchild) {
        
            this.rchild = rchild;
        }
    
        public Extree(String data){
        //定义有参构造函数（构造数据域为data值的结点）
            this.data=data;//让对象为Extree的参数传入data域中
        }
    
        public static void preOrder(Extree tNode){
        //用于表达前序遍历的方法
            if(tNode != null) {
        //只要引入的数据不为空，则执行下方内容
                System.out.print(tNode.data + " ");//先输出此节点的data内容
                preOrder(tNode.lchild);//再递归输出此节点的左孩子内容
                preOrder(tNode.rchild);//再递归输出此节点的右孩子内容
            }
        }
    
        public static void inOrder(Extree tNode){
        //用于表达中序遍历的方法
            if(tNode != null) {
        //只要引入的数据不为空，则执行下方内容
                inOrder(tNode.lchild);//先递归输出此节点的左孩子内容
                System.out.print(tNode.data + " ");//再输出此节点的data内容
                inOrder(tNode.rchild);//再递归输出此节点的右孩子内容
            }
        }
    
        public static void PostOrder(Extree tNode){
        //用于表达后序遍历的方法
            if(tNode != null) {
        //只要引入的数据不为空，则执行下方内容
                PostOrder(tNode.lchild);//先递归输出此节点的左孩子内容
                PostOrder(tNode.rchild);//再递归输出此节点的右孩子内容
                System.out.print(tNode.data + " ");//再输出此节点的data内容
            }
        }
    
        public static void levelOrder(Extree tNode){
        //用于表达层次遍历的方法
            if(tNode==null) {
        //只要引入的数据不为空，则执行下方内容
                return ;
            }
            Queue<Extree> queue=new LinkedList ();//创建一个Extree类型的队列对象queue去调用LinkedList中对Queue重写的方法
            queue.offer(tNode);//将tNode进行入队操作
            Extree count=null;//定义一个用于承载出队元素的对象
            while(!queue.isEmpty()){
        //若队列非空则执行循环
                count=queue.poll();//用current来承载出队元素
                System.out.print(count.data+" ");//输出此时元素的data域
                if(count.lchild!=null){
        //结点非空则入队左孩子
                    queue.offer(count.lchild);
                }
                if(count.rchild!=null){
        //结点非空则入队右孩子
                    queue.offer(count.rchild);
                }
            }
        }
    
        public static void main(String[] args) {
        
    
            Extree b1=new Extree("A");//输入按照前序遍历为顺序的元素内容
            Extree b2=new Extree("B");
            Extree b3=new Extree("D");
            Extree b4=new Extree("E");
            Extree b5=new Extree("J");
            Extree b6=new Extree("C");
            Extree b7=new Extree("F");
            Extree b8=new Extree("I");
            Extree b9=new Extree("G");
    
            b1.lchild=b2;//确定每个元素的左、右孩子关系
            b1.rchild=b6;
            b2.lchild=b3;
            b2.rchild=b4;
            b4.lchild=b5;
            b6.lchild=b7;
            b6.rchild=b9;
            b7.rchild=b8;
    
            //依次进行遍历运算
            System.out.print("前序遍历为：");
            Extree.preOrder(b1);//从二叉链表的根节点进行遍历
            System.out.println();
            System.out.print("中序遍历为：");
            Extree.inOrder(b1);//从二叉链表的根节点进行遍历
            System.out.println();
            System.out.print("后序遍历为：");
            Extree.PostOrder(b1);//从二叉链表的根节点进行遍历
            System.out.println();
            System.out.print("层次遍历为：");
            Extree.levelOrder(b1);//从二叉链表的根节点进行遍历
            System.out.println();
        }
    }

### 运行结果 ###

![结果截图][a0d6d47d2ecc4e938dc52771e34dab62.png_pic_center]

### 心得分享 ###

在层序遍历中要用到队列，需要创建一个Extree类型的队列对象queue去调用LinkedList中对Queue重写的方法，在循环外层进行根节点的入队操作，循环内部开始遍历所有的左、右孩子，然后挨个输出。  
在前序遍历、后序遍历、中序遍历和层序遍历的方法中，只能使用print，而不能使用println，否则会将每个元素后都进行换行操作，因为内部方法不是所有元素进行一次性输出，而是一次一个的输出元素。只能在全部输出结束后，进行换行操作。  
注意在前序遍历、后序遍历、中序遍历和层序遍历的方法中，第一步先判空，不能忘记判空。  
要注意每次运行前序遍历、后序遍历、中序遍历和层序遍历的方法，是从二叉链表的根节点开始运行的。  
扩展二叉树需要将输入的字符串转换成为字符，之后对第一个根节点的左右结点进行访问，如果下面一个元素不为\#，则设置它为根节点的左孩子，再把此左孩子看做新的根节点，查看下面一个元素内容，直到元素内容为\#停止，如果下一个元素内容不为\#，则它为此时根节点的右孩子，若内容到达\#了，则返回根节点的双亲，看其下一个内容是否为\#，不为\#，则为这个双亲的右孩子，以此类推,最后返回到最初的根节点，访问下一个内容，去确定其右孩子是否存在。

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

以上就是本文全部内容，如果它对您有帮助，请您帮我点个赞，这对我真的很重要

[a0d6d47d2ecc4e938dc52771e34dab62.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/8f9ce29b9eb74505ade9b08ab774f1f1.png