1.树和森林
树是一种基本的数据结构。一棵树只有一个根结点。可以没有或有多个子结点。每个子结点以及子结点以下的结点又组成了一棵树,叫做子树。在一棵树结构中,只有父结点,没有子结点的结点叫做叶子结点
森林是多棵互不相交的树的集合。对树中的每个结点而言,其子树的集合就是森林。
2.二叉树
更多二叉树见
http://www.iteye.com/topic/561141
二叉树是另一种树型结构,它的特点是每个结点至多只有两棵子树,并且二叉树中的子树还有左右之分,它们的次序不能颠倒。
3.二叉树结点的表示
Class Node{
private Object data; //结点中存储的数据
private Node parent; //父结点的引用
private Node lChild; //左结点的引用
private Node rChild; //右结点的引用
}
4.二叉树的性质
1.在二叉树的第i层上至多有2^(i-1)个结点(i>=1)
2.深度为k的二叉树至多有(2^k)-1个结点(k>=1)
3.对任何一棵二叉树,如果其终端节点数为n0,度为2的结点数为n2,则n0=n2+1.
设n1为度为1的结点树,则总结点数n=n0+n1+n2
根据度与结点的对应关系有n=n1+2*n2+1(1表示一个根结点)
两式结合有n0=n2+1
4.具有n个结点的完全二叉树的深度是[]+1
完全二叉树形象的理解是它的上一层是满二叉树,而下一层要求右侧的孩子节点可以也只可以连续缺少,但是左侧不能缺少。性质4的证明如下:
假设深度为k,则该二叉树为满二叉树时结点最多为(2^k)-1,最少的情况是最后一层只有一个结点为2^(k-2)+1。则2^(k-2)+1<=n<=(2^k)-1,即<k<=+1,因为k是整数所以k=[]+1.
5.二叉排序树的建立和遍历
二叉排序树具有如下性质:1)左子树上所有结点的值均小于根结点的值2)右子树上所有结点的值均不小于根结点的值3)左右子树也分别是二叉排序树
建立二叉排序树的代码如下:
/**
* 将一个整型数组存储在一个查找二叉树中
* @param array 被存储的数组
* @return 查找二叉树的根节点
*/
public TreeNode arrayToTree(int[] array) {
TreeNode root = new TreeNode(array[0]);
for (int i = 1; i < array.length; i++) {
TreeNode node = new TreeNode(array[i]);
insertNode(node, root);
}
return root;
}
private void insertNode(TreeNode node, TreeNode root) {
if ((Integer) node.getObj() < (Integer) root.getObj()) {
if (root.getLchild() == null){
root.setLchild(node);
}
else
insertNode(node, root.getLchild());
} else {
if (root.getRchild() == null){
root.setRchild(node);
}
else
insertNode(node, root.getRchild());
}
}
遍历排序二叉树的代码如下:
/**
* 中序遍历二叉树
* @param root 二叉树的根节点
*/
public void traverseTree(TreeNode root) {
if (root != null) {
int data = (Integer) root.getObj();
traverseTree(root.getLchild());
System.out.println(data);
traverseTree(root.getRchild());
}
}
分享到:
相关推荐
本章节将深入探讨一种非线性数据结构——树,特别是二叉树,这是Java编程中非常重要的概念。线性结构如数组、链表、堆栈和队列在处理顺序数据时非常有用,但树结构则在表示复杂关系时更为有效。 树是一种非线性结构...
在深入探讨数据结构与算法之前,首先需理解其编程基础——Java语言。Java作为一种广泛应用的编程语言,其面向对象特性尤为突出,为数据结构与算法的实现提供了坚实的基础。 **1.1 Java语言基础知识** - **基本数据...
本章节作为开篇,旨在为读者打下坚实的Java编程基础,为后续深入学习数据结构与算法奠定理论基石。 ##### 1.1 Java语言基础知识 **1.1.1 基本数据类型及运算** 介绍了Java中的基本数据类型,包括整型(如`int`)...
- **树、森林与二叉树的相互转换**:讨论树、森林与二叉树之间如何相互转换。 - **树与森林的遍历**:讲解树与森林的遍历方法,包括前序、中序、后序遍历等。 - **由遍历序列还原树结构**:介绍如何根据遍历序列...
在《数据结构与算法 JAVA 版》这本书中,第一章主要介绍了Java编程语言的基础知识以及其面向对象的特点。 - **1.1 Java语言基础知识** - **1.1.1 基本数据类型及运算**:这部分内容涵盖了Java中的基本数据类型,如...
- **树、森林与二叉树的相互转换**:如何将树转换为二叉树或将二叉树转换回原来的树形式。 - **树与森林的遍历** - **由遍历序列还原树结构** ##### 6.5 Huffman树 - **二叉编码树**:介绍了一种用于编码的二叉树...
- **Strategy接口**:解释策略模式的概念,并讨论其在Java编程中的应用。 ##### 3.2 线性表的顺序存储与实现 - 讨论顺序存储的原理、优点(如访问速度快)和缺点(如插入删除操作效率低)。 ##### 3.3 线性表的...
在《数据结构与算法》这本书的第一章中,作者详细介绍了Java语言的基础知识以及Java的面向对象特性,为后续学习数据结构和算法打下了坚实的编程基础。 ##### Java语言基础知识 - **基本数据类型及运算**:介绍了...
训练计划中,参赛者将学习树和二叉树的定义、性质、遍历方式(前序、中序、后序)以及树和森林的存储结构等。特别地,赫夫曼树在数据压缩方面有着重要作用,构建最优二叉树和赫夫曼编码的算法也是学习的重点。 图论...
- **树与二叉树**:理解二叉树的定义、性质、遍历算法,树的表示和操作,以及森林与二叉树之间的转换。 - **图**:了解图的相关概念,如邻接矩阵和邻接表,理解图的搜索算法及其应用。 - **查找与排序**:掌握...
3. **树与二叉树**:掌握二叉树的定义、性质、表示方法和遍历算法,理解树的表示和操作,了解森林与二叉树的关系,以及它们在实际问题中的应用。 4. **图及其算法**:理解图的基本概念,掌握图的存储结构(如邻接...
- **树与二叉树**:掌握二叉树的定义、性质、遍历算法,以及树的表示和操作算法,了解森林与二叉树之间的转换。 - **图**:理解图的基本概念,如图的存储结构(邻接矩阵和邻接表)以及搜索算法(如深度优先搜索和...
- **树与二叉树**:二叉树的定义、性质、遍历算法,以及树和森林的相关内容。 - **图及其相关算法**:图的概念、存储结构、搜索算法及应用。 - **查找与排序**:典型算法的描述、复杂性分析及应用。 - **外部...
在IT领域,特别是数据结构和算法的学习中,"LevelOrder二叉树",通常指的是二叉树的一种遍历方式——层次遍历(也称为层序遍历)。这种遍历方法按照从上到下、从左到右的顺序访问二叉树的节点,形成一种类似于森林的...
在图论学习中,我们通常会遇到各种类型的图,如无向图、有向图、加权图、树等,以及相关的概念和算法。在这个Graph-Theory存储库中,开发者李恩(Yann Lee)提供了注释丰富的Java代码,可能是为了帮助初学者或有经验...