# 【C语言 数据结构】堆与二叉树（下）

### 堆排序

``````#include<stdio.h>
void downAdjust(int* pa, int parent, int n)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && pa[child] > pa[child + 1])
{
child++;
}
if (pa[parent] > pa[child])
{
swap(&pa[parent], &pa[child]);
}
else
{
break;
}
parent = child;
child = parent * 2 + 1;
}
}
int main()
{
int arr[] = { 1,3,2,5,7,4,7,4,2,5,6,8};
int n = sizeof(arr) / sizeof(arr[0]);
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
}
for (int i = n; i > 0; )
{
swap(&arr[0], &arr[i - 1]);
}
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}

return 0;
}``````

### topK算法

``````void downAdjust(int* pa, int parent, int n)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && pa[child] > pa[child + 1])
{
child++;
}
if (pa[parent] > pa[child])
{
swap(&pa[parent], &pa[child]);
}
else
{
break;
}
parent = child;
child = parent * 2 + 1;
}
}
#include<stdio.h>
int main()
{
int arr[] = { 1,6,10,3,5,8,46,23,6,25,3,40 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 0;
scanf("%d", &k);
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
}
for (int i = k; i < n; i++)
{
if (arr[i] > arr[0])
{
swap(&arr[i], &arr[0]);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", arr[i]);
}
return 0;
}``````

## 五. 二叉树的实现

### 1. 链接结构搭建二叉树

``````typedef int TLType;
typedef struct TreeList
{
TLType val;
struct TreeList* left;
struct TreeList* right;
}TL;
TL *creatnode(TLType x)
{
TL*pa = (TL*)malloc(sizeof(TL));
if (pa == NULL)
{
perror("malloc");
return;
}
TL* newnode = pa;
newnode->left = newnode->right = NULL;
newnode->val = x;
return newnode;
}
TL* CreatTree()
{
TL* tree1 = creatnode(1);
TL *tree2 = creatnode(2);
TL* tree3 = creatnode(3);
TL* tree4 = creatnode(3);
tree1->left = tree2;
tree1->right = tree3;
tree2->left = tree4;
return tree1;
}
#include<stdio.h>
int main()
{
TL* p = NULL;
p = CreatTree();
}``````

### 2. 二叉树的遍历

#### a. 前序遍历：（根，左子树，右子树）

val1 val2 val4 N N val5 N N val3 val6 N N val7 N N

``````#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{
TLType val;
struct TreeList* left;
struct TreeList* right;
}TL;
TL *creatnode(TLType x)
{
TL*pa = (TL*)malloc(sizeof(TL));
if (pa == NULL)
{
perror("malloc");
return;
}
TL* newnode = pa;
newnode->left = newnode->right = NULL;
newnode->val = x;
return newnode;
}
TL* CreatTree()
{
TL* tree1 = creatnode(1);
TL *tree2 = creatnode(2);
TL* tree3 = creatnode(3);
TL* tree4 = creatnode(4);
TL* tree5 = creatnode(5);
TL* tree6 = creatnode(6);
TL* tree7 = creatnode(7);
tree1->left = tree2;
tree1->right = tree3;
tree2->left = tree4;
tree2->right = tree5;
tree3->left = tree6;
tree3->right = tree7;
return tree1;
}
#include<stdio.h>
void PrevOrder(TL *root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%d ", root->val);
PrevOrder(root->left);
PrevOrder(root->right);
}
int main()
{
TL* p = NULL;
p = CreatTree();
PrevOrder(p);
}``````

#### b. 中序遍历：（左子树，根，右子树）

N val4 N val2 N val5 N val1 N val6 N val3 N val7 N

代码实现

``````#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{
TLType val;
struct TreeList* left;
struct TreeList* right;
}TL;
TL *creatnode(TLType x)
{
TL*pa = (TL*)malloc(sizeof(TL));
if (pa == NULL)
{
perror("malloc");
return;
}
TL* newnode = pa;
newnode->left = newnode->right = NULL;
newnode->val = x;
return newnode;
}
TL* CreatTree()
{
TL* tree1 = creatnode(1);
TL *tree2 = creatnode(2);
TL* tree3 = creatnode(3);
TL* tree4 = creatnode(4);
TL* tree5 = creatnode(5);
TL* tree6 = creatnode(6);
TL* tree7 = creatnode(7);
tree1->left = tree2;
tree1->right = tree3;
tree2->left = tree4;
tree2->right = tree5;
tree3->left = tree6;
tree3->right = tree7;
return tree1;
}
#include<stdio.h>
void InOder(TL* root)
{
if (root == NULL)
{
printf("N ");
return;
}
InOder(root->left);
printf("%d ", root->val);
InOder(root->right);
}
int main()
{
TL* p = NULL;
p = CreatTree();
InOder(p);
}``````

