实现完全二叉树

1、树概念及结构

1、和我们之前学习的顺序表、链表这样的线性顺序结构不同，树是一种非线性的数据结构

2、树是递归定义的，树由根和 N 棵子树（N>=0）构成。

3、树与非树的判断：子树是不相交的；每个节点有且仅有一个父节点；一棵拥有 N 个节点的数有 N-1 条边

4、节点的度：一个节点含有的子树的个数，称为该节点的度

5、叶节点或终端节点：度为 0 的节点称为叶节点

6、父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点

7、子节点：一个节点含有子树的根节点称为该节点的子节点

8、兄弟节点：具有相同父节点的节点互称兄弟节点

9、树的度：一棵树中，最大的节点的度称为树的度

10、节点的层次：从根开始定义，根为第一层，根的子节点为第二层，以此类推

11、树的高度或深度：树中节点的最大层次

12、节点的祖先：从根到该节点所经分支上的所有节点

13、子孙：以某节点为根的子树中任一节点都称为该节点的子孙

14、森林：由m（m>0）棵互不相交的树的集合称为森林（并查集就会用到森林）

2、孩子兄弟表示法

//孩子兄弟表示法(最好的树结构)
typedef int DataType;struct TreeNode
{struct TreeNode* firstChild;//父亲指向第一个孩子struct TreeNode* pNextBrother;//剩下的孩子用孩子的兄弟指针链接起来DataType data;
};

3、二叉树

3.1、二叉树的概念

1、二叉树是度为 2 的树，即二叉树不存在度大于2的节点
2、二叉树的子树有左右之分，且次序不能颠倒，因此二叉树是有序数列
3、二叉树可以为空树
4、对任何一个非空二叉树，如果度为 0 叶节点个数为n0，度为2的分支节点个数为n2，则有n0 = n2+1 （即度为 0 的比度为 2 的节点永远多一个）
5、完全二叉树中度为 0 的节点只有 1个 或 0个

3.2、特殊的二叉树

1、满二叉树：一个二叉树，如果每层的节点数都达到最大值，则这个二叉树就是满二叉树，也就是说，如果一个二叉树的层数为K，且节点总数为2^k-1，它就是满二叉树

2、完全二叉树：完全二叉树是效率很高的数据结构，他的前K-1层都是满的，最后一层不满，但是最后一层从左往右是连续的

3、如果将完全二叉树的数据存储到数组中，会有以下三个公式来描述父节点与子节点的关系

1. leftchild = parent * 2+1 （左孩子的下标等于父节点下标乘 2 加 1）
2. rightchile = parent * 2+2（右孩子的下标等于父节点下标乘 2 加 2）
3. parent = （child-1）/ 2 （无论是左孩子还是右孩子，都能用这个公式找到父亲）

3.3、二叉树的存储

1、数组存储：只适合存储 完全二叉树 和 满二叉树

2、链式存储：适合基本所有二叉树存储，但如果存储 完全二叉树 和 满二叉树 ，效率不如数组存储

4、堆的性质

1、大根堆：树中父亲节点的数据都大于等于孩子
2、小根堆：树中父亲节点的数据都小于等于孩子

（注：上图为小根堆，下图为大根堆）

5、数组结构实现完全二叉树

1、结构体的定义

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;size_t size;size_t capacity;
}HP;

2、初始化堆

void HeapInit(HP* php)
{assert(php);//断言判空php->a = NULL;php->size = php->capacity = 0;
}

3、销毁堆

void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

4、交换函数

void Swap(HPDataType* pa, HPDataType* pb)
{HPDataType tmp = *pa;*pa = *pb;*pb = tmp;
}

5、向上调整函数

void AdjustUp(HPDataType* a,size_t child)//向上调整函数
{size_t parent = (child - 1) / 2;while (child>0)//如果child在数组中的位置大于0就继续{//if(a[child] > a[parent])//大堆if (a[child] < a[parent]) //小堆判断{Swap(&a[child], &a[parent]);//交换父节点和子节点中的数据child = parent;//交换完数据之后更新一下子节点的位置//将子节点的位置更新到原来的父节点上parent = (child - 1) / 2;}else{break;                                    }
}

6、插入数据

void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;//问号表达式判断容量，如果原容量为0就扩容到4，如果非零就扩大为原来的两倍HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);if (tmp == NULL){printf("realloc failed\n");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;++php->size;//向上调整控制保持是一个小堆AdjustUp(php->a,php->size-1);//传数组和数组的最后一个数据//也就是二叉树中刚刚加入的孩子
}
}

7、向下调整函数

void AdjustDown(HPDataType* a,size_t size,size_t root)//向下调整函数
{size_t parent = root;size_t child = parent * 2 + 1;while (child < size)//用孩子在数组中的位置比较，如果还有孩子，就继续，没有就停止{//1、选出左右孩子中小的那个if (child+1<size && a[child + 1] < a[child])//因为不确定右孩子存不存在，直接访问有越界风险//所以需要加个child+1（也就是右孩子）小于size的判断条件{++child;}if (a[child] < a[parent])//2、孩子与父亲比较，孩子小于父亲{Swap(&a[child], &a[parent]);//3、孩子与父亲交换parent = child;//把孩子的位置给父亲child = parent * 2 + 1;//在把孩子位置置成下一个孩子}else//如果孩子大于父亲{break;}}
}

8、删除堆顶数据函数

void HeapPop(HP* php)//堆的删除
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);--php->size;AdjustDown(php->a,php->size,0);//向下调整
}

9、判断是否空堆

bool HeapEmpty(HP* php)
{//判断堆是不是空堆assert(php);return php->size == 0;
}

10、计算堆大小函数

size_t HeapSize(HP* php)
{assert(php);return php->size;
}

11、取堆顶元素函数

HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}