sns网站是什么,广州网站快速排名优化,wordpress 响应式主题,电脑什么软件做短视频网站定义 最多有两棵子树的有序树#xff0c;称为二叉树。二叉树是一种特殊的树。 递归定义#xff1a;二叉树是n(n0)个有限结点构成的集合。N0称为空二叉树#xff1b;n0的二叉树由一个根结点和两互不相交的#xff0c;分别称为左子树和右子树的二叉树构成。 二叉树中… 定义 最多有两棵子树的有序树称为二叉树。二叉树是一种特殊的树。 递归定义二叉树是n(n0)个有限结点构成的集合。N0称为空二叉树n0的二叉树由一个根结点和两互不相交的分别称为左子树和右子树的二叉树构成。 二叉树中任何结点的第1个子树称为其左子树左子树的根称为该结点的左孩子二叉树中任何结点的第2个子树称为其右子树左子树的根称为该结点的右孩子。如下图是一个二叉树 图1.二叉树 满二叉树和完全二叉树 在一棵二叉树中如果所有分支结点都存在左子树和右子树并且叶子结点都在同一层上这样的二叉树称作满二叉树。一棵深度为k且由2k-1个结点的二叉树称为满二叉树。 如果一棵具有n个结点的二叉树的结构与满二叉树的前n个结点的结构相同这样的二叉树称作完全二叉树。 图2. 满二叉树和完全二叉树 基本性质 这里规定二叉树的根结点的层次为1。 性质1则二叉树的第i 层最多有2i-1个结点在此二叉树的层次从1开始i≥1 性质2深度为k的二叉树最多有2k-1个结点。(k≥1) 性质3对任何一棵二叉树T, 如果其叶结点个数为n0, 度为2的非叶结点个数为n2, 则有 n0 n2 1 性质4具有 n(n0)个结点的完全二叉树的深度为⎣log2n⎦1⎦x⎦表示不超过x的最大整数。 性质5如果对一棵有n个结点的完全二叉树的结点按层序编号从第1层到第⎣l og2n⎦ 1层每层从左到右,则对任一结点i1≤i≤n),有 (1)如果i1则结点i无双亲是二叉树的根如果i1则其双亲是结点⎣i/2⎦。 (2) 如果2in, 则结点i的左孩子结点是2i否则结点i为叶子结点无左孩子结点。 (3)如果2i1n则结点i的右孩子是结点2i1; 否则结点i为叶子结点无右孩子结点。 抽象数据类型 数据元素具有相同特性的数据元素的集合。 结构关系树中数据元素间的结构关系由二叉树的定义确定。 基本操作树的主要操作有 1创建树IntTree(T) 2销毁树DestroyTree(T) 3构造树CreatTree(Tdeinition) 4置空树ClearTree(T) 5判空树TreeEmpty(T) 6求树的深度TreeDepth(T) 7获得树根Root(T) 8获取结点Value(Tcur_ee)将树中结点cur_e存入e单元中。 9数据赋值Assign(Tcur_evalue)将结点value赋值于树T的结点cur_e中。 10获得双亲Parent(Tcur_e)返回树T中结点cur_e的双亲结点。 11获得最左孩子LeftChild(Tcur_e)返回树T中结点cur_e的最左孩子。 12获得右兄弟RightSibling(Tcur_e)返回树T中结点cur_e的右兄弟。 13插入子树InsertChild(Tpic)将树c插入到树T中p指向结点的第i个子树之前。 14删除子树DeleteChild(Tpi)删除树T中p指向结点的第i个子树。 15遍历树TraverseTree(Tvisit()) 二叉树的存储结构 二叉树是非线性结构即每个数据结点至多只有一个前驱但可以有多个后继。它可采用顺序存储结构和链式存储结构。 1顺序存储结构 二叉树的顺序存储就是用一组连续的存储单元存放二叉树中的结点。因此必须把二叉树的所有结点安排成为一个恰当的序列结点在这个序列中的相互位置能反映出结点之间的逻辑关系用编号的方法从树根起自上层至下层每层自左至右地给所有结点编号,缺点是有可能对存储空间造成极大的浪费在最坏的情况下一个深度为k且只有k个结点的右单支树需要2k-1个结点存储空间。依据二叉树的性质完全二叉树和满二叉树采用顺序存储比较合适树中结点的序号可以唯一地反映出结点之间的逻辑关系这样既能够最大可能地节省存储空间又可以利用数组元素的下标值确定结点在二叉树中的位置以及结点之间的关系。图5-5(a)是一棵完全二叉树图5-5b给出的图5-5(a)所示的完全二叉树的顺序存储结构。 (a) 一棵完全二叉树 (b) 顺序存储结构 图5-5 完全二叉树的顺序存储示意图 对于一般的二叉树如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系只有增添一些并不存在的空结点使之成为一棵完全二叉树的形式然后再用一维数组顺序存储。如图5-6给出了一棵一般二叉树改造后的完全二叉树形态和其顺序存储状态示意图。显然这种存储对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时会造成空间的大量浪费不宜用顺序存储结构。最坏的情况是右单支树如图5-7 所示一棵深度为k的右单支树只有k个结点却需分配2^k1个存储单元。 (a) 一棵二叉树 (b) 改造后的完全二叉树 (c) 改造后完全二叉树顺序存储状态 图5-6 一般二叉树及其顺序存储示意图 (a) 一棵右单支二叉树 (b) 改造后的右单支树对应的完全二叉树 (c) 单支树改造后完全二叉树的顺序存储状态 图5-7 右单支二叉树及其顺序存储示意图 结构5-1二叉树的顺序存储 #define Maxsize 100 //假设一维数组最多存放100个元素
typedef char Datatype; //假设二叉树元素的数据类型为字符
typedef struct
{ Datatype bt[Maxsize];int btnum;}Btseq; 2链式存储结构 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。其结点结构为 其中data域存放某结点的数据信息lchild与rchild分别存放指向左孩子和右孩子的指针当左孩子或右孩子不存在时相应指针域值为空用符号∧或NULL表示。利用这样的结点结构表示的二叉树的链式存储结构被称为二叉链表如图5-8所示。 (a) 一棵二叉树 (b) 二叉链表存储结构 图5-8 二叉树的二叉链表表示示意图 为了方便访问某结点的双亲还可以给链表结点增加一个双亲字段parent,用来指向其双亲结点。每个结点由四个域组成其结点结构为 这种存储结构既便于查找孩子结点又便于查找双亲结点但是相对于二叉链表存储结构而言它增加了空间开销。利用这样的结点结构表示的二叉树的链式存储结构被称为三叉链表。 图5-9给出了图5-8 (a)所示的一棵二叉树的三叉链表表示。 图5-9二叉树的三叉链表表示示意图 尽管在二叉链表中无法由结点直接找到其双亲但由于二叉链表结构灵活操作方便对于一般情况的二叉树甚至比顺序存储结构还节省空间。因此二叉链表是最常用的二叉树存储方式。 结构5-2二叉树的链式存储 #define datatype char //定义二叉树元素的数据类型为字符
typedef struct node //定义结点由数据域左右指针组成
{ Datatype data;struct node *lchild,*rchild;}Bitree; 转载于:https://www.cnblogs.com/tham/p/6827431.html
