数据结构之二叉树及Java实现

- 日理万妓 2022-05-27 11:27 206阅读 0赞

## 一、二叉树的基本介绍 ##

链表、栈以及队列都是线性的数据结构，元素存储起来较为简单，元素只存在一个对一个的关系，而树则是一种更为复杂的数据结构，这种结构元素存在一个对多个的关系，一个父节点可以包括多个子节点。二叉树是一种特殊的树，每个节点最多只有两个子树，而且子树区分是左节点和右节点，次序不能颠倒。  
树和二叉树的区别如下所示：

*  树中节点的最大度数没有限制，而二叉树节点的最大度数为2，也就是说最多只能包含两个节点。
 *  树中的节点不区分左右，而二叉树的节点有左右之分，不能颠倒。

## 二、二叉树的Java实现 ##

与线性表的实现相似，二叉树也有两种实现方式，一种是基于数组的二叉树，另一种是基于链表的二叉树，但是基于数组的二叉树可能会产生一定的空间浪费，当二叉树为完全二叉树时，则不会存在浪费空间的问题了。而链式存储无论二叉树结构如何都不会存在这样的问题，所以二叉树的实现一般都采用基于链表的方式。  
二叉树的常用操作如下所示：

*  初始化
 *  为指定节点添加子节点
 *  判断二叉树是否为空
 *  返回根节点
 *  返回二叉树的深度
 *  遍历二叉树

1.基于数组的二叉树  
![这里写图片描述][70]  
按照完全二叉树的节点按层依次自左向右编号，若节点为空，则在数组中留空。  
数组实现的二叉树如下所示：

public class ArrayTree<T> {
        private T[] data;
        private int deep;
        private int MaxSize;
        private int size = 0;
        public ArrayTree(int deep){
            this.deep = deep;
            //根据二叉树的深度计算元素的最大个数
            MaxSize = (int)Math.pow(2, deep)-1;
            data = (T[]) new Object[MaxSize];
        }
        /**
         * 
         * @param value 根节点的值
         */
        public void creatRoot(T value){
            data[0] = value;
            size++;
        }
        /**
         * @param value 添加的节点的值
         * @param index 父节点的索引
         * @param left 是否添加到左节点，否则为右节点
         * */
        public void add(T value,int index,boolean left){
            if(data[index] == null){
                throw new RuntimeException(index + ": null");
            }
            if(2*index+1 >= MaxSize){
                throw new RuntimeException("array full");
            }
            if(left){
                data[2*index+1] = value;
                size++;
            }
            else{
                data[2*index+2] =  value;
                size++;
            }
        }
        //根据根节点是否为空判断二叉树是否为空
        public boolean isEmpty(){
            return data[0]==null;
        }
    
        //二叉树中元素的个数
        public int size(){
            return this.size;
        }
        //打印二叉树
        public String toString(){
            String str = "";
            for(int i=0; i<MaxSize; i++){
                str = str + data[i] + " ";
            }
            return str;
        }
        public static void main(String args[]){
            ArrayTree<String> at = new ArrayTree<String>(3);
            /**
             *                 根节点
             *     第二层左节点         第二层右节点
             *         第三层右节点  第三层左节点   
             */
            at.creatRoot("根节点");
            at.add("第二层左节点", 0, true);
            at.add("第二层右节点", 0, false);
            at.add("第三层右节点", 1, false);
            System.out.println(at.toString());
            at.add("第三层左节点", 2, true);
            System.out.println(at.toString());
            System.out.println("二叉树元素个数： " + at.size());
        }
    }

测试结果：

根节点 第二层左节点 第二层右节点 null 第三层右节点 null null 
    根节点 第二层左节点 第二层右节点 null 第三层右节点 第三层左节点 null 
    二叉树元素个数： 5

2.基于链表的二叉树

基于链表的二叉树需要在每个节点存储它的左节点和右节点，当然也可以再加上父节点。  
链表实现的二叉树如下所示：

import java.util.ArrayList;
    import java.util.List;
    
    
    public class NodeTree<T> {
        
        class Node<T>{
        
            public Node left;//左子树
            public Node right;//右子树
            public T data;
            //二叉树的每个节点
            public Node(T data){
                this.data = data;
                this.left = null;
                this.right = null;
            }
            public Node(){}
        }
        private Node root = null;
        private int size = 0;
    
        /**
         * 创建二叉树的根节点
         * @param value 根节点的值
         */
        public void createRoot(T value){
            if(value == null){
                throw new RuntimeException("头节点为空");
            }
            Node<T> newNode = new Node<T>(value);
            this.root = newNode;
            size++;
        }
        /**
         * 获取根节点
         * @return 返回根节点root
         */
        public Node getRoot(){
            if(root == null){
                throw new RuntimeException("头节点为空");
            }
            return this.root;
        }
        /**
         * 判断二叉树是否为空
         * @return
         */
        public boolean isEmpty(){
            return root==null;
        }
        /**
         * 返回二叉树中元素的个数
         * @return
         */
        public int size(){
            return size;
        }
        /**
         * 添加节点
         * @param n 父节点
         * @param value 添加节点的元素值
         * @param left 是否为左节点
         * @return 返回添加的新节点
         */
        public Node add(Node<T> n,T value,boolean left){
            if(value == null){
                throw new RuntimeException("子节点为空");
            }
            if(n == null){
                throw new RuntimeException("父节点为空");
            }
            Node<T> newNode = new Node<T>(value);
            if(left){
                if(n.left!=null){
                    throw new RuntimeException("已有左子节点");
                }
                n.left = newNode;
                size++;
                return newNode;
            }
            else{
                if(n.right!=null){
                    throw new RuntimeException("已有右子节点");
                }
                n.right = newNode;
                size++;
                return newNode;
            }
    
        }
        /**
         * 返回树的深度
         * @return
         */
        public int height() {
            return height(root);
        }
        public static void main(String args[]){
            NodeTree<String> nt = new NodeTree<String>();
            /**
             *                  根节点
             *   第二层左节点               第二层右节点
             *         第三层右节点    第三层左节点
             *     第四层左节点      
             */
            nt.createRoot("根节点");
            NodeTree.Node nt2 = nt.add(nt.root, "第二层左节点", true);
            NodeTree.Node nt3 = nt.add(nt.root, "第二层右节点", false);
            NodeTree.Node nt4 = nt.add(nt2, "第三层右节点", false);
            NodeTree.Node nt5 = nt.add(nt3, "第三层左节点", true);
            System.out.println("树的高度： " + nt.height());
            NodeTree.Node nt6 = nt.add(nt4, "第四层左节点", true);
            System.out.println("树的高度： " + nt.height());
            System.out.println("元素个数： " + nt.size());
        }
    
    
    }

