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());
}
}
分享到:
相关推荐
画完图之后我们会发现,所谓“二叉树的镜像”就是把二叉树中所有子树的左孩子和右孩子进行交换。因此需要遍历二叉树所有的结点,在遍历的同时交换非叶子结点的左右子树。遍历我们可以使用先序遍历,首先判断当前根...
数据结构——树的概念和二叉树PPT学习教案.pptx
【数据结构(Java)】树 - 二叉树(csdn)————程序
树的存储结构、森林及与二叉树的转换树的存储结构、森林及与二叉树的转换
这是二叉树的java算法,基本思路是通过二叉树的遍历,完成的java语法的算法编程
数据结构(清华大学版)——树和二叉树
6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树 6.4 线索二叉树 6.5 树和森林 6.6 哈夫曼树
森林转换成二叉树c语言实现的数据结构算法
(1)数据结构与算法概念解析 (2)数据结构之数组 (3)数据结构之栈 (4)数据结构之队列 (5)数据结构之链表 (6)数据结构之二叉树 (7)数据结构之霍夫曼树 (8)数据结构之红黑树(一)——基础分析 ...
无论您是Java编程的初学者还是有经验的程序员,该资源都将为您提供有价值的指导和支持,帮助您掌握Java中实现二叉树打印的方法。我们相信,该资源将成为想提高算法设计技能的Java程序员的宝贵参考资料。
第二天 平衡二叉树 6天通吃树结构—— 第一天 二叉查找树 算法速成系列(15)算法系列15天速成——第十五天 图【下】(大结局) 算法系列15天速成——第十四天 图【上】 算法系列15天速成——第十三天 树操作【下】 ...
通过“图片压缩编码”的编程实践,学习树、遍历二叉树、哈夫曼树、哈夫曼编码和他们的编程应用。 (1)掌握树的存储结构 (2)掌握二叉树的三种遍历方法 (3)掌握并理解Huffman树、Huffman编码等知识和应用 (4)掌握文件的...
二叉树的建立,遍历算法(递归与非递归,基于对列或堆栈)统计二叉树中叶子结点的个数,统计二叉树中结点的总数,求二叉树的深度(后序遍历),求二叉树的宽度(具有结点数最多的层上的结点数,已知二叉树中序遍历和...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
(2)选取与合并:在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树,这棵新的二叉树的根结点的权值为其左右子树根结点的权值之和。 (3)删除与加入:在F中删除作为左、右子树的两棵...
用java建一个简单的二叉树 比较基础 很适合初学者看看
这是一个基于生成树的算法,可以先用回溯、递推求出二叉树,再用二叉树求解,主要用于遍历问题!
java算法二叉树,通俗易懂,我看過的文檔中,這個算是解析得清楚了
5.5 树、森林与二叉树的转换.doc5.5 树、森林与二叉树的转换.doc5.5 树、森林与二叉树的转换.doc
1、假设二叉树的结点值是字符,根据输入的一颗二叉树的标明了空子树的完整先根遍历序列,建立一棵以二叉链表表示的二叉树。 2、对二叉树进行先根、中根和后根遍历操作,并输出遍历序列,同时观察输出序列是否与逻辑...