Java数据结构--二叉树

r囧r小猫 2023-10-06 10:38 28阅读 0赞

## `一、二叉树的概念` ##

> 二叉树是结点的有限结合，这个集合或者为空或者是由一个跟结点和两棵互不相交的分别称为左子树和右子树的二叉树组成。二叉树中的每个结点至多有两棵子树，且子树有左右之分，次序不能颠倒。  
> 二叉树是一种重要的树型结构，但是二叉树不是树的特例。二叉树的5种形态分别为：空二叉树、只有根结点的二叉树、根结点和左子树、根结点和右子树、根结点和左子树。  
> 二叉树与树的区别：二叉树中每个结点的孩子至多不能超过两个，而树对结点的孩子树无限制；另外，二叉树中结点的子树有左右之分，而树的子树没有次序。思考一颗度为2的树与一棵二叉树有什么区别？

> 区别有两点：  
> 1）二叉树的一个结点至多有两个子树，树则不然；  
> 2）二叉树的一个结点的子树有左右之分，而树的子树没有次序。  
> 具有3个结点的树和具有3个结点的二叉树的有所不同形态如下所示：  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70]

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 1]

## `二、二叉树的性质` ##

> 几种种特殊形态的二叉树：满二叉树、完全二叉树、扩充二叉树。如图所示：  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 2]  
> 深度为k且2k\-1个结点的二叉树称为满二叉树。  
> 若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。  
> 根据定义：  
> 1）满二叉树是完全二叉树。反之不成立；  
> 2）对于完全二叉树，若其结点无左孩子，则必无右孩子，该结点为叶结点。

> 性质1：二叉树第i层上的结点数目最多为2i\-1（i ≥ 1）;  
> 性质2：深度为k的二叉树至多有2k\-1个结点（k ≥ 1）;  
> 性质3：任意二叉树中，若叶结点的个数为n0，度为2的结点树为n2，则n0=n2\+1；  
> 性质4：具有n个结点的完全二叉树的深度为\[log2n\]+1( \[log2n\]表示该值的最大整数 )；  
> 性质5：如果一棵树有n个结点的完全二叉树的结点按层次编号（即自上而下，自左至右），则对任一结点i（1 ≤ i ≤ n），有：
> 
>  *  1）如果i=1，则结点i是二叉树，无双亲；如果i > 1，则其双亲是编号为\[i/2\]的结点。
>  *  2）如果 2*i > n ，则结点i无左孩子；否则其左孩子是编号为2*i的结点。
>  *  3）如果 2*i+1 > n，则结点i无右孩子；否则其右孩子是编号为 2*i + 1的结点。
>  *  4）若 i 为奇数且不为1，则结点i的左兄弟的编号是 i - i；否则，结点i无左兄弟。
>  *  5）若i为偶数且小于n，则结点i的右兄弟编号是i+1；否则，结点i无右兄弟。

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

#### 3.1 二叉树的顺序存储结构 ####

> 对于完全二叉树可以采用顺序存储结构（即一维数组）进行存储，按照性质5对结点进行编号，编号为 i 的结点存放在数组第 i 个元素所分配的存储单元中，完全二叉树结点之间的逻辑关系通过数组元素的下标体现。`图3.1`是图的顺序存储结构。

> 对于非完全二叉树，通过补设一些虚线，使得二叉树的结点的编号与完全二叉树相同，再进行顺序存储。  
> 每个“虚节点”都将占据一个数组元素存储单元。  
> 非完全二叉树采用顺序存储结构会造成存储空间的浪费。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 3]

#### 3.2 二叉树的链式存储结构 ####

> 二叉树除了可以采用顺序存储结构实现存储外，还可以采用链式存储结构进行存储，与采用顺序存储结构相比，采用链式存储结构实现二叉树的存储显得更自然。二叉树最常用的链式存储结构是二叉链，每个结点包含三个域，分别是数据元素域data、左孩子链域lChild、右孩子链域rChild，结点的存储结构`如图3.2.1所示`

> ![在这里插入图片描述][20200708222939291.png]

> 与单链表带头结点和不带头结点的两种情况相似，二叉链存储结构的二叉树也有带头结点和不带头结点两种。对于`图3.1(a)`所示的二叉树，带头结点和不带头结点的二叉链存储结构的二叉树`如图3.2（a）`和`图3.2（b）`所示。

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 4]

