Java-数据结构：树

r囧r小猫 2022-10-06 11:52 195阅读 0赞

# 目录： #

一、树  
1. 概述  
2. 一些基本术语  
二、二叉树  
1. 概述  
2. 重要特性  
三、二叉树的存储结构  
1. 顺序存储  
2. 链式存储  
四、二叉树的遍历  
1. 由遍历序列确定二叉树  
2. 根据遍历序列估计二叉树  
3. 遍历和建树代码

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

# 一、树 #

## 1. 概述 ##

*  与线性表表示的一一对应的线性关系不同，树表示的是更为复杂的数据元素之间的**非线性关系**。
 *  直观来看，**树是以分支关系定义的层次结构**，是 **一对多** 的关系
 *  树的**定义**：树 (Tree) 是 n( n>=0 ) 个结点的有限集合
 *  有且仅有一个 **根结点** (Root)
 *  当n>1的时，其余结点可分为 m( m>0 ) 个互不相交的有限集T1，T2，…, Tm，其中每一个集合本身又是一棵树，并且称之为根的**子树**。

> 树的定义本身是一个递归定义，即在树的定义中又用到树的概念

## 2. 一些基本术语 ##

*  **树的结点**：包含一个**数据元素**和若干指向其子树的**分支**
 *  **度**（degree）：结点拥有的子树的数目
 *  度为\*\* 0 **的结点称为** 叶子\*\*，或\*\* 终端结点\*\*。度不为\*\* 0\*\* 的结点称为 **非终端结点** 或 **分支节点**
 *  结点的子树的根，称为该结点的 **孩子**（child），相应的该结点称为孩子的 **双亲**（parent）
 *  同一个双亲的孩子之间互称**兄弟**（sibling）
 *  结点的 **祖先** 是从根到该结点所经分支上所有的结点。
 *  以某结点为根的子树中的任意一结点都称为该结点的 **子孙**
 *  结点的 **层次**（Level）从根开始定义，根为第一层，根的孩子为第二层，以此类推
 *  树中结点的最大层次称为树的 **深度**（depth）或 **高度**

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

# 二、二叉树 #

## 1. 概述 ##

*  **定义**：对一般的树加了约束：
 *  每个结点**最多两棵**子树，即二叉树中不存在 **度大于2** 的结点
 *  子树有 **左右次序** 之分
 *  **有 5 种形态**：

![二叉树的形态][d1fb30ab3372e30a304fff929d1fda94.png]

*  **满二叉树**和**完全二叉树**（对满二叉树最底层，从右至左删除结点）

## 2. 重要特性 ##

*  二叉树，在第 **i** 层至多有 **2i-1** 个结点
 *  深度为 **k** 的二叉树至多有 **2k-1** 个结点
 *  高度（或深度）为 **K** 的**完全二叉树**至少有 **2k-2** 个 **叶子结点**
 *  非空二叉树的 **叶子结点数** 等于**度为 2** 的结点数加 1，即：`n0 = n2 + 1`

> 完全二叉树的 n1 只能是 0 或者 1

*  一颗度为 **m** 的二叉树，度为 1 的结点为 n1，度为 2 的结点为 n2，… …，度为 m 的结点数为 nm，则叶子结点数：**n0**\*\*= 1 + n2\*\*\*\*+ 2n3\*\*\*\*+…+ (m-1)nm\*\*
 *  具有 n 个结点的完全二叉树，深度为 **log2n + 1**
 *  **编号性质**：n 个结点的完全二叉树（其深度为 **log2n + 1**），对各结点从上到下，从左到右依次编号（1~n）则：若 i 是某结点 a 的编号：
 *  如果 i 不等于 1，则 a 的**双亲结点**的编号为： **⌊ i/2 ⌋**
 *  如果 **2i ≤ n**, 则 a 的**左孩子**编号为 **2i**；如果\*\* 2i > n\*\*, 则 a\*\* 无左孩子\*\*；
 *  如果\*\* 2i + 1 ≤ n\*\*, 则 a 的**右孩子**编号为\*\* 2i + 1\*\*；如果\*\* 2i + 1> n\*\*, 则 a\*\* 无右孩子\*\*；

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

# 三、二叉树的存储结构 #

## 1. 顺序存储 ##

*  用 **数组** 来存储数据元素
 *  从存储的角度来看，这种顺序存储结构，仅适用于 **完全二叉树**

> 因为在最坏的情况下，一个深度为 **k** 且只有 **k** 个结点的单支树( 树中不存在度为 2 的结点 )，却需要长度为 **2k-1** 的一维数组。

## 2. 链式存储 ##

