// 以順序表實現堆typedefintHeapDatatype;typedefstructHeap{HeapDatatype *a;// 用來創建數組intcapacity;// 容量intsize;// 有效數據個數}HP;// 初始化voidHeapInit(HP *php);// 初始化數組（利用一个已存在的数组来建堆）voidHeapInitArray(HP *php,int*a,intn);// 交換voidSwap(HeapDatatype *x1,HeapDatatype *x2);// 向上調整voidAdjustUp(HeapDatatype *a,intchild);// 向下調整voidAdjustDown(HeapDatatype *a,intn,intparent);// 插入數據voidHeapPush(HP *php,HeapDatatype x);// 刪除數據voidHeapPop(HP *php);// 取堆頂數據HeapDatatype HeapTop(HP *php);// 判斷堆是否為空bool HeapEmpty(HP *php);// 堆有效數據的個數intHeapSize(HP *php);// 堆銷毀voidHeapDestroy(HP *php);

voidHeapInit(HP *php){assert(php);php->a =(HeapDatatype*)malloc(sizeof(HeapDatatype)*4);if(php->a ==NULL){perror("malloc fail");return;}php->capacity =4;php->size =0;}

voidHeapInitArray(HP *php,int*a,intn){assert(php);php->a =(HeapDatatype*)malloc(sizeof(HeapDatatype)*n);if(php->a ==NULL){perror("malloc fail");return;}php->capacity =n;php->size =n;for(inti =0;i<n;++i){php->a[i]=a[i];}// 建堆for(inti =(i-2)/2;i >=0;--i ){AdjustDown(php->a,php->size,i);}}

voidAdjustUp(HeapDatatype*a,intchild){// 找双亲节点intparent =(child-1)/2;while(child >0){if(a[child]>a[parent]){Swap(&a[child],&a[parent]);child =parent;parent =(child-1)/2;}else{break;}}}

voidAdjustDown(HeapDatatype*a,intn,intparent){intchild =2*parent +1;// 判断那个孩子比较大while(child <n){if(child +1<n &&a[child]<a[child+1]){child++;}if(a[child]>a[parent]){Swap(&a[child],&a[parent]);parent =child;child =2*parent+1;}else{break;}}}

voidHeapPush(HP *php,HeapDatatype x){assert(php);if(php->capacity ==php->size){HeapDatatype*tmp =(HeapDatatype*)realloc(php->a,sizeof(HeapDatatype)*2*php->capacity);if(tmp ==NULL){perror("realloc fail");return;}php->a =tmp;php->capacity *=2;}php->a[php->size++]=x;// 插入之后，要确保依然满足堆的特性，所以要进行向上调整AdjustUp(php->a,php->size-1);}

voidHeapPop(HP *php){assert(php);Swap(&php->a[0],&php->a[size-1]);php->size--;AdjustDown(php->a,php->size,0);}

HeapDatatype HeapTop(HP *php){assert(php);returnphp->a[0];}

bool HeapEmpty(HP *php){assert(php);returnphp->size ==0;}

intHeapSize(HP *php){assert(php);returnphp->size;}

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

三、

在树中，有一个特殊的节点称为根节点（如上图中的 body 节点）

根节点的特色是他没有前驱节点，除了根节点之外的其他节点被分成了 M 个 ( M > 0 ) 互不相交的集合T 1 、div）

叶节点或终端节点：度为零的节点

​ 以上图为例： li、根节点的左子树、根节点的右子树组成

从二叉树的逻辑结构不难发现二叉树的实现是以递归来实现的
而对二叉树的增删查改通常不是通过一般的二叉树实现的，所以在这里我们不讨论二叉树的增删查改，我们会利用二叉树的遍历来了解最一般的二叉树

4.2 二叉树的遍历

二叉树的遍历主要问题有四种

1. 前序遍历：访问顺序 – 根 - 左子树 - 右子树

2. 中序遍历：访问顺序 – 左子树 - 根 - 右子树

3. 后序遍历：访问顺序 – 左子树 - 右子树 - 根

4. 层序遍历：访问顺序 – 依序访问每一层的节点，一层访问完后再访问下一层
   
   层序遍历不仅遍历方式和其他三种不一样，实现方式也与其他三种不一样

4.3 二叉树的遍历（代码实现）

4.3.1 创建节点

因为我们不是以正规的二叉树创建方法实现，所以我们要自己创建二叉树

// 先定义结构体typedefintBTDatatype;typedefstructBinaryTreeNode{BTDatatype data;// 存储数据structBinaryTreeNode*left;// 指向左孩子structBinaryTreeNode*right;// 指向右孩子}BTNode;// 创建节点BTNode*CreateNode(BTDatatype x){BTNode*node =(BTNode*)malloc(sizeof(BTNode));if(node ==NULL){perror("malloc fail");return;}node->data =x;node->left =NULL:node->right =NULL:returnnode;}

4.3.2 创建树

创建节点并创建树

BTNode*CreateTree(){// 创建节点BTNode*node1 =CreateNode(1);BTNode*node2 =CreateNode(2);BTNode*node3 =CreateNode(3);BTNode*node4 =CreateNode(4);BTNode*node5 =CreateNode(5);BTNode*node6 =CreateNode(6);node1->left =node2;node1->right =node3;node2->left =node4;node2->right =node5;node3->right =node6;// 这里没有写错，我们让node3没有左孩子returnnode1;}

4.3.3 二叉树遍历

// 前序遍历 (我们会把空节点一起打印出来)voidPreOrder(BTNode*root){if(root ==NULL){printf("NULL ");return;}// 前序遍历的访问顺序 -- 根 - 左子树 - 右子树// 先访问根printf("%d ",root->data);// 访问左子树PreOrder(root->left);// 访问右子树PreOrder(root->right);}

// 中序遍历voidInOrder(BTNode*root){if(root ==NULL){printf("NULL ");return;}// 中序遍历的访问顺序 -- 左子树 - 根 - 右子树// 左子树InOrder(root->left);// 根printf("%d ",root->data);// 右子树InOrder(root->right);}

//后序遍历voidPostOrder(BTNode*root){if(root ==NULL){printf("NULL ");return;}// 后序遍历的访问顺序 -- 左子树 - 右子树 - 根PostOrder(root->left);PostOrder(root->right);printf("%D ",root->data);}

4.3.4 二叉树的其他接口

// 求二叉树的节点数// 方法：求得左子树和右子树的节点数后再加1（根节点）intTreeSize(BTNode*root){if(root ==NULL){return;}intlnum =TreeSize(root->left);intrnum =TreeSize(root->right);returnlnum +rnum +1;}// 求二叉树的高度intTreeHeight(BTNode*root){if(root ==NULL){return0;}intlnum =TreeHeight(root->left);intrnum =TreeHeight(root->right);returnlnum >rnum ?lnum +1:rnum +1;}

4.3.4 第k層的節點數

intTreeKLevel(BTNode*root,intk){if(root ==NULL){return0;}if(k ==1){return1;}intlnum =TreeKLevel(root->left,k-1);intrnum =TreeKLevel(root->right,k-1);returnlnum +rnum;}

4.3.5 寻找值为x的节点（如果有多个值为x的节点则返回第一个节点）

// 思路：先从根节点开始，如果根节点的值不满足我们要找的，就找左子树的节点，如果左子树没有，找右子树的节点BTNode*BinaryTreeFind(BTNode*root,BTDatatype x){if(root ==NULL){returnNULL;}if(root->data ==x){returnroot;}// 将左子树的结果保存BTNode*lret =BTNBinaryTreeFind(root->left,x);if(lret){returnlret;}// 将右子树的结果保存BTNode*rret =BinaryTreeFind(root->right,x);if(rret){returnrret;}// 整个二叉树都没有找到就返回NULLreturnNULL;}

4.3.6 层序遍历 & 判断一棵树是否是完全二叉树

层序遍历

我们前面有说过，层序遍历的实现和前、二叉树的概念

2.1 概念

二叉树的本质就是树，但二叉树有着自己的特殊性质

从图中可以看到两个二叉树的性质

1. 二叉树每个节点的度不会大于2
2. 二叉树有左右子树之分

二叉树的不同情况

注意：树可以没有节点，此时就是空树

2-2 特殊二叉树

1. 满二叉树 （ 图 a ）

   一个二叉树每一层的节点数都是该层的最大值，则这个二叉树就是满二叉树

2. 完全二叉树 （图 b ）

   一个二叉树每一层的节点依照从左至右的顺序，如果有一层的节点不是该层的最大值，则这个二叉树是完全二叉树

   注意：满二叉树是一个特殊的完全二叉树
   

2-3 二叉树的性质

1. 若根节点的层数为1，则第 i 层的最大节点数为 $2^{i-1}$

2. 若根节点的层数为1，则深度为 h 的二叉树最大节点数为 $2^h-1$

3. 对任何一棵二叉树, 如果度为 0 其叶节点个数为 $n_0$, 度为 2 的分支节点个数为 $n_2$,则有 $n_0=n_2+1$

4. 若规定根节点的层数为1，具有 n 个节点的满二叉树的深度，$h=lo{g}_2(n+1)$

   注意这里的 log 是以2为底

5. 对于具有 n 个节点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对

   于序号为 i。中、div

   兄弟节点：有相同双亲节点的节点

   ​ 以上图为例：ul的兄弟节点是p和div；li的兄弟节点是li和img

   树的度：最大节点的的度就是树的度

   ​ 以上图为例：最大节点的度是3 （body节点）所以树的度为3

   节点的层次：以根节点开始，根为第一层，根节点的子节点为第二层，以此类推

   树的高度：就是节点的最大的层次

   ​ 以上图为例：最大的节点层次是3，所以树的高度是3

   堂兄弟节点：双亲在同一层的节点互为堂兄弟

   ​ 以上图为例 li 和 img 是堂兄弟节点

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

   ​ 以上图为例：body是所有节点的祖先

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

   ​ 以上图为例：除了body节点以外的节点都是body节点的子孙

   森林：由 m（m>0）棵互不相交的树的集合称为森林

二、

1.2 与树相关的专有名词

节点的度：一个节点的子树个数

​ 以上图为例：body 节点的度为 3 （ul、T2​、img 都是叶节点

分支节点或非终端节点：度不为零的节点

​ 以上图为例：body、div 都是分支节点

双亲节点或父节点：如果一个节点有子节点，则这个节点就是这个子节点的双亲节点

​ 以上图为例：body节点是 ul、的节点有

（1）若 i > 0，i 位置节点的双亲序号：$\frac{i-1}{2}$； i=0，i 为根节点编号，无双亲节点

（2）若 2i+1< n，左孩子序号：2i+1，2i+1 >= n 则无左孩子

（3）若 2i+2 <n，右孩子序号：2i+2，2i+2 >= n 则无右孩子

2-4 二叉树的存储结构

一般来所，二叉树的存储结构可以分成两种

1. 顺序存储结构

   顺序存储结构就是利用数组来实现，通常只有完全二叉树才会使用数组来实现，因为如果不是完全二叉树会有空间浪费的问题，在实际当中只有堆会使用到二叉树的顺序存储结构

   虽然物理结构上是数组，但是逻辑结构上还是一棵二叉树
   

2. 链式存储结构

   链式存储结构就是以链表来表示一棵二叉树，在目前主要以二叉链表来表示，每个节点由数据域（data）、p、

   一、

   上一篇：rabbitmq异常处理问题集

   下一篇：OpenCV常用的函数和操作