免费的做微博的网站模板,wordpress 页面 首页,菜鸟教程网站,怎样用电脑和网訨自己做网站一、树
1.树的定义
与线性表不同#xff0c;树是一种非线性的数据结构#xff0c;由N(N0)个结点组成的具有层次关系的集合#xff1b;因其形状类似生活中一颗倒挂着的树#xff0c;故将其数据结构称为树。 2.树的相关概念 根结点 没有前驱的结点#xff0c;称为根…一、树
1.树的定义
与线性表不同树是一种非线性的数据结构由N(N0)个结点组成的具有层次关系的集合因其形状类似生活中一颗倒挂着的树故将其数据结构称为树。 2.树的相关概念 根结点 没有前驱的结点称为根结点子树以某个结点为根结点的所有后代结点(包括此结点)为该结点的子树例如B、E、F组成的树是A的子树结点的度某个结点后继结点的个数称为结点的度叶(终端)结点某个结点后继结点的个数为0称为叶结点分支(非终端)结点某个结点后继结点的个数非0称为分支结点双亲(父)结点某个结点的前驱结点称为该结点的双亲结点孩子(子)结点某个结点的后继结点称为该结点的孩子结点兄弟结点某两个结点的前驱结点相同则称为兄弟结点堂兄结点某两个结点在同一个层次上称为堂兄结点祖先某个结点到根结点的一条路线上的结点统称为该结点的祖先子孙某个结点的所有后代结点统称为该结点的子孙树的度最大的结点的度称为树的度树的高度(深度)根结点到叶结点所经过结点的个数最大的称为树的高度或深度结点的层级某结点与根结点连线所含义的结点个数森林M(M2)个互不相交的树称为森林 总结
一个树其任意子树是互不相交的否则就不叫树而是图这一树形结构如B、C、D为根组成的树不存在相交情况。任意一个树都可以看成根和子树子树又可以看成根和子树所以树这一结构是由递归搭建的。
3.树的表示
对树这一结构有明确的了解后又有一个新的问题我们该如何的去表示的树的结构呢常见的有孩子表示法双亲表示法孩子双亲表示法孩子兄弟表示法这里将介绍最好理解的孩子表示法和优点明显的孩子兄弟表示法
i.孩子表示法
#define MAX 10 // 已知树的最大的深度typedef int TDatetype;typedef struct Tree
{TDatetype date;struct Tree* child[MAX];
}Tree;
ii.左孩子右兄弟表示法
typedef int TDatetype;typedef struct Tree
{TDatetype date;struct Tree* child;struct Tree* brother;
}Tree; 4.树的实际应用
我们文件的存储方式就是以树这一结构存储每一个盘即为一个树所有盘则组成一个森林下面则是Linux系统下文件的存储结构。 二、二叉树
1.二叉树的定义
在树的定义基础上树的度最大不超过2的(每个结点的度最大不超过2的)即为二叉树。注二叉树有左孩子右孩子之分 2.特殊的二叉树
i.满二叉树 满二叉树的定义树的深度为h每一层都达到含有结点的最大个数即第x(0xh)层结点个数 2^(x-1)
ii.完成二叉树 完全二叉树的定义树的深度为h前h-1层结点个数达到最大值第h层从左到右有连续的结点。
3.二叉树的性质
第H层结点个数2^(H-1)高度为H的二叉树所含有结点个数的最大值为2^H-1N个结点的满二叉树其高度为以2为底log(N1)N个结点的完全二叉树其高度为以2为底log(NX1)X为相同高度的满二叉树与完全二叉树的结点个数差的绝对值终端结点的个数 度为2的结点个数 1
4.二叉树的表示
i.二叉树的顺序结构
二叉树的顺序结构将一颗二叉树的数据以层为顺序依次存储在数组中保留空结点的位置。 typedef int BTDateType; // 重定义树的数据类型typedef struct BinaryTree
{BTDateType* date; // 动态顺序表int size; // 当前顺序表存储数据的个数int capacity; // 当前顺序表的容量大小
}BinaryTree;为什么要这么设计呢
因为我们通过数组下标可以得出其父亲或者两个孩子的结点位置
某结点左孩子的下标 该结点的下标 * 2 1某结点右孩子的下标 该结点的下标 * 2 2某结点的父亲下标 (该结点的下标 - 1) / 2
读者若不相信可以以上面示图为例子代入数据进行自我验证
根据此特性首先我们就可以理解了为什么要留着空结点的位置而不是直接把数据依次存入~最后可以得出结论适合于存储完全二叉树而不适合存储普通二叉树因为普通二叉树会造成大量的空间浪费。
ii.二叉树的链式结构
二叉树的链式结构声明如下孩子不存在则用NULL表示
typedef int BTDatetype;typedef struct BinaryTree
{BTDatetype date; // 数据struct Tree* lift; // 左孩子struct Tree* right; // 右孩子
}BT;