*  以 **链表** 的形式，存储数据元素以及数据元素之间的关系。

![链式存储][a5f7dc8e81c1701768242e15200ae000.png]

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

# 四、二叉树的遍历 #

## 1. 由遍历序列确定二叉树 ##

*  由 **先序和中序，可以确定**
 *  由 **后序和中序，可以确定**（但是注意后序**最后一个为根**，**下一个是右子树根**）
 *  由 **层次和中序，可以确定**

## 2. 根据遍历序列估计二叉树 ##

*  **前序** 遍历序列 和 **后序** 遍历序列 **相同** 的树：**只有根结点**
 *  **前序** 遍历 和 **中序** 遍历 **相同** 的二叉树：**所有结点没有左子树（右单分支树**
 *  **中序** 遍历 和 **后序** 遍历 **相同** 的二叉树：**所有结点没有右子树（左单分支树）**
 *  **前序**遍历 和 **后序** 遍历 **相反** 的二叉树：没有左子树或者没有右子树（**只有一个叶子结点**）**高度等于其结点数**
 *  **前序** 遍历 和 **中序** 遍历 **相反** 的二叉树：**所有结点没有右子树（左单分支树）**
 *  **中序** 遍历 和 **后序** 遍历 **相反** 的二叉树：**所有结点没有左子树（右单分支树）**

## 3. 遍历和建树代码 ##

*  二叉树的建树
 *  深度优先遍历（先序，中序和后序）
 *  广度优先遍历（先序，后序）

/* BitTree.java */
    
    package com.java.tree;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    /**
     * Created by Jaco.Young.
     * 2018-06-13 18:26
     */
    public class BitTree {
        
    
        //代表由先序和中序唯一确定的树的根结点
        private TreeNode root;
    
        /**
         * 提供给外部调用的方法
         * 字符数组pre表示先序遍历序列，mid表示中序遍历序列
         */
        public void build(char[] pre, char[] mid){
        
            //将创建树的根结点赋值给 root
            root = buildTree(pre,0, pre.length-1, mid, 0, mid.length-1);
        }
    
        /**
         * 前提条件，树中不存在重复元素
         * 由先序遍历序列和中序遍历序列，构造二叉树的方法
         * 我们建树的过程总是将序列不断地分割成左子树、右子树
         * lPre、rPre和lMid、rMid，分别就表示要对先序和中序的哪一部分进行建树
         */
        private TreeNode buildTree(char[] pre, int lPre, int rPre, char[] mid, int lMid, int rMid){
        
            //在先序遍历序列中，找到当前这棵树的根结点
            char root = pre[lPre];
    
            //在中序遍历序列中，根据先序中的根结点来查找在中序中的位置
            int rootIndex = getRootIndex(mid, lMid, rMid, root);
    
            //如果没有找到，说明所给的参数异常
            if(rootIndex == -1){
        
                throw new IllegalArgumentException("Illegal Argument!");
            }
    
            //计算当前这棵树，左右子树的个数
            //整个中序序列：[左子树(lMid)  root(rootIndex)  右子树(rMid)]
            //左子树[lMid,rootIndex-1]
            int lNum = rootIndex - lMid; //rootIndex-1 -lMid + 1
            //右子树[rootIndex+1,rMid]
            int rNum = rMid - rootIndex;  //rMid - (rootIndex + 1) + 1
    
            //开始构建当前根结点的左子树和右子树
            //先构建左子树
            TreeNode lchild;  //作为左子树的根结点
            //以当前结点为根的树，没有左子树
            if(lNum == 0){
        
                lchild = null;
            }else{
        
                //当前这个树的左子树，仍然是一棵树，递归构造这棵树的左子树
                //设x为当前树先序中左子树最后一个元素的下标，则：x - (lpre + 1) = lNum
                //得：x = lPre + lNum
                lchild = buildTree(pre, lPre + 1, lPre+lNum, mid, lMid, rootIndex - 1);
            }
    
            //构建右子树
            TreeNode rchild;
            if(rNum == 0){
        
                rchild = null;
            }else{
        
                //当前结点的右子树，仍然包含很多节点，需要递归的构造其右子树
                rchild = buildTree(pre, lPre + lNum + 1, rPre, mid, rootIndex + 1, rMid);
            }
    
            //构造完整的二叉树
            return new TreeNode(root,lchild,rchild);
        }
    
        //在中序遍历序列中，根据先序中的根结点来查找在中序中的位置
        private int getRootIndex(char[] mid, int lMid, int rMid, char root) {
        
            for(int i = lMid; i <= rMid; i++){
        
                if(mid[i] == root){
        
                    return i;
                }
            }
            return -1;
        }
    
        //二叉树每一个结点的结构
        private class TreeNode{
        
            //结点中存储的数据
            char item;
            //指向左孩子结点
            TreeNode lChild;
            //指向右孩子结点
            TreeNode rChild;
    
            //构造方法,完成初始化
            public TreeNode(char item, TreeNode lChild, TreeNode rChild){
        
                this.item = item;
                this.lChild = lChild;
                this.rChild = rChild;
            }
        }
    
        //提供三个让外界调用的方法
        public  void preTraverse() {
        
            preOrder(root);
        }
    
        public void midTraverse() {
        
            midOrder(root);
        }
    
        public void postTraverse() {
        
            postOrder(root);
        }
    
        //先序遍历  DLR
        private void preOrder(TreeNode root) {
        
            if( root != null) {
        
                //先访问根节点
                System.out.print(root.item + " ");
                //递归访问左子树
                preOrder(root.lChild);
                //递归访问右子树
                preOrder(root.rChild);
            }
        }
    
        //中序遍历   LDR
        private void midOrder(TreeNode root) {
        
            if(root != null) {
        
                //递归访问左子树
                midOrder(root.lChild);
                //访问根
                System.out.print(root.item + " ");
                //递归访问右子树
                midOrder(root.rChild);
            }
        }
    
        //后续遍历
        // LRD
        private void postOrder(TreeNode root) {
        
            if(root != null) {
        
                //递归访问左子树
                postOrder(root.lChild);
                //递归访问右子树
                postOrder(root.rChild);
                //访问根
                System.out.print(root.item + " ");
            }
        }
    
        //广度优先遍历  BFS
        public void BFS() {
        
            //创建一个能放TreeNode对象的队列
            Queue<TreeNode> queue = new LinkedList<>();
            //将树的根节点入队列
            queue.add(root);
            //循环执行广度优先遍历
            while(!queue.isEmpty()) {
        
                //将当前的队头元素出队列
                TreeNode node = queue.remove();
                //访问出队列的节点
                System.out.print(node.item + " ");
    
                //出队列的节点是否有左孩子，有则将其左孩子入队列
                if(node.lChild != null) {
        
                    //有左孩子
                    queue.add(node.lChild);
                }
                //出队列的节点是否有右孩子，如果右，将其右孩子如队列
                if(node.rChild != null) {
        
                    queue.add(node.rChild);
                }
            }
        }
    }

