数据结构_树
一、树的定义
(1)有且仅有一个根节点;
(2)当结点个数大于1时,其余节点可分为互不相交的子树。 递归定义
概念:
结点的度
:节点拥有的子树数;
叶子(终端)结点
:度为0的结点
树的度
:树内各结点度的最大值
孩子
:结点的子树的根,对应 双亲,兄弟,祖先,子孙,堂兄弟
深度
:树中结点的最大层次
有序树
:树中结点的各子树看成是从左到右是有次序的,不能互换。反之为无序树。
二、森林
互不相交的树的集合。
三、二叉树
树的度小于等于2的树
满二叉树:除叶子节点外,其他结点的度都为2的二叉树。2^K-1个结点,k为深度
完全二叉树:对于深度为K的,有N个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点
性质:
(1) 在二叉树中,第i层的结点总数不超过2^(i-1);
(2) 深度为h的二叉树最多有(2^h)-1个结点(h>=1),最少有h个结点;
(3) 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;
(4) 具有n个结点的完全二叉树的深度为int(log2n)+1
(5)有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系:
若I为结点编号则 如果I<>1,则其父结点的编号为I/2;
如果2*I<=N,则其左儿子(即左子树的根结点)的编号为2*I;若2*I>N,则无左儿子;
如果2*I+1<=N,则其右儿子的结点编号为2*I+1;若2*I+1>N,则无右儿子。
(6)给定N个节点,能构成h(N)种不同的二叉树。
存储结构:
1、顺序存储结构
利用数组存储,结点在数组中的相对位置蕴含结点间的关系。如tree[i]的双亲为tree[n-1],n为(i+1)/2向下取整
左孩子tree[2i+1]和tree[2i+2]
适合完全二叉树,一般二叉树会造成空间的浪费。
2、链式存储结构
两种实现方式:
(1)左孩子指针域,数据域,右孩子指针域
(2)左孩子指针域,数据域,右孩子指针域,父节点指针域 便于找到结点双亲
二叉树的遍历:
先根序遍历、中根序遍历、后根序遍历
分享到:
相关推荐
知识共享-数据结构_树(雷惊风-超精细).
c语言数据结构_之_树
数据结构最基础,也是很重要的一部分。主要讲述树的算法,结构,及运用。
BitTree_mirror_树_数据结构_mirror遍历_MirrorMirror_源码
动态序列与动态树问题——浅谈几种常用数据结构_莫凡.pdf
一些数据结构的基本算法,例如树,图的遍历等。
数据结构_实验_课程设计_哈夫曼树_编码_代码&报告
1、绪2、线性表3、栈4、队列5、串6、数组7、广义表8、树9、图10、查找11、排序
数据结构_哈弗曼树编码.pdf
自己实现huffman树的代码,分享出来
数据结构_C语言_严蔚敏 吴伟民版_排序 课程源程序
实现数据结构中树的创建查询,删除和修改节点
一、实验目的 (1)理解动态查找表的动态生成过程; (2)任意给出一组数(不...(1)定义二叉排序树的数据结构; (2)实现二叉排序树的插入算法与查找算法,并建立二叉排序树; (3)进行数据查找和建树过程的比较。
B-树和B+树的C语言实现(数据结构)。
镜像对称的判断,主要是判断根节点的左右子树数据域是否相等,第二部分就是递归判断左子树的左子树与右子树的右子树以及右子树的左子树和左子树的右子树是否相等。
实验项目:树型结构的建立、遍历和应用 实验题目:二叉树存储结构的建立、遍历和应用 实验内容: 树型结构的遍历是树型结构算法的基础,本实验要求编写程序演示二叉树 的存储结构的建立方法、遍历过程以及应用。 ...
1、训练学生灵活应用所学数据结构知识,独立完成问题分析,结合数据结构理论知识,编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; 3.提高综合运用所学的...
给定一棵二叉树的前序遍历以及中序遍历结果,构造这棵二叉树,很明显,构造二叉树的方法使用递归的方法,而给定的前序以及中序遍历能够唯一确定这个二叉树。
基本要求:1、城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义,若两个城市之间不存在道路,则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些...
2. 实现哈夫曼树数据结构,使用哈夫曼树完成如下文档的编码与译码,假设该文档由5种符号字符(A、B、C、D、E)构成 ABACDEABBCEABAACCCDEACCBAABCCCA 3. 选做:实现二叉树的中序遍历线索化数据结构 4. 选做:使用...