#### c. 后序遍历：（左子树，右子树，根）

N N val4 N N val5 val2 N N val6 N N val7 val3 val1

``````#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{
TLType val;
struct TreeList* left;
struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{
TL* pa = (TL*)malloc(sizeof(TL));
if (pa == NULL)
{
perror("malloc");
return;
}
TL* newnode = pa;
newnode->left = newnode->right = NULL;
newnode->val = x;
return newnode;
}
TL* CreatTree()
{
TL* tree1 = creatnode(1);
TL* tree2 = creatnode(2);
TL* tree3 = creatnode(3);
TL* tree4 = creatnode(4);
TL* tree5 = creatnode(5);
TL* tree6 = creatnode(6);
TL* tree7 = creatnode(7);
tree1->left = tree2;
tree1->right = tree3;
tree2->left = tree4;
tree2->right = tree5;
tree3->left = tree6;
tree3->right = tree7;
return tree1;
}
void PostOder(TL* root)
{
if (root == NULL)
{
printf("N ");
return;
}
PostOder(root->left);
PostOder(root->right);
printf("%d ", root->val);
}
int main()
{
TL* p = NULL;
p = CreatTree();
PostOder(p);
}``````

#### d. 层序遍历

``````#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int TLType;
typedef struct TreeList
{
TLType val;
struct TreeList* left;
struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{
TL* pa = (TL*)malloc(sizeof(TL));
if (pa == NULL)
{
perror("malloc");
return;
}
TL* newnode = pa;
newnode->left = newnode->right = NULL;
newnode->val = x;
return newnode;
}
TL* CreatTree()
{
TL* tree1 = creatnode(1);
TL* tree2 = creatnode(2);
TL* tree3 = creatnode(3);
TL* tree4 = creatnode(4);
TL* tree5 = creatnode(5);
TL* tree6 = creatnode(6);
TL* tree7 = creatnode(7);
tree1->left = tree2;
tree1->right = tree3;
tree2->left = tree4;
tree2->right = tree5;
tree3->left = tree6;
tree3->right = tree7;
return tree1;
}
typedef struct QueueNode
{
struct QueueNode* next;
TL* data;
}QNode;

typedef struct Queue
{
QNode* tail;
int size;
}Que;

void QueueInit(Que* pq)
{
assert(pq);

pq->size = 0;
}

void QueueDestroy(Que* pq)
{
assert(pq);

while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}

pq->size = 0;
}

void QueuePush(Que* pq, TL* x)
{
assert(pq);

QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}

newnode->data = x;
newnode->next = NULL;

if (pq->tail == NULL)
{
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}

pq->size++;
}

bool QueueEmpty(Que* pq)
{
assert(pq);

}
void QueuePop(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));

{
}
else
{
}

pq->size--;
}

TL* QueueFront(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));

}

int QueueSize(Que* pq)
{
assert(pq);

return pq->size;
}
void leverOrder(TL* root, Que* pq)
{
QueuePush(pq, root);
while (!QueueEmpty(pq))
{
TL* pa = QueueFront(pq);
printf("%d ", pa->val);
QueuePop(pq);
if (pa->left != NULL)
{
QueuePush(pq, pa->left);
}
if (pa->right != NULL)
{
QueuePush(pq, pa->right);
}
}

}
int main()
{
TL* p = NULL;
p = CreatTree();
Que q;
QueueInit(&q);
leverOrder(p, &q);
return 0;
}``````

### 3. 简单二叉树经典问题求解

#### a. 求二叉树的节点个数