测试结果：

树的高度： 3
    树的高度： 4
    元素个数： 6

## 三、二叉树的遍历 ##

遍历二叉树是指按某种规律访问二叉树的每个节点，数组实现的二叉树直接打印数组即可，而链表实现的二叉树主要包括两类遍历方式：

*  广度优先遍历：逐层访问每层的节点
 *  深度优先遍历：先访问树中最深层次的节点，主要包含三种方法  
    
    
     *  先序遍历
     *  中序遍历
     *  后序遍历

深度优先的三种遍历方式命名都是针对根节点而言的，先处理根节点的称为先序遍历（根左右），其次处理根节点的为中序遍历（左根右），最后处理根节点的为后序遍历（左右根）。

1.先序遍历的实现

/**
         * 先序遍历二叉树，采用根左右的顺序访问
         * @return
         */
        public List<Node> preIterator(){
            return preIterator(root);
        }
        private List<Node> preIterator(Node n){
            List<Node> list = new ArrayList<Node>();
            list.add(n);
            if(n.left!=null){
                list.addAll(preIterator(n.left));
            }
            if(n.right!=null){
                list.addAll(preIterator(n.right));
            }
            return list;
        }

2.中序遍历的实现

/**
         * 中序遍历二叉树，采用左根右的顺序访问
         * @return
         */
        public List<Node> inIterator(){
            return inIterator(root);
        }
        public List<Node> inIterator(Node n){
            List<Node> list = new ArrayList<Node>();
    
            if(n.left!=null){
                list.addAll(inIterator(n.left));
            }
            list.add(n);
            if(n.right!=null){
                list.addAll(inIterator(n.right));
            }
            return list;
        }

3.后序遍历的实现

/**
         * 后序遍历二叉树，采用左右根的顺序访问
         * @return
         */
        public List<Node> postIterator(){
            return postIterator(root);
        }
        public List<Node> postIterator(Node n){
            List<Node> list = new ArrayList<Node>();
    
            if(n.left!=null){
                list.addAll(postIterator(n.left));
            }
    
            if(n.right!=null){
                list.addAll(postIterator(n.right));
            }
            list.add(n);
            return list;
        }

测试代码：

public static void main(String args[]){
            NodeTree<String> nt = new NodeTree<String>();
            /**
             *                  根节点
             *   第二层左节点               第二层右节点
             *         第三层右节点    第三层左节点
             *     第四层左节点      
             */
            nt.createRoot("根节点");
            NodeTree.Node nt2 = nt.add(nt.root, "第二层左节点", true);
            NodeTree.Node nt3 = nt.add(nt.root, "第二层右节点", false);
            NodeTree.Node nt4 = nt.add(nt2, "第三层右节点", false);
            NodeTree.Node nt5 = nt.add(nt3, "第三层左节点", true);
            NodeTree.Node nt6 = nt.add(nt4, "第四层左节点", true);
    
            List<NodeTree.Node> prelist = new ArrayList<NodeTree.Node>();
            System.out.print("先序遍历： ");
            prelist = nt.preIterator();
            for(NodeTree.Node n:prelist){
                System.out.print(n.data + " ");
            }
            System.out.println();
    
            System.out.print("中序遍历： ");
            List<NodeTree.Node> inlist = new ArrayList<NodeTree.Node>();
            inlist = nt.inIterator();
            for(NodeTree.Node n:inlist){
                System.out.print(n.data + " ");
            }
            System.out.println();
    
            System.out.print("后序遍历： ");
            List<NodeTree.Node> postlist = new ArrayList<NodeTree.Node>();
            postlist = nt.postIterator();
            for(NodeTree.Node n:postlist){
                System.out.print(n.data + " ");
            }
            System.out.println();
        }

测试结果：

先序遍历： 根节点 第二层左节点 第三层右节点 第四层左节点 第二层右节点 第三层左节点 
    中序遍历： 第二层左节点 第四层左节点 第三层右节点 根节点 第三层左节点 第二层右节点 
    后序遍历： 第四层左节点 第三层右节点 第二层左节点 第三层左节点 第二层右节点 根节点

[70]: /images/20220527/cfc7e5f489d44661b17e759afaf6b8e7.png