💯 博客内容：复习数据结构
😀 作 者：陈大大陈
🚀 个人简介：一个正在努力学技术的准前端，专注基础和实战分享 ，欢迎私信！
💖 欢迎大家：这里是CSDN，我总结知识和写笔记的地方，喜欢的话请三连，有问题请私信 😘 😘 😘
目录
顺序表
单链表
双向链表
循环双向链表
栈
队列
循环队列
二叉树
顺序表
这个是动态顺序表，我觉得功能已经十分的齐全了，要是有缺少的功能大家可以私信或者在评论区告诉我，我会修改的。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLDatatype;
typedef struct SeqList
{
SLDatatype* a;
int size;//储存的有效数据个数
int capacity;//容量
}SL;
void SLInit(SL* psl)
{
assert(psl);
psl->a = (SLDatatype*)malloc(sizeof(SLDatatype)*4);
if (psl->a == NULL)
{
perror("malloc fail");
return;
}
psl->size = 0;
psl->capacity = 4;
}
void SLCheckCapacity(SL* psl)
{
assert(psl);
if (psl->size == psl->capacity)
{
SLDatatype* tmp = (SLDatatype*)realloc(psl->a,sizeof(SLDatatype) * psl->capacity * 2);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
psl->a = tmp;
psl->capacity *= 2;
}
}
void SLDestroy(SL* psl)
{
assert(psl);
free(psl->a);
psl->a = NULL;
psl->size = 0;
psl ->capacity = 0;
}
void SLPrint(SL* psl)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->a[i]);
}
printf("\n");
}
//STL命名风格
void SLPushBack(SL* psl, SLDatatype x)
{
assert(psl);
SLCheckCapacity(psl);
psl->a[psl->size++] = x;
}
void SLPushFront(SL* psl, SLDatatype x)
{
assert(psl);
SLCheckCapacity(psl);
int end = psl->size-1;
while (end >= 0)
{
psl->a[end + 1] = psl->a[end];
--end;
}
psl->a[0] = x;
psl->size++;
}
void SLPopBack(SL* psl)
{
assert(psl);
if (psl->size <= 0)
{
return;
}
psl->size--;
}
void SLPopFront(SL* psl)
{
assert(psl);
if (psl->size <= 0)
{
return;
}
for (int i = 0; i < psl->size-1; i++)
{
psl->a[i] = psl->a[i + 1];
}
psl->size--;
}
void SLInsert(SL* psl, int pos, SLDatatype x)
{
assert(psl);
SLCheckCapacity(psl);;
for (int i = pos; i < psl->size; i++)
{
psl->a[i+1] = psl->a[i];
}
psl->a[pos] = x;
psl->size++;
}
void SLErase(SL* psl, int pos)
{
assert(psl);
if (psl->size <= 0)
{
return;
}
for (int i = pos; i < psl->size-1; i++)
{
psl->a[i] = psl->a[i + 1];
}
psl->size--;
}
// 找到返回下标，没有找到返回-1
int SLFind(SL* psl, SLDatatype x)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
if (psl->a[i] == x)
{
return i;
}
}
return -1;
}
void SLModify(SL* psl, int pos, SLDatatype x)
{
assert(psl);
psl->a[pos] = x;
}
void menu()
{
printf("***************************************\n");
printf("1、尾插数据 2、尾删数据\n");
printf("3、头插数据 4、头删数据\n");
printf("5、打印数据 6.修改数据\n");
printf("-1.退出程序\n");
printf("***************************************\n");
}
int main()
{
int option = 0;
SL s;
SLInit(&s);
while (option != -1)
{
menu();
printf("请输入你的操作:>");
scanf("%d", &option);
if (option == 1)
{
/*printf("请输入要尾插的数据，以-1结束:");
int x = 0;
scanf("%d", &x);
while (x != -1)
{
SLPushBack(&s, x);
scanf("%d", &x);
}*/
int n = 0;
printf("请输入要尾插的数据个数，再依次输入要插入的数据:");
scanf("%d", &n);
int x = 0;
while (n > 0)
{
scanf("%d", &x);
SLPushBack(&s, x);
n--;
}
}
else if (option == 5)
{
SLPrint(&s);
}
else if (option == 2)
{
int n = 0;
printf("请输入要尾删的数据个数");
scanf("%d", &n);
int x = 0;
while (n > 0)
{
SLPopBack(&s);
n--;
}
}
else if (option == 3)
{
int n = 0;
printf("请输入要头插的数据个数，再依次输入要插入的数据:");
scanf("%d", &n);
int x = 0;
while (n > 0)
{
scanf("%d", &x);
SLPushFront(&s, x);
n--;
}
}
else if (option == 4)
{
int x;
int n;
printf("请输入需要头删的个数");
scanf("%d", &n);
while (n)
{
SLPopFront(&s);
n--;
}
}
else if (option == 6)
{
printf("请输入要修改的数的下标\n");
int x;
scanf("%d", &x);
printf("请输入修改后的数字\n");
int n;
scanf("%d", &n);
SLModify(&s, x, n);
}
else if (option == -1)
{
break;
}
else
{
printf("无此选项,请重新输入\n");
}
}
SLDestroy(&s);
return 0;
}单链表
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d=>", cur->data);
cur = cur->next;
}
printf("NULL");
printf("\n");
}
SLTNode* BuyLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SLPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuyLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
newnode->next = *pphead;
*pphead = newnode;
}
}
void SLPushBack(SLTNode** pphead, SLTDataType x)
{
SLTNode* cur = *pphead;
SLTNode* newnode = BuyLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
newnode = *pphead;
}
else
{
while (cur->next!= NULL)
{
cur = cur->next;
}
cur->next = newnode;
}
}
void SLPopFront(SLTNode** pphead)
{
assert(*pphead);
SLTNode* del = *pphead;
*pphead = (*pphead)->next;
free(del);
}
void SLPopBack(SLTNode** pphead)
{
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
// 找到尾结点
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
void TestSList2()
{
SLTNode* plist = NULL;
SLPushBack(&plist, 1);
SLPushBack(&plist, 2);
SLPushBack(&plist, 3);
SLPushBack(&plist, 4);
SLPopFront(&plist);
SLPushFront(&plist, 1);
SLPopBack(&plist);
SLPushBack(&plist, 4);
SLTPrint(plist);
}
int main()
{
TestSList2();
return 0;
}
双向链表
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* prev;
struct ListNode* next;
LTDataType data;
}LTNode;
LTNode* BuyLTNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
LTNode* LTInit()
{
LTNode* phead = BuyLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
void LTPrint(LTNode* phead)
{
assert(phead);
printf("GUard<==>");
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d<==>", cur->data);
cur = cur->next;
}
printf("\n");
}
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* newnode = BuyLTNode(x);
newnode->next = phead;
phead->prev = newnode;
newnode->prev = tail;
tail->next = newnode;
}
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* head = phead->next;
LTNode* newnode = BuyLTNode(x);
phead->next = newnode;
newnode->prev = phead;
newnode->next = head;
head->prev = newnode;
}
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* tail = phead->prev;
LTNode* tailprev = tail->prev;
free(tail);
phead->prev = tailprev;
tailprev->next = phead;
}
void LTPopFront(LTNode* phead)
{
LTNode* head = phead->next;
LTNode* headnext = head->next;
phead->next = headnext;
headnext->prev = phead;
free(head);
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
LTNode* cur = phead->next;
while (cur!=phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* newnode = BuyLTNode(x);
newnode->next = pos;
pos->prev = newnode;
prev->next = newnode;
newnode->prev = prev;
}
// 删除pos位置的值
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
}
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur!=phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
void TestList3()
{
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTPrint(plist);
LTNode* pos = LTFind(plist, 3);
if (pos)
{
LTInsert(pos, 30);
}
LTPopFront(plist);
LTPopBack(plist);
LTPushBack(plist, 9);
LTPrint(plist);
LTDestroy(plist);
plist = NULL;
}
int main()
{
TestList3();
return 0;
}像头插，尾删这样的功能，我们可以直接通过复用 LTInsert和LTErase来实现，这样写可以大幅度简化代码，让代码精简。代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef struct Node
{
int data;
struct Node* next;
struct Node* prev;
}Node;
Node* BuyListNode(int x);
Node* SLInit();
void LTPopFront(Node* phead);
void LTPushFront(Node* phead, int x);
void LTPopBack(Node* phead);
void LTDestroy(Node* phead);
void LTPushBack(Node* phead, int x);
void LTErase(Node* phead);
void LTInsert(Node* pos, int x);
int LTEmpty(Node* phead);
void Print(Node* phead);
Node* BuyListNode(int x)
{
Node* newnode = (Node*)malloc(sizeof(Node));
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
Node* SLInit()
{
Node* phead = BuyListNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
void LTInsert(Node* pos, int x)
{
assert(pos);
Node* newnode = BuyListNode(x);
Node* prev = pos->prev;
newnode->next = prev->next;
newnode->prev = prev;
prev->next = newnode;
pos->prev = newnode;
}
void LTPushFront(Node* phead, int x)
{
assert(phead);
LTInsert(phead->next, x);
}
void LTPushBack(Node* phead, int x)
{
assert(phead);
LTInsert(phead, x);
}
void LTPopFront(Node* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTErase(phead->prev);
}
void LTErase(Node* pos)
{
assert(pos);
Node* prev = pos->prev;
Node* next = pos->next;
prev->next = next;
next->prev = prev;
}
void LTPopBack(Node* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTErase(phead->prev);
}
void LTDestroy(Node* phead)
{
assert(phead);
Node* cur = phead->next;
while (phead != cur)
{
Node* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
int LTEmpty(Node* phead)
{
assert(phead);
return phead == phead->next;
}
void Print(Node* phead)
{
Node* cur = phead->next;
while (cur != phead)
{
Node* next = cur->next;
printf("%d<==>", cur->data);
cur = next;
}
printf("\n");
}循环双向链表
typedef int DLLData;
typedef struct DLLNode
{
DLLData data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
// 创建返回链表的头结点.
ListNode* ListCreate()
{
ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
guard->next = guard->prev = guard;
return guard;
}
// 创建一个新的结点
ListNode* BuyNewnode(LTDataType x)
{
ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
new_node->data = x;
return new_node;
}
// 双向链表销毁
void ListDestroy(ListNode* phead)
{
assert(phead);
ListNode* tmp = phead->next, *node = phead->next;
phead->next = NULL;
while (tmp)
{
node = tmp->next;
free(tmp);
tmp = node;
}
}
// 双向链表打印
void ListPrint(ListNode* phead)
{
assert(phead);
ListNode* tmp = phead->next;
printf("phead<=>");
while (tmp != phead)
{
printf("%d<=>", tmp->data);
tmp = tmp->next;
}
printf("phead\n");
}
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
assert(phead);
ListInsert(phead, x);
}
// 双向链表尾删
void ListPopBack(ListNode* phead)
{
assert(phead);
assert(!CheckVoid(phead));
ListErase(phead->prev);
}
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{
assert(phead);
ListInsert(phead->next, x);
}
// 双向链表头删
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(!CheckVoid(phead));
ListErase(phead->next);
}
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* tmp = phead->next;
while (tmp != phead)
{
if (tmp->data == x)
return tmp;
tmp = tmp->next;
}
return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
ListNode* front = pos->prev;
ListNode* new_node = BuyNewnode(x);
front->next = new_node;
new_node->next = pos;
pos->prev = new_node;
new_node->prev = front;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
}
// 检查链表为空
bool CheckVoid(ListNode* rhs)
{
assert(rhs);
return rhs->next == rhs;
}栈
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->top = 0;//这里要注意，如果设置top为-1，则为指向数据位置，如果设置top=0,则指向数据的下一个位置。
pst->capacity = 0;
}
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
void STPush(ST* pst, STDataType x)
{
if (pst->top == pst->capacity)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
void STPop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
pst->top--;
}
STDataType STTop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->a[pst->top - 1];
}
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
void TestStack1()
{
ST st;
STInit(&st);
STPush(&st, 1);
STPush(&st, 2);
printf("%d ", STTop(&st));
STPop(&st);
STPush(&st, 3);
STPush(&st, 4);
while (!STEmpty(&st))
{
printf("%d ", STTop(&st));
STPop(&st);
}
STDestroy(&st);
}
int main()
{
TestStack1();
return 0;
}队列
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->ptail = pq->phead = NULL;
pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->ptail == NULL)
{
assert(pq->phead == NULL);
pq->ptail = pq->phead = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
//头删
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
int main()
{
Queue* pq = (Queue*)malloc(sizeof(Queue));;
QueueInit(pq);
QueuePush(pq, 1);
QueuePush(pq, 2);
QueuePush(pq, 3);
QueuePush(pq, 4);
QueuePush(pq, 5);
printf("%d\n", QueueSize(pq));
printf("%d\n", QueueFront(pq));
printf("%d\n", QueueBack(pq));
return 0;
}循环队列
# include<stdio.h>
# include<malloc.h>
# define TRUE 1
# define FALSE 0
/*链队列*/
/*链队列的存储结构*/
typedef struct Node {
int data; //队列数据域
struct Node* next; //队列指针域
}LinkQueueNode;
typedef struct {
LinkQueueNode* front;//头指针
LinkQueueNode* rear;//尾指针
}LinkQueue;
/*链队列的初始化*/
int InitQueue(LinkQueue* Q) {
Q->front = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
if (Q->front != NULL) {
Q->rear = Q->front;
Q->front->next = NULL;
return TRUE;
}
else
return FALSE; //溢出
}
/*链队列的创建*/
void CreateQueue(LinkQueue* Q) {
LinkQueueNode* NewNode;
int c, flag = 1;
while (flag) {
scanf("%d", &c);
if (c != 0) {
NewNode = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
NewNode->data = c;
Q->rear->next = NewNode; //新结点插入到队尾
Q->rear = NewNode; //修改队尾指针
}
else {
flag = 0;
NewNode->next = NULL;
}
}
}
/*链队列入队*/
int EnterQueue(LinkQueue* Q, int x) {
/*将数据元素x插入到队列Q中*/
LinkQueueNode* NewNode;
NewNode = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
if (NewNode != NULL) {
NewNode->data = x;
NewNode->next = NULL;
Q->rear->next = NewNode; //新结点插入到队尾
Q->rear = NewNode; //修改队尾指针
return TRUE;
}
return FALSE;
}
/*链队列出队*/
int DeleteQueue(LinkQueue* Q, int* x) {
/*将队列Q的队头元素出队，并保存到x中*/
LinkQueueNode* p;
if (Q->front == Q->rear) //空队列
return FALSE;
p = Q->front->next; //p指向队头元素
Q->front->next = p->next; //队头元素p出队
if (Q->rear == p) //若队中只有一个元素p，则p出队后成为空队
Q->rear = Q->front;
*x = p->data;
free(p);
return TRUE;
}
/*队列输出*/
void Display(LinkQueue* Q) {
if (Q->front == Q->rear) //空队列
printf("空队列！\n");
else {
LinkQueueNode* p;
p = Q->front->next; //p指向队头元素
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
}
int main() {
int x;
LinkQueue Q;
InitQueue(&Q); //初始化队列
printf("创建队列(以0结束)："); //创建
CreateQueue(&Q);
printf("创建的队列元素为：");
Display(&Q);
EnterQueue(&Q, 5); //入队
printf("入队后队中元素为：");
Display(&Q);
DeleteQueue(&Q, &x); //出队
printf("出队元素为：%d\n", x);
printf("出队后队中元素为：");
Display(&Q);
return 0;
}
二叉树
二叉树的层序遍历需要用到队列的知识，大家看代码可能不理解是什么意思，不过没关系。
只要你画个图，一切就会豁然开朗！
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
typedef BTNode* QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
BTNode* BuyNode(BTDataType x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
int BTNodeSize(BTNode* root)
{
return root == NULL ? 0 : BTNodeSize(root->left) + BTNodeSize(root->right) + 1;
}
int BTreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}
int BTreeHeight(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int LeftHeight = BTreeHeight(root->left);
int RightHeight = BTreeHeight(root->right);
return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
}
int BTreeLevelKSize(BTNode* root, int k)
{
assert(k > 0);
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BTreeLevelKSize(root->left, k - 1) + BTreeLevelKSize(root->right, k - 1);
}
BTNode* BTFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode* ret1 = BTFind(root->left, x);
if (ret1)
{
return ret1;
}
BTNode* ret2 = BTFind(root->right, x);
if (ret2)
{
return ret2;
}
return NULL;
}
void BTreeNodeDestroy(BTNode* root)
{
if (root == NULL)
{
return;
}
BTreeNodeDestroy(root->left);
BTreeNodeDestroy(root->right);
free(root);
}
// 判断二叉树是否是完全二叉树
bool BTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
// 遇到空就跳出
if (front == NULL)
break;
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
// 检查后面的节点有没有非空
// 有非空，不是完全二叉树
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
void InsertSort(int* a, int n)
{
for (int i = 1; i < n; ++i)
{
// [0, end] 有序，插入tmp依旧有序
int end = i - 1;
int tmp = a[i];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
图的知识太多了，我在这里就不列举了。
大家期末加油。。。祝大家拿满绩。。。
文章出处登录后可见！
已经登录？立即刷新
