数据结构 – 树以及Java代码实现

我们知道数据结构根据数据的存储方式分为线性结构和非线性结构,而树就属于非线性结构。

树是由n(n>0)个有限结点组成的具有层次结构的集合。当n=0时,叫做空树。

把这种数据结构叫做树是因为它看起来像一棵“倒挂的树”,即根朝上,叶朝下的树。

它具有以下特征:

  • 没有父结点的树叫做根结点
  • 每个结点可以有一个或多个子结点
  • 每个非根结点只有一个父结点
数据结构 - 树以及Java代码实现

树的基本术语

  • 结点的度:结点的子树个数

  • 树的度:树中所有结点的度的最大值

  • 路径和路径长度:从结点n 1 到n k路径 是一个结点序列n 1 、n 2 、… 、n k

    其中n i 是n i+1 的父结点。路径所包含的边的个数叫做 路径的长度

  • 结点的层次:规定根结点的层次为1层,其他任一结点的层次为其父结点的层次加一

  • 树的深度:树中所有结点的层次最大值是这棵树的深度

二叉树

二叉树其实就是树的一种特殊情况。区别在于:

  • 二叉树的每个结点最多只能有两个结点
  • 二叉树中的结点是区分左右的。顺序不能颠倒

二叉树拥有如下性质:

  • 在二叉树的第i层最多有2 i-1 个结点
  • 深度为k的二叉树,最多有2 k – 1 个结点 (k>=1)
  • n 0 = n 2 + 1,n 0 为度数为0的结点数,n 度数为2的结点数

斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

左斜树

数据结构 - 树以及Java代码实现

右斜树

数据结构 - 树以及Java代码实现

满二叉树

在一棵二叉树中。如果所有结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。

数据结构 - 树以及Java代码实现

完全二叉树

对一颗具有n个结点的二叉树按层编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树。

数据结构 - 树以及Java代码实现

完全二叉树的性质:

  • 具有n个结点的完全二叉树的深度[log 2 n] + 1,其中[log2n]是向下取整。

二叉树的存储结构

二叉树的结点可以使用一维数组进行存储,或者是链表进行存储。

顺序存储

二叉树的顺序存储就是利用一维数组存储二叉树的结点,结点的存储位置就是数组的下标索引

由此,我们知道二叉树的顺序存储结构的优点是查找效率高,而且增加和删除结点的效率高。

缺点就是当二叉树结构不是完全二叉树时,容易出现空间浪费的问题。

例如:当出现斜树的情况时,那么数组中大部分的位置都是没有存储结点的,大大浪费了空间。

数据结构 - 树以及Java代码实现

对应一维数组的存储如下:

数据结构 - 树以及Java代码实现

链式存储

二叉树的链式存储就是使用链表进行结点的存储。

结点的结构存在一个数据域,两个指针域。

数据结构 - 树以及Java代码实现

二叉树的遍历

二叉树的遍历是指从二叉树的根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次,且仅被访问一次。

二叉树的访问次序可以分为四种:

  • 前序遍历
  • 中序遍历
  • 后序遍历
  • 层序遍历

前序遍历

前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。

中序遍历

中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。在遍历左、右子树时,仍然先遍历左子树,然后访问根结点,最后遍历右子树。

后序遍历

后序遍历首先遍历左子树,然后遍历右子树,最后访问根结点,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后遍历根结点。

层次遍历

层次遍历就是按照树的层次自上而下的遍历二叉树。

二叉树的代码实现

顺序存储

package com.xgc.tree.binarytree.sequentialstoreage;

public class BinaryTree {
	
	Object[] arr;
	
	public void buildTree(Object[] arr) {
		this.arr = arr;
	}
	
	/**
	 * 先序遍历
	 * @param root 树的根结点
	 */
	public void preOrderTree() {
		preOrderTree(0);
	}
	
	private void preOrderTree(int index) {
		if (arr==null || arr.length == 0) return;
		System.out.print(arr[index] + " ");
		if((index*2+1)<arr.length){
			preOrderTree(index*2+1);
        }
        if((index*2+2)<arr.length){
        	preOrderTree(index*2+2);
        }
	}
	
	//中序和后序遍历 与 先序遍历类似,这里就不写了
	//层次遍历就更简单了,遍历数组就可以了
}
复制代码

链式存储

