织梦做导航网站,在线登录qq聊天,长春建站优化加徽信xiala5,中国反钓鱼网站联盟目录
一#xff0c;树的概念及结构 1#xff0c;树的定义 2#xff0c;树结点的分类及关系 3#xff0c;树的表示
二#xff0c;二叉树的概念及结构 1#xff0c;二叉树的定义 2#xff0c;特殊的二叉树 3#xff0c;二叉树的性质 4#xff0c;二叉树的存储结构
1树的概念及结构 1树的定义 2树结点的分类及关系 3树的表示
二二叉树的概念及结构 1二叉树的定义 2特殊的二叉树 3二叉树的性质 4二叉树的存储结构
1顺序存储
2链式储存 一树的概念及结构 1树的定义
树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 树Tree是nn0个结点的有限集 n0时称为空树 在任意一颗非空树中 1有且仅有一个特定的称为根Root的结点 2当n1时其余结点可分为mm0个互不相交的有限集T1T2......Tm其中每一个集合本身又是一棵树并且称为跟的子树SubTree 如下图所示 注意树形结构中子树之间不能有交集否则就不是树形结构 2树结点的分类及关系 结点的度一个结点含有的子树的个数称为该结点的度 如上图A的为4
叶结点或终端结点度为0的结点称为叶结点 如上图KGLMN...等结点为叶结点
非终端结点或分支结点度不为0的结点 如上图BCE...等结点为分支结点
双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父节点
孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点
兄弟结点具有相同父结点的结点互称为兄弟结点 如上图B、C是兄弟结点
树的度一棵树中最大的结点的度称为树的度 如上图树的度为4
结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推
树的高度或深度树中结点的最大层次 如上图树的高度为4
堂兄弟结点双亲在同一层的结点互为堂兄弟如上图H、I互为堂兄弟结点
结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先C是GH的祖先
子孙以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙GH是C的子孙
森林由mm0棵互不相交的树的集合称为森林 3树的表示 树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既然保存值域也要保存结点和结点之间的关系实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法 typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
};
图解 二二叉树的概念及结构 1二叉树的定义 二叉树Binary Tree是nn0) 个结点的有限集合 该集合或者为空集称为空二叉树 或者由一个根结点和两颗互不相交的分别为根结点的左子树和右子树的二叉树组成 图示 由上图可以看出 1二叉树不存在度大于2的结点 2二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树 二叉树具有以下五种基本形态 2特殊的二叉树
1斜树 所有的结点都只有左子树的二叉树叫左斜树 所有的结点都只有右子树的二叉树叫右斜树 斜树图示 2满二叉树 一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是 说如果一个二叉树的层数为K且结点总数是2^k-1 则它就是满二叉树 3完全二叉树 完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K 的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树 3二叉树的性质
1若规定根结点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1)个结点
2若规定根结点的层数为1则深度为h的二叉树的最大结点数是 2^h-1
3对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n1 ,则有 n0n11
4若规定根结点的层数为1具有n个结点的满二叉树的深度hlog2(n1)
5对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有结点从0开始编号则对于序号为i的结点有 1若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点 2若2i1n左孩子序号2i1 3若2i1n右孩子序号2i2 4二叉树的存储结构 二叉树一般可以使用两种结构存储一种顺序结构一种链式结构 1顺序存储 顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储 二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 2链式储存 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系; 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址; 链式结构又分为二叉链和三叉链 typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* _pLeft; // 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
}// 三叉链
struct BinaryTreeNode
{struct BinTreeNode* _pParent; // 指向当前节点的双亲struct BinTreeNode* _pLeft; // 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
}第一阶段就到这里了带大家先了解一下树和二叉树的原理
后面博主会陆续更新
如有不足之处欢迎来补充交流
完结。。。
