Java,数据结构和算法,八大数据结构,树,二叉树、B树

树:是由结点(顶点)和边组成,可能是非线性的,且不存在着任何环的一种数据结构;

空树:没有结点的树称为空(null或empty)树;

非空树:一棵非空的树包括一个根结点,还(很可能)有多个附加结点,所有结点构成一个多级分层结构;

结点:使用树结构存储的每一个数据元素都被称为“结点”;图中,数据元素 A 就是一个结点;

父结点(双亲结点)、子结点和兄弟结点:对于图 中的结点 A、B、C、D 来说,A是 B、C、D结点的父结点(也称为“双亲结点”),而 B、C、D 都是 A结点的子结点(也称“孩子结点”)。对于B、C、D来说,它们都有相同的父结点,所以它们互为兄弟结点。

结点的度和层次:对于一个结点,拥有的子树数(结点有多少分支)称为结点的度(Degree);图中,根结点 A下分出了 3个子树,所以,结点 A的度为 3。

深度:定义一棵树的根结点层次为1,其他结点的层次是其父结点层次加1,一棵树中所有结点的层次的最大值称为这棵树的深度。

有序树和无序树:如果树中结点的子树从左到右看,谁在左边,谁在右边,是有规定的,这棵树称为有序树;反之称为无序树。

森林:由 m(m >= 0)个互不相交的树组成的集合被称为森林。

二叉树

二叉树:每个节点最多只能有两个子节点;简单地理解,满足以下两个条件的树就是二叉树:

1、本身是有序树;

2、树中包含的各个节点的度不能超过 2,即只能是 0、1或者 2;

满二叉树:

如果二叉树中除了叶子结点,每个结点的度都为 2,则此二叉树称为满二叉树。

完全二叉树:

一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。

二叉树的遍历方式:前序遍历,后续遍历,中序遍历;

二叉树的遍历

前序遍历:先遍历父节点,在遍历左子树;然后是右子树;

中序遍历:先遍历左子树,在遍历父点击,在遍历右子树;

后序遍历:先遍历左子树,在遍历右子树,然后是父节点;

二叉树的删除

1、如果删除的叶子节点,删除该节点;

2、如果删除的非叶子节点,删除该子树;

顺序存储二叉树

将二叉树存储在一个数组中,通过存储元素的下标反映元素之间的父子关系;

以数组的方式来存储二叉树,但依然可以前序、中序、后序遍历树;

第N个元素的左子树节点为:2*N+1;

第N个元素的右子树节点为:2*N+2;

第N个元素的父节点为:(N-1)/2;

N表示二叉树中的第几个元素(从0开始编号)

堆排序会用到顺序存储二叉树;

线索化二叉树

N个节点的二叉链表中含有N+1【公式2n-(n-1)=n+1】个空指针域;

利用二叉链表中的空指针域,存放指向该节点在某种遍历次序下的前驱和后继节点的指针(珍重附加的指针称为"线索");

这种加了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree);

根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树;

一个节点的前一个节点,称为前驱;

一个节点的后一个节点,称为后继;

顺序存储二叉树——规则

第N个元素的左子树节点为:2*N+1;

第N个元素的右子树节点为:2*N+2;

第N个元素的父节点为:(N-1)/2;

N表示二叉树中的第几个元素(从0开始编号)

B树

B树,即二叉搜索树:1、所有非叶子结点至多拥有两个儿子(Left和Right);2、所有结点存储一个关键字;3、非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;

B-树

B-树,是一种多路搜索树(并不是二叉的):1、定义任意非叶子结点最多只有M个儿子;且M>2;2、根结点的儿子数为[2, M];3、除根结点以外的非叶子结点的儿子数为[M/2, M];4、每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字);5、非叶子结点的关键字个数=指向儿子的指针个数-1;6、非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];7、非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;8、所有叶子结点位于同一层;

B+树

B+树是应文件系统所需而产生的一种B-树的变形树,一棵m阶的B+树和m 阶的B-。

树的差异在于:1、有n 棵子树的结点中含有n 个关键码;2、所有的叶子结点中包含了全部关键码的信息,及指向含有这些关键码记录的指针,且叶子结点本身依关键码的大小自小而大的顺序链接;3、所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键码。

B*树

B*树是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;

B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2);B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

案例:二叉树实现

public class Element<E> {

	// 存放数据
	private E data;

	// 左子树
	private Element<E> leftElement;

	// 右子树
	private Element<E> rightElement;

	public Element(E data) {
		super();
		this.data = data;
	}

	public E getData() {
		return data;
	}

	public void setData(E data) {
		this.data = data;
	}

	public Element<E> getLeftElement() {
		return leftElement;
	}

	public void setLeftElement(Element<E> leftElement) {
		this.leftElement = leftElement;
	}

	public Element<E> getRightElement() {
		return rightElement;
	}

	public void setRightElement(Element<E> rightElement) {
		this.rightElement = rightElement;
	}

	@Override
	public String toString() {
		return "BinaryTree [data=" + data + "]";
	}

	// ================================================================================//
	// ===operate
	// ================================================================================//

	// 前序遍历
	public void preOrderTraversal() {
		// 1、输出父节点
		System.out.println(this);
		// 2、递归左子树
		if (this.leftElement != null) {
			this.leftElement.preOrderTraversal();
		}
		// 3、递归右子树
		if (this.rightElement != null) {
			this.rightElement.preOrderTraversal();
		}
	}

