中小企业服务中心网站建设,linux和WordPress的关系,网站怎么做黑链接,wp怎么做双语网站【数据结构入门指南】二叉树 一、二叉树的概念二、现实中的二叉树三、特殊的二叉树四、二叉树的性质五、二叉树的存储结构5.1 顺序结构5.2 链式结构 一、二叉树的概念 二叉树是一棵特殊的树。一棵二叉树是结点的一个有限集合#xff0c;该节点#xff1a; ①#xff1a;或者… 【数据结构入门指南】二叉树 一、二叉树的概念二、现实中的二叉树三、特殊的二叉树四、二叉树的性质五、二叉树的存储结构5.1 顺序结构5.2 链式结构 一、二叉树的概念 二叉树是一棵特殊的树。一棵二叉树是结点的一个有限集合该节点 ①或者为空。 ② 由一个根节点加上两棵别称为左子树和右子树的二叉树组成。 从上图可以看出
二叉树不存在度大于2的结点.二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树。
Tips:对于任意的二叉树都是由以下几种情况复合而成的 二、现实中的二叉树 三、特殊的二叉树 ① 满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是2^k -1,则它就是满二叉树。 ②完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 四、二叉树的性质
① 若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2(i-1)个结点。 ② 若规定根节点的层数为1则深度为h的二叉树的最大结点数是2h-1。 ③ 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2,则n0 n2 1。 ④ 若规定根节点的层数为1具有n个结点的满二叉树的深度,hlog2(n1)。 ⑤对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有
若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点。若2i1n左孩子序号2i12i1n否则无左孩子。若2i2n右孩子序号2i22i2n否则无右孩子。 五、二叉树的存储结构
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。
5.1 顺序结构 顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费,/font.。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 5.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; // 当前节点值域
}-【数据结构入门指南】二叉树顺序结构: 堆及实现全程配图非常经典
