数据结构与算法Java版——二叉树及其遍历

布满荆棘的人生 2022-06-13 03:16 190阅读 0赞

> 　二叉树可以用顺序存储结构表示，也可以用二叉链表表示，但顺序存储结构一般仅适合于存储完全二叉树……
> 
> 　　这个学期学了数据结构这本书，所以我打算用Java实现其中表，队，栈，树。如果你有兴趣可以持续关注我后续操作。我的博客地址为[我的博客][Link 1]

## 二叉树之二叉链表 ##

二叉树可以用顺序存储结构表示，也可以用二叉链表表示，但顺序存储结构一般仅适合于存储完全二叉树，如果不是存储一棵满二叉树，都会造成一定存储空间的浪费，尤其当存储一颗右斜树时，会造成存储空间的极大浪费，最坏的情况就是这种，如下图：

![这里写图片描述][85542292.jpg]  
　　所以我们一般用二叉链表表示二叉树，其基本思路：令每个节点对应一个链表节点，链表节点不仅存储二叉树节点有关数据信息，还要设置左右孩子节点。

class Node <T>{
        Node lChild;  //左子树
        Node rChild;  //右子树
        T data; //数据
    
        public Node(Node lChild, Node rChild, T data) {
            super();
            this.lChild = lChild;
            this.rChild = rChild;
            this.data = data;
        }
    }

接下来就是创建二叉树类

public class BinaryTree <T>{
        private int nodeNum;    //节点数
        public Node root;   //根节点
    
        //以某节点为根节点创建二叉链表
        public BinaryTree(T data) {
            this.root=new Node(null, null, data);
        }
    
        /**
         * 
         * @param parent 指定节点
         * @param data 添加节点数据
         * @param pos 节点位置 0为左，1为右
         */
        public Node addNode(Node parent,T data,int pos){
            if(parent==null){
                try {
                    throw new Exception("该节点为空，无法添加节点");
                } catch (Exception e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }else{
                if(pos==0&&parent.lChild==null){
                    //添加左子树
                    parent.lChild=new Node(null, null, data);
                    nodeNum++;
                    return parent.lChild;
                }else if(pos==1&&parent.rChild==null){
                    //添加右子树
                    parent.rChild=new Node(null, null, data);
                    nodeNum++;
                    return parent.rChild;
                }else{
                    try {
                        throw new Exception("节点无法再添加节点");
                    } catch (Exception e) {
                        // TODO Auto-generated catch block
                        e.printStackTrace();
                    }
                }   
            }
            return null;
        }
    
        public boolean isEmpty(){
            return root.data==null;
        }
    
        //递归获得深度
        public int deep(){
            return deep(root);
        }
    
        private  int deep(Node root){
            if(root==null){
                return 0;
            }else if(root.lChild==null&&root.rChild==null){
                //根节点孩子为null时，树深度为1
                return 1;
            }else{
                int lDeep=deep(root.lChild);
                int rDeep=deep(root.rChild);
                //比较左右子树深度
                int max=lDeep>rDeep? lDeep:rDeep;
                return max+1;
            }
        }
    }

以上就用二叉链表表示了二叉树。

## 四种遍历 ##

前序遍历

**前序遍历二叉树操作定义：**  
　　**若二叉树为空，则空操作返回；否则**  
**1. 访问根节点**  
**2. 前序遍历根节点的左子树**  
**3. 前序遍历根节点的右子树**

这里我分享三种前序遍历的方法：

方法一：（自己写的，感觉挺累赘的）

//前序遍历,递归实现前序遍历
        private String preTraversal(Node node){
            if(node.lChild==null&&node.rChild==null){
                return node.data+"";
            }else{
                StringBuilder sb=new StringBuilder();
                sb.append(node.data+" ");
                String data="";
                String data1="";
                if(node.lChild!=null){
                    data=preTraversal(node.lChild);
                }
                if(node.rChild!=null){
                    data1=preTraversal(node.rChild);
                }
                return sb.append(data+" "+data1)+"";
            }
    
        }
    
        public String preTraversal(){
            return preTraversal(root);
        }

方法二：（百度上一位网友的，利用的栈操作的，个人觉得挺不错的）

//前序遍历，利用栈进行
        public void preTraversal2(Node root){  
            if(root==null)return;  
            Stack<Node> s=new Stack<Node>();  
            while(root!=null||!s.isEmpty()){  
                while(root!=null){  
                    System.out.print(root.data+" ");  
                    s.push(root);//先访问再入栈  
                    root=root.lChild;  
                }  
                root=s.pop();  //出栈
                root=root.rChild;//如果是null，出栈并处理右子树  
            }  
        }

方法三：（这是数据结构c++版书上是这么写的，这里我把它改为了Java版，个人觉得代码最简洁，也很实用）

public void preTraversal3(Node root){
            if(root!=null){
                System.out.print(root.data+" ");
                preTraversal3(root.lChild);
                preTraversal3(root.rChild);
            }
        }

中序遍历

中序遍历二叉树的操作定义：

**若二叉树为空，则空操作返回；否则**  
**1. 中序遍历根节点的左子树**  
**2. 访问根节点**  
**3. 中序遍历根节点的右子树**

这里介绍数据结构的最常用的一种方法。

//中序遍历
        public void inOrderTraversal(Node root){
            if(root!=null){
                inOrderTraversal(root.lChild);
                System.out.print(root.data+" ");
                inOrderTraversal(root.rChild);
            }
        }

后序遍历

**后序遍历二叉树的操作定义：**

**若二叉树为空，则空操作返回；否则**

**1. 后序遍历根节点的左子树**  
**2. 后序遍历根节点的右子树**  
**3. 访问根节点**

这里介绍数据结构c++版的一种方法。

//后序遍历
        public void postOrderTraversal(Node root){
            if(root!=null){
                postOrderTraversal(root.lChild);
                postOrderTraversal(root.rChild);
                System.out.print(root.data+" ");
            }
        }

层序遍历

**二叉树的层序遍历，是指从二叉树第一层开始，从上到下，在同一层中从左到右的顺序对各个节点逐个访问。**

//层序遍历，利用队实现
        public void levelTraversal(){
            //创建队
            Queue q=new LinkedList<>();
            //添加根节点
            q.add(root);
            while(!q.isEmpty()){
                //第一个元素出队
                Node node=(Node) q.poll();
                System.out.print(node.data+" ");
                if(node.lChild!=null)
                    //入队
                    q.add(node.lChild);
                if(node.rChild!=null)
                    //入队
                    q.add(node.rChild); 
            }
        }

总结

以上就是今天分享的内容，二叉树以及其遍历都是树中的重点，二叉树是一种最简单的树结构，特别适合计算机处理，而且任何树都可以简单转换为二叉树，所以今天的内容花了挺多时间的，当然二叉树的内容还没结束，后面还要介绍哈夫曼树以及红黑树。不过今天就到此为止啦，明天继续。

[Link 1]: http://xichangblog.com
[85542292.jpg]: http://or0um8wrx.bkt.clouddn.com/17-6-25/85542292.jpg