/* Test.java*/
    package com.java.tree;
    
    /**
     * 测试类
     * Created by Jaco.Young.
     * 2018-06-13 20:16
     */
    public class Test {
        
        public static void main(String[] args){
        
            //构造先序遍历序列和中序遍历序列
            char[] pre = {
        'A','B','E', 'K', 'L', 'F', 'D', 'H', 'J'};
            char[] mid = {
        'K', 'E', 'L', 'B', 'F', 'A', 'H', 'D', 'J'};
    
            BitTree bitTree = new BitTree();
            //根据遍历序列构建二叉树
            bitTree.build(pre, mid);
    
            //先序遍历
            bitTree.preTraverse();
            System.out.println();
            //中序遍历
            bitTree.midTraverse();
            System.out.println();
            //后序遍历
            bitTree.postTraverse();
            System.out.println();
            //广度优先遍历
            bitTree.BFS();
        }
    }

> 运行结果为：  
> A B E K L F D H J  
> K E L B F A H D J  
> K L E F B H J D A

# 写在最后 #

**以上分享的全部资料都可免费分享领取——** **[【点击这里下载】][Link 1]**

还有一份JAVA核心知识点整理（PDF）：**JVM，JAVA集合，JAVA多线程并发，JAVA基础，Spring原理，微服务，Netty与RPC**，网络，日志，Zookeeper，Kafka，RabbitMQ，Hbase，**MongoDB，Cassandra，设计模式，负载均衡，数据库，一致性哈希，JAVA算法，数据结构，加密算法，分布式缓存**，Hadoop，Spark，Storm，YARN，机器学习，云计算…

F A H D J

> K L E F B H J D A

# 写在最后 #

**以上分享的全部资料都可免费分享领取——** **[【点击这里下载】][Link 1]**

![image][]

[d1fb30ab3372e30a304fff929d1fda94.png]: /images/20221005/7d7fae5d794c495b980e5b0ac86b3bcc.png
[a5f7dc8e81c1701768242e15200ae000.png]: /images/20221005/ff2f60f7ac5d49b199660ed590fb5f64.png
[Link 1]: https://docs.qq.com/doc/DSmxTbFJ1cmN1R2dB
[image]: /images/20221005/a507fa238e904e22bb2bd3ebf1a7b929.png