``````#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{
TLType val;
struct TreeList* left;
struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{
TL* pa = (TL*)malloc(sizeof(TL));
if (pa == NULL)
{
perror("malloc");
return;
}
TL* newnode = pa;
newnode->left = newnode->right = NULL;
newnode->val = x;
return newnode;
}
TL* CreatTree()
{
TL* tree1 = creatnode(1);
TL* tree2 = creatnode(2);
TL* tree3 = creatnode(3);
TL* tree4 = creatnode(4);
TL* tree5 = creatnode(5);
TL* tree6 = creatnode(6);
TL* tree7 = creatnode(7);
tree1->left = tree2;
tree1->right = tree3;
tree2->left = tree4;
tree2->right = tree5;
tree3->left = tree6;
tree3->right = tree7;
return tree1;
}
int TreeSize(TL* root)
{
if (root == NULL)
{
return 0;
}
return 1 + TreeSize(root->left) + TreeSize(root->right);
}
int main()
{
TL* p = NULL;
p = CreatTree();
int size = TreeSize(p);
printf("%d ", size);
return 0;
}``````

#### b. 求树的高度

``````#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{
TLType val;
struct TreeList* left;
struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{
TL* pa = (TL*)malloc(sizeof(TL));
if (pa == NULL)
{
perror("malloc");
return;
}
TL* newnode = pa;
newnode->left = newnode->right = NULL;
newnode->val = x;
return newnode;
}
TL* CreatTree()
{
TL* tree1 = creatnode(1);
TL* tree2 = creatnode(2);
TL* tree3 = creatnode(3);
TL* tree4 = creatnode(4);
TL* tree5 = creatnode(5);
TL* tree6 = creatnode(6);
TL* tree7 = creatnode(7);
TL* tree8 = creatnode(8);
tree1->left = tree2;
tree1->right = tree3;
tree2->left = tree4;
tree2->right = tree5;
tree3->left = tree6;
tree3->right = tree7;
tree4->left = tree8;
return tree1;
}
int TreeHigh(TL* root)
{
if (root == NULL)
{
return 0;
}
int Left = 1 + TreeHigh(root->left);
int Right = 1 +  TreeHigh(root->right) ;
return Left > Right ? Left : Right;
}
int main()
{
TL* p = NULL;
p = CreatTree();
int high = TreeHigh(p);
printf("%d ", high);
return 0;
}``````

#### c. 求根节点的个数

``````#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{
TLType val;
struct TreeList* left;
struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{
TL* pa = (TL*)malloc(sizeof(TL));
if (pa == NULL)
{
perror("malloc");
return;
}
TL* newnode = pa;
newnode->left = newnode->right = NULL;
newnode->val = x;
return newnode;
}
TL* CreatTree()
{
TL* tree1 = creatnode(1);
TL* tree2 = creatnode(2);
TL* tree3 = creatnode(3);
TL* tree4 = creatnode(4);
TL* tree5 = creatnode(5);
TL* tree6 = creatnode(6);
TL* tree7 = creatnode(7);
TL* tree8 = creatnode(8);
tree1->left = tree2;
tree1->right = tree3;
tree2->left = tree4;
tree2->right = tree5;
tree3->left = tree6;
tree3->right = tree7;
tree4->left = tree8;
return tree1;
}
int RootSize(TL* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return RootSize(root->left) + RootSize(root->right);
}
int main()
{
TL* p = NULL;
p = CreatTree();
int root = RootSize(p);
printf("%d ", root);
return 0;
}``````

#### d. 求倒数第k排节点的个数

``````#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{
TLType val;
struct TreeList* left;
struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{
TL* pa = (TL*)malloc(sizeof(TL));
if (pa == NULL)
{
perror("malloc");
return;
}
TL* newnode = pa;
newnode->left = newnode->right = NULL;
newnode->val = x;
return newnode;
}
TL* CreatTree()
{
TL* tree1 = creatnode(1);
TL* tree2 = creatnode(2);
TL* tree3 = creatnode(3);
TL* tree4 = creatnode(4);
TL* tree5 = creatnode(5);
TL* tree6 = creatnode(6);
TL* tree7 = creatnode(7);
TL* tree8 = creatnode(8);
tree1->left = tree2;
tree1->right = tree3;
tree2->left = tree4;
tree2->right = tree5;
tree3->left = tree6;
tree3->right = tree7;
tree4->left = tree8;
return tree1;
}