package com.xgc.tree.binarytree.linkedstoreage;

/**
 * 二叉树的结点
 * @author xgc
 *
 */
public class TreeNode {

	Object data;
	//左节点
	TreeNode left;
	//右节点
	TreeNode right;
	
	public TreeNode(Object data) {
		this.data = data;
	}
	
	public TreeNode(TreeNode left , Object data, TreeNode right) {
		this.left = left;
		this.data = data;
		this.right = right;
	}
	
}
复制代码
package com.xgc.tree.binarytree.linkedstoreage;

/**
 * 二叉树的结点
 * @author xgc
 *
 */
public class TreeNode {

	Object data;
	//左节点
	TreeNode left;
	//右节点
	TreeNode right;
	
	public TreeNode(Object data) {
		this.data = data;
	}
	
	public TreeNode(TreeNode left , Object data, TreeNode right) {
		this.left = left;
		this.data = data;
		this.right = right;
	}
	
}

复制代码

测试

package com.xgc.tree.binarytree.linkedstoreage;

public class BinaryTreeTest {

	public static void main(String[] args) {
		Object[] arr = {1,2,3,4,5,6,7,8,9};
		BinaryTree tree = new BinaryTree();
		TreeNode root = tree.buildTree(arr);
		System.out.print("先序遍历 ");
		tree.preOrderTree(root);
		System.out.println();
		
		System.out.print("中序遍历 ");
		tree.inOrderTree(root);
		System.out.println();
		
		System.out.print("后序遍历 ");
		tree.postOrderTree(root);
		System.out.println();
		
		System.out.print("层次遍历 ");
		tree.levelOrderTree(root);
		System.out.println();
	}

}
复制代码

执行结果如下:

先序遍历 1 2 4 8 9 5 3 6 7 
中序遍历 2 4 8 9 5 1 3 6 7 
后序遍历 2 4 8 9 5 3 6 7 1 
层次遍历 1 2 3 4 5 6 7 8 9 
复制代码

二叉搜索树

二叉搜索树:一颗二叉树,可以为空。如果不为空,满足如下性质:

  • 非空左子树所有结点的值都小于根结点的值

  • 非空右子树所有结点的值都大于根结点的值

  • 左子树和右子树都是二叉搜索树

二叉搜索树不会出现重复元素,所以遇到重复元素的时候就不插入。

二叉搜索树操作的函数有:

  • 插入新结点
  • 删除结点
  • 查找最大值和最小值
  • 查找指定值的结点

在上面的操作中,删除结点的操作比较复杂,所以介绍删除结点操作的实现思路,其他的就不介绍了,看代码实现就可以了。

二叉搜索树的删除操作分类讨论:

  1. 要删除的结点没有子结点,即是叶节点。

    这里我们将要删除结点的父结点的left或right设为NULL就可以了

    这里的left、right取决于要删除的结点是父结点的左结点或右结点

数据结构 - 树以及Java代码实现

像上图current是当前要删除的结点,我们只要把parent.left设为null即可

  1. 删除的结点有一个孩子结点

    将这个孩子结点赋值给要删除结点的父结点的left或right

数据结构 - 树以及Java代码实现
  1. 要删除的结点有两个孩子结点

    这种情况比较复杂,我们引入 后继结点 的概念。

    后继结点:如果将一棵二叉树按照中序遍历的方式输出,则任一结点的下一个结点就是该结点的后继结点。

    • 后继节点为要删除结点的右结点

      将要删除的结点用后继结点替换即可,注意处理好删除结点的left和后继结点的right

数据结构 - 树以及Java代码实现
数据结构 - 树以及Java代码实现
  • 后继节点为要删除结点的右孩子的左子

    这种情况比较复杂,看动图就明白了

数据结构 - 树以及Java代码实现
数据结构 - 树以及Java代码实现

二叉搜索树的代码实现

package com.xgc.tree.binarysearchtree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉搜索树
 * @author xgc
 *
 */
public class BinarySearchTree {
	
	/**
	 * 二叉搜索树的结点
	 * @author xgc
	 *
	 */
	private class Node {
        int data; // 数据域
        Node right; // 右子树
        Node left; // 左子树
        
        public Node(int data) {
        	this.data = data;
        }

		public Node() {
		}
	}
	
	//树的根节点
	private Node root;
	