	// 中序遍历
	public void infixOrderTraversal() {
		// 1、递归左子树
		if (this.leftElement != null) {
			this.leftElement.infixOrderTraversal();
		}
		// 2、输出父节点
		System.out.println(this);
		// 3、递归右子树
		if (this.rightElement != null) {
			this.rightElement.infixOrderTraversal();
		}
	}

	// 后序遍历
	public void postOrderTraversal() {
		// 1、递归左子树
		if (this.leftElement != null) {
			this.leftElement.postOrderTraversal();
		}
		// 2、递归右子树
		if (this.rightElement != null) {
			this.rightElement.postOrderTraversal();
		}
		// 3、输出父节点
		System.out.println(this);
	}

}
/**
 * 二叉树节点
 * 
 * @param <E>
 */
public class BinaryTree<E> {

	private Element<E> root;

	public void setRoot(Element<E> root) {
		this.root = root;
	}

	// ================================================================================//
	// ===operate
	// ================================================================================//

	// 前序遍历
	public void preOrderTraversal() {
		if (this.root != null) {
			this.root.preOrderTraversal();
		} else {
			System.out.println("二叉树为空");
		}
	}

	// 中序遍历
	public void infixOrderTraversal() {
		if (this.root != null) {
			this.root.infixOrderTraversal();
		} else {
			System.out.println("二叉树为空");
		}
	}

	// 后续遍历
	public void postOrderTraversal() {
		if (this.root != null) {
			this.root.postOrderTraversal();
		} else {
			System.out.println("二叉树为空");
		}
	}

}
public class BinaryTreeDemo {

	public static void main(String[] args) {
		BinaryTree<String> binaryTree = new BinaryTree<String>();
		// 手动创建二叉树
		Element<String> element1 = new Element<String>("1");
		Element<String> element2 = new Element<String>("2");
		Element<String> element3 = new Element<String>("3");
		Element<String> element4 = new Element<String>("4");
		Element<String> element5 = new Element<String>("5");
		Element<String> element6 = new Element<String>("6");
		Element<String> element7 = new Element<String>("7");
		// 1 的子节点:2 和 3
		element1.setLeftElement(element2);
		element1.setRightElement(element3);
		// 2的子节点: 4和5
		element2.setLeftElement(element4);
		element2.setRightElement(element5);
		// 3的子节点: 6和7
		element3.setLeftElement(element6);
		element3.setRightElement(element7);
		binaryTree.setRoot(element1);

		System.out.println("前序遍历:");
		binaryTree.preOrderTraversal();
		System.out.println("中序遍历:");
		binaryTree.infixOrderTraversal();
		System.out.println("后序遍历:");
		binaryTree.postOrderTraversal();
	}

}

案例:顺序存储二叉树

/**
 * 顺序存储二叉树
 */
public class ArrayBinaryTree {

	private int[] array;

	public ArrayBinaryTree(int[] array) {
		this.array = array;
	}

	public void preOrder() {
		this.preOrder(0);
	}

	/**
	 * 前序遍历
	 * 
	 * @param index 数组的下标
	 */
	public void preOrder(int index) {
		// 数组为空
		if (array == null || array.length <= 0) {
			System.out.println("数组为空,不能按照前序遍历.");
			return;
		}
		System.out.println(array[index]);
		// 向左递归
		if ((2 * index + 1) < array.length) {
			preOrder(2 * index + 1);
		}
		// 向右递归
		if ((2 * index + 2) < array.length) {
			preOrder(2 * index + 2);
		}
	}

	public void infixOrder() {
		this.infixOrder(0);
	}

	/**
	 * 中序遍历
	 * 
	 * @param index 数组的下标
	 */
	public void infixOrder(int index) {
		// 数组为空
		if (array == null || array.length <= 0) {
			System.out.println("数组为空,不能按照前序遍历.");
			return;
		}
		// 向左递归
		if ((2 * index + 1) < array.length) {
			infixOrder(2 * index + 1);
		}
		System.out.println(array[index]);
		// 向右递归
		if ((2 * index + 2) < array.length) {
			infixOrder(2 * index + 2);
		}
	}

	public void postOrder() {
		this.postOrder(0);
	}

	/**
	 * 后序遍历
	 * 
	 * @param index 数组的下标
	 */
	public void postOrder(int index) {
		// 数组为空
		if (array == null || array.length <= 0) {
			System.out.println("数组为空,不能按照前序遍历.");
			return;
		}
		// 向左递归
		if ((2 * index + 1) < array.length) {
			postOrder(2 * index + 1);
		}
		// 向右递归
		if ((2 * index + 2) < array.length) {
			postOrder(2 * index + 2);
		}
		System.out.println(array[index]);
	}

}
public class ArrayBinaryTreeDemo01 {

	public static void main(String[] args) {
		int[] array = { 1, 2, 3, 4, 5, 6, 7 };
		ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(array);
		System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++");
		arrayBinaryTree.preOrder(); // 1,2,3,4,3,6,7
		System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++");
		arrayBinaryTree.infixOrder(); // 4,2,5,1,6,3,7
		System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++");
		arrayBinaryTree.postOrder(); // 4,5,2,6,7,3,1
		System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++");
	}

}
原文链接:,转发请注明来源!