int TreeHigh(TL* root)
{
if (root == NULL)
{
return 0;
}
int Left = 1 + TreeHigh(root->left);
int Right = 1 +  TreeHigh(root->right) ;
return Left > Right ? Left : Right;
}
int RootKsize(TL* root,int n,int k)
{
if (root == NULL)
{
return 0;
}
if (n == k)
{
return 1;
}
return RootKsize(root->left, n - 1, k) + RootKsize(root->right, n - 1, k);
}
int main()
{
int k = 0;
scanf("%d", &k);
TL* p = NULL;
p = CreatTree();
int high = TreeHigh(p);
int rootk = RootKsize(p, high, k);
printf("%d ", rootk);
return 0;
}``````

#### e. 判断是否是相同的树

``````#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int TLType;
typedef struct TreeList
{
TLType val;
struct TreeList* left;
struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{
TL* pa = (TL*)malloc(sizeof(TL));
if (pa == NULL)
{
perror("malloc");
return;
}
TL* newnode = pa;
newnode->left = newnode->right = NULL;
newnode->val = x;
return newnode;
}
TL* CreatTree1()
{
TL* tree1 = creatnode(1);
TL* tree2 = creatnode(2);
TL* tree3 = creatnode(3);
TL* tree4 = creatnode(4);
TL* tree5 = creatnode(5);
TL* tree6 = creatnode(6);
TL* tree7 = creatnode(7);
TL* tree8 = creatnode(8);
tree1->left = tree2;
tree1->right = tree3;
tree2->left = tree4;
tree2->right = tree5;
tree3->left = tree6;
tree3->right = tree7;
tree4->left = tree8;
return tree1;
}
TL* CreatTree2()
{
TL* tree1 = creatnode(1);
TL* tree2 = creatnode(2);
TL* tree3 = creatnode(3);
TL* tree4 = creatnode(4);
TL* tree5 = creatnode(5);
TL* tree6 = creatnode(6);
TL* tree7 = creatnode(7);
tree1->left = tree2;
tree1->right = tree3;
tree2->left = tree4;
tree2->right = tree5;
tree3->left = tree6;
tree3->right = tree7;
return tree1;
}
bool IsSameTree(TL* root1,TL* root2)
{
if (root1 == NULL && root2 == NULL)
{
return true;
}
if (root1 == NULL || root2 == NULL)
{
return false;
}
if (root1->val != root2->val)
{
return false;
}
return IsSameTree(root1->left, root2->left) && IsSameTree(root1->right, root2->right);
}
int main()
{
TL* p = NULL;
p = CreatTree1();
TL* q = CreatTree2();
printf("%d ", IsSameTree(p, q));
return 0;
}``````

#### f. 找到某个值，返回节点的地址

``````#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int TLType;
typedef struct TreeList
{
TLType val;
struct TreeList* left;
struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{
TL* pa = (TL*)malloc(sizeof(TL));
if (pa == NULL)
{
perror("malloc");
return;
}
TL* newnode = pa;
newnode->left = newnode->right = NULL;
newnode->val = x;
return newnode;
}
TL* CreatTree()
{
TL* tree1 = creatnode(1);
TL* tree2 = creatnode(2);
TL* tree3 = creatnode(2);
TL* tree4 = creatnode(4);
TL* tree5 = creatnode(5);
TL* tree6 = creatnode(6);
TL* tree7 = creatnode(7);
TL* tree8 = creatnode(8);
tree1->left = tree2;
tree1->right = tree3;
tree2->left = tree4;
tree2->right = tree5;
tree3->left = tree6;
tree3->right = tree7;
tree4->left = tree8;
return tree1;
}
TL* FindRoot(TL* root,int m)
{
if (root == NULL)
{
return NULL;
}
if (root->val == m)
{
return root;
}
TL* Left = FindRoot(root->left, m);
TL* Right = FindRoot(root->right, m);
if (Left == NULL && Right == NULL)
{
return NULL;
}
if (Left == NULL && Right != NULL)
{
return Right;
}
else
{
return Left;
}

}
int main()
{
TL* p = NULL;
p = CreatTree();
int m = 0;
scanf("%d", &m);
TL *root = FindRoot(p,m);
if (root == NULL)
{
printf("找不到n");
}
else
{
printf("%d ", root->val);
}
return 0;
}``````

THE END