## `四、二叉树的遍历` ##

#### 4.1 二叉树遍历的概念 ####

> 二叉树的遍历是指沿某条搜索路径访问二叉树，对二叉树中的每个结点访问一次且仅一次。这里的“访问”实际上是指对结点进行某种操作。二叉树的遍历方式有：前序遍历、中序遍历、后序遍历，这些遍历又有先左后右和先右后左之分，`如图4.1`所示。

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 5]

#### 4.2 前序遍历二叉树 ####

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 6]

> 前序遍历算法：若二叉树非空，先访问根结点，再前序遍历左子树，最后遍历右子树。`如图4.2所示`为二叉树的搜索路线。  
> 遍历图4.2所示的二叉树时，得到先序序列为:A、B、D、C、E、F。

#### 4.3 中序遍历二叉树 ####

> 中序遍历算法：若二叉树非空，先中序遍历左子树，在访问根结点，最后中序遍历右子树。  
> 遍历`图4.2`所示的二叉树时，得到的中序序列为：D、B、A、E、C、F。

#### 4.4 后续遍历二叉树 ####

> 后续遍历算法：若二叉树非空，先后序遍历左子树，再后序遍历右子树，最后访问根结点。  
> 后序遍历`图4.2`所示的二叉树时，得到的中序序列为：D、B、E、F、C、A。

> 在遍历的过程中，需要注意：  
> 1）在探索路线中，若访问结点均是第一次经过结点时进行的，则是前序遍历；若访问结点均是在第二次（或第三次）经过结点时进行的，则是中序遍历（后序遍历）。只要将搜索路线上所有在第一次、第二次和第三次经过的结点分别列表，即可分别得到该二叉树的前序序列、中序序列和后序序列。  
> 2）上述3种序列都是线性的序列，有且仅有一个开始结点和一个终端结点，其余结点都有且仅有一个前趋结点和一个后续结点。为了区别于树形结构中前趋（即双亲）结点和后续（即孩子）结点的概念，对上述3种线性序列，要在某结点的前趋和后续之前冠以其遍历次序名称。  
> 图4.2所示的二叉树中的结点C，其前序前趋结点是D，前序后续结点是E；中序前趋结点是E，中序后续结点是F；后序前趋结点是F，后序后续结点是A。但是就该树的逻辑结构而言，C的前趋结点是A，后续结点是E和F。

#### 4.5 二叉树遍历算法的实现 ####

public class BinTree {
        
    	char data;    // 根结点数据
    	BinTree left; // 左子树
    	BinTree right;// 右子树
    	
    	public BinTree(char data) {
        
    		this.data = data;
    		this.left = null;
    		this.right = null;
    	}
    
    	public static void preOrder(BinTree root) {
         //前序遍历
    		if(root != null) {
        
    			System.out.print(root.data + "-");
    			preOrder(root.left);
    			preOrder(root.right);
    		}
    	}
    	
    	public static void inOrder(BinTree root) {
         //中序遍历
    		if(root != null) {
        
    			inOrder(root.left);
    			System.out.print(root.data + "-");
    			inOrder(root.right);
    		}
    	}
    	
    	public static void postOrder(BinTree root) {
         //后序遍历
    		if(root != null) {
        
    			postOrder(root.left);
    			postOrder(root.right);
    			System.out.print(root.data + "-");
    		}
    	}
    
    	public static void main(String[] args) {
        
    		// 创建二叉树
    		BinTree root = new BinTree('A');
    		root.left = new BinTree('B');
    		root.right = new BinTree('C');
    
    		BinTree b = root.left;
    		b.left = new BinTree('D');
    
    		BinTree c = root.right;
    		c.left = new BinTree('E');
    		c.right = new BinTree('F');
    
    		System.out.println("先根遍历：");
    		preOrder(root);
    		System.out.println("");
    
    
    		System.out.println("中根遍历：");
    		inOrder(root);
    		System.out.println("");
    
    		System.out.println("后根遍历：");
    		postOrder(root);
    		System.out.println("");
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200705234535948.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200705234726281.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200706000107651.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200708222453344.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[20200708222939291.png]: https://img-blog.csdnimg.cn/20200708222939291.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200708223816799.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200709230545952.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200709233400264.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70