	/**
	 * 根据指定的值找出二叉搜索树中对应的结点
	 * @param data
	 * @return
	 */
	public Node find(int data) {
		Node current = root;
		while(current.data != data) {
			if (data > current.data) {
				current = current.right;
			}
			if (data < current.data) {
				current = current.left;
			}
			if (current == null) {
				return null;
			}
		}
		return current;
	}
	
	/**
	 * 二叉搜索树的插入
	 * @param data
	 */
	public void insert(int data) {
		//要插入的结点
		Node p = new Node(data);
		
		if (root == null) {
			root = p;
		} else {
			Node parent = new Node();
			Node current = root;
			while(true) {
				parent = current;
				
				if (data>current.data) {
					current = current.right;
					if (current==null) {
						parent.right = p;
						return;
					}
				} else if(data == current.data) {
					return;
				} else {
					current = current.left;
					if (current==null) {
						parent.left = p;
						return;
					}
				}
			}
		}
	}
	

	/**
	 * 删除指定的数据
	 * @param data
	 * @return 删除操作是否成功
	 */
	public boolean delete(int data) {
		Node current = root;
		Node parent = new Node();
		
		boolean isRightChild = true;
		
		//查找要删除的结点
		while(current.data != data) {
			parent = current;
			if (data > current.data) {
				current = current.right;
				isRightChild = true;
			} else {
				current = current.left;
				isRightChild = false;
			}
		}
		
		//要删除的结点为叶结点
		if (current.right == null && current.left == null) {
			if (current == root) {
				root = null;
			} else {
				if (isRightChild) {
					parent.right = null;
				} else {
					parent.left = null;
				}
			}
			
			return true;
		}
		//要删除的结点只有一个子结点
		else if(current.left == null) {
			if (current == root) {
				root = current.right;
			}else if(isRightChild) {
				parent.right = current.right;
			}else {
				parent.left = current.right;
			}
			
			return true;
		}
		else if(current.right == null) {
			if (current == root) {
				root = current.left;
			}else if(isRightChild) {
				parent.right = current.left;
			}else {
				parent.left = current.left;
			}
			
			return true;
		}
		//要删除的结点有两个子结点
		else {
			Node successor = getSuccessor(current);
			
			if (current == root) {
				root = successor;
			} else if (isRightChild) {
				parent.right = successor;
			} else {
				parent.left  =successor;
			}
			
			successor.left = current.left;
			return true;
		}
	}

	/**
	 * 获取给定结点的后继结点
	 * 不仅获取后继结点,还对删除结点的右子树结构进行了调整
	 * @param current
	 * @return 后继结点
	 */
	private Node getSuccessor(Node node) {
		Node successorParent = node;
		Node successor = node;
		Node current = node.right;
		
		while(current!=null) {
			successorParent = successor;
			successor = current;
			current = current.left;
		}
		//到这里后继结点已经找好了
		
		//如果后继结点为要删除结点的右结点的左子,调整一下要删除结点的右子树
		if (successor != node.right) {
			successorParent.left = successor.right;
			successor.right = node.right;
		}
		return successor;
	}
	
	public void levelOrderTree() {
		if (root == null) return;
		Queue<Node> nodes = new LinkedList<>();
		nodes.add(root);
		while (!nodes.isEmpty()) {
			Node node = nodes.poll();
			System.out.print(node.data + " ");
			if (node.left != null) {
				nodes.add(node.left);
			}
			if (node.right != null) {
				nodes.add(node.right);
			}
		}
	}
	
	public void show(Node node) {
		System.out.println(node.data);
	}
}
复制代码

测试

package com.xgc.tree.binarysearchtree;

public class BinarySearchTreeTest {

	public static void main(String[] args) {
		BinarySearchTree tree = new BinarySearchTree();
		tree.insert(5);
		tree.insert(6);
		tree.insert(7);
		tree.insert(3);
		tree.insert(4);
		tree.insert(7);
		
		tree.levelOrderTree();
		
		tree.delete(3);
		
		System.out.println();
		tree.levelOrderTree();
		
		System.out.println();
		tree.show(tree.find(7));
	}

}
复制代码

执行结果为:

5 3 6 4 7 
5 4 6 7 
7
复制代码

原文 

https://juejin.im/post/5ef49997e51d4534a36151f0

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 数据结构 – 树以及Java代码实现

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址