⼆叉树概念及结构
1. 树概念及结构
1.1树概念
树是⼀种⾮线性的数据结构，它是由n（n>=0）个有限结点组成⼀个具有层次关系的集合。把它叫做树是因
为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。
根结点：根节点没有前驱结点。
除根节点外，其余结点被分成是⼀棵结构与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱，可以有0个或多个后继。
因此，树是递归定义的。
节点的度：⼀个节点含有的⼦树的个数称为该节点的度； 如上图：A的为2
叶节点：度为0的节点称为叶节点； 如上图：G、H、I节点为叶节点
⾮终端节点或分⽀节点：度不为0的节点； 如上图：B、D、C、E、F节点为分⽀节点
双亲节点或⽗节点：若⼀个节点含有⼦节点，则这个节点称为其⼦节点的⽗节点； 如上图：A是B的⽗节点
孩⼦节点或⼦节点：⼀个节点含有的⼦树的根节点称为该节点的⼦节点； 如上图：B是A的孩⼦节点
兄弟节点：具有相同⽗节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
兄弟节点：具有相同⽗节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
树的度：⼀棵树中，最⼤的节点的度称为树的度； 如上图：树的度为2
节点的层次：从根开始定义起，根为第1层，根的⼦节点为第2层，以此类推；
树的⾼度或深度：树中节点的最⼤层次； 如上图：树的⾼度为4
堂兄弟节点：双亲在同⼀层的节点互为堂兄弟；如上图：H、I互为兄弟节点
节点的祖先：从根到该节点所经分⽀上的所有节点；如上图：A是所有节点的祖先
⼦孙：以某节点为根的⼦树中任⼀节点都称为该节点的⼦孙。如上图：所有节点都是A的⼦孙
森林：由m棵互不相交的树的集合称为森林；
1.2树的表⽰
树结构相对线性表就⽐较复杂了，要存储表⽰起来就⽐较⿇烦了，实际中树有很多种表⽰⽅式，如：双亲表二叉树定义
⽰法，孩⼦表⽰法、孩⼦兄弟表⽰法等等。我们这⾥就简单的了解其中最常⽤的孩⼦兄弟表⽰法。
typedef int DataType;
struct Node
{
struct Node* firstChild1;
struct Node* pNextBrother;
DataType data;
};
2. ⼆叉树概念及结构
2.1概念
⼀棵⼆叉树是结点的⼀个有限集合，该集合或者为空，或者是由⼀个根节点加上两棵别称为左⼦树和右⼦树的⼆叉树组成。
⼆叉树的特点：
每个结点最多有两棵⼦树，即⼆叉树不存在度⼤于2的结点。
⼆叉树的⼦树有左右之分，其⼦树的次序不能颠倒。
2.2数据结构中的⼆叉树
2.3特殊的⼆叉树
满⼆叉树：⼀个⼆叉树，如果每⼀个层的结点数都达到最⼤值，则这个⼆叉树就是满⼆叉树。也就是说，如果⼀个⼆叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满⼆叉树。
完全⼆叉树：完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为K的，有n个结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从1⾄n的结点⼀⼀对应时称之为完全⼆叉树。 要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。
2.4⼆叉树的存储结构
⼆叉树⼀般可以使⽤两种存储结构，⼀种顺序结构，⼀种链式结构。
2.4.1顺序存储
顺序结构存储就是使⽤数组来存储，⼀般使⽤数组只适合表⽰完全⼆叉树，因为不是完全⼆叉树会有空间的浪费。⽽现实中使⽤中只有堆才会使⽤数组来存储。⼆叉树顺序存储在物理上是⼀个数组，在逻辑上是⼀颗⼆叉树。
⼆叉树的链式存储结构是指，⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。 通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址 。链式结构⼜分为⼆叉链和三叉链，当前我们学习中⼀般都是⼆叉链，后⾯课程学到⾼阶数据结构如红⿊树等会⽤到三叉链。
// ⼆叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向当前节点左孩⼦
struct BinTreeNode* _pRight; // 指向当前节点右孩⼦
BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pParent; // 指向当前节点的双亲
struct BinTreeNode* _pLeft; // 指向当前节点左孩⼦
struct BinTreeNode* _pRight; // 指向当前节点右孩⼦
BTDataType _data; // 当前节点值域
}；
若规定根节点的层数为1，则⼀棵⾮空⼆叉树的第i层上最多有2^(i-1) 个结点.
若规定根节点的层数为1，则深度为h的⼆叉树的最⼤结点数是2^h- 1.
对任何⼀棵⼆叉树, 如果度为0其叶结点个数为 n0, 度为2的分⽀结点个数为 n2，则有n0＝n2＋1
若规定根节点的层数为1，具有n个结点的满⼆叉树的深度，h=Log2(n+1). (ps：Log2(n+1)是log以2为
底，n+1为对数)
对于具有n个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的数组顺序对所有节点从0开始编号，则对
于序号为i的结点有：
1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，⽆双亲节点
2. 若2i+1<n，左孩⼦序号：2i+1，2i+1>=n否则⽆左孩⼦
3. 若2i+2<n，右孩⼦序号：2i+2，2i+2>=n否则⽆右孩⼦
4. ⼆叉树顺序结构及概念
3.1⼆叉树的顺序结构
普通的⼆叉树是不适合⽤数组来存储的，因为可能会存在⼤量的空间浪费。⽽完全⼆叉树更适合使⽤顺序结构存储。现实中我们通常把堆(⼀种⼆叉树)使⽤顺序结构的数组来存储，需要注意的是这⾥的堆和操作系统虚拟进程地址空间中的堆是两回事，⼀个是数据结构，⼀个是操作系统中管理内存的⼀块区域分段。
3.2堆的概念及结构
如果有⼀个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全⼆叉树的顺序存储⽅式存储在⼀个⼀维数组中，并满⾜：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为⼩堆(或⼤堆)。将根节点最⼤的堆叫做最⼤堆或⼤根堆，根节点最⼩的堆叫做最⼩堆或⼩根堆。
堆的性质：
堆中某个节点的值总是不⼤于或不⼩于其⽗节点的值；
堆总是⼀棵完全⼆叉树。
3.3堆的实现
typedef int HPDataType;
typedef struct Heap
{
HPDataType* _a;
int _size;
int _capacity;
}Heap;
void swap(int *a, int *b);
void AdjustDown(int *a, int parent, int n);
void AdjustUp(int *a, int child, int n);

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。