链式二叉树的创建销毁及其应用
因为层序遍历和判断是否为完全二叉树需要队列实现,所以要引入队列
Queue.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QueueNode; typedef struct Queue { QueueNode* head; QueueNode* tail; // size_t _size; }Queue; //void QueueInit(QueueNode** pphead, QueueNode** pptail); 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);
Queue.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; } void QueueDestroy(Queue* pq) { assert(pq); QueueNode* cur = pq->head; while (cur != NULL) { QueueNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } void QueuePush(Queue* pq, QDataType x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); newnode->data = x; newnode->next = NULL; if (pq->head == NULL) { pq->head = newnode; pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->head == pq->tail) { free(pq->head); pq->head = pq->tail = NULL; } else { QueueNode* next = pq->head->next; free(pq->head); pq->head = next; } } QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } int QueueSize(Queue* pq) { assert(pq); int n = 0; QueueNode* cur = pq->head; while (cur) { cur = cur->next; n++; } return n; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; }
接下来就是二叉树的实现
BinaryTree.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include "Queue.h" typedef char BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树 BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi); // 二叉树销毁 void BinaryTreeDestory(BTNode** root); // 二叉树节点个数 int BinaryTreeSize(BTNode* root); // 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root); // 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k); // 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root); // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root); // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root); // 层序遍历 void BinaryTreeLevelOrder(BTNode* root); // 判断二叉树是否是完全二叉树 int BinaryTreeComplete(BTNode* root);
BinaryTree.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "BinaryTree.h" #include "Queue.h" // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树 BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi) { if (a[*pi] == '#') { (*pi)++; return NULL; } BTNode* root = (BTNode*)malloc(sizeof(BTNode)); root->data = a[*pi]; (*pi)++; root->left = BinaryTreeCreate(a, n, pi); root->right = BinaryTreeCreate(a, n, pi); return root; } // 二叉树销毁 void BinaryTreeDestory(BTNode** root) { if (*root) { BinaryTreeDestory(&((*root)->left)); BinaryTreeDestory(&((*root)->right)); free(*root); } *root = NULL; } // 二叉树节点个数 int BinaryTreeSize(BTNode* root) { if (root == NULL) { return 0; } return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1; } // 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->left == NULL && root->right == NULL) { return 1; } return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right); } // 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k) { if (root == NULL) { return NULL; } if (k == 1) { return 1; } return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1); } // 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) { return NULL; } if (root->data == x) { return root; } BTNode* leftRet = BinaryTreeFind(root->left, x); if (leftRet) { return leftRet; } BTNode* rightRet = BinaryTreeFind(root->right, x); if (rightRet) { return rightRet; } return NULL; } // 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) { return NULL; } printf("%c ", root->data); BinaryTreePrevOrder(root->left); BinaryTreePrevOrder(root->right); } // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) { return NULL; } BinaryTreePrevOrder(root->left); printf("%c ", root->data); BinaryTreePrevOrder(root->right); } // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) { if (root == NULL) { return NULL; } BinaryTreePrevOrder(root->left); BinaryTreePrevOrder(root->right); printf("%c ", root->data); } // 层序遍历 void BinaryTreeLevelOrder(BTNode* root) { if (root == NULL) { return; } Queue q; QueueInit(&q); QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); printf("%c ", front->data); if (front->left) { QueuePush(&q, front->left); } if (front->right) { QueuePush(&q, front->right); } if (front == NULL && !QueueEmpty(&q)) { return false; } } printf("\n"); QueueDestroy(&q); } // 判断二叉树是否是完全二叉树 int BinaryTreeComplete(BTNode* root) { if (root == NULL) { return; } Queue q; QueueInit(&q); QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); printf("%c ", front->data); if (front) { QueuePush(&q, front->left); QueuePush(&q, front->right); } else { break; } } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); printf("%c ", front->data); if (front) { QueueDestroy(&q); return false; } } QueueDestroy(&q); return true; }
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "BinaryTree.h" int main() { char str[] = "ABD##E#H##CF##G##"; int len = strlen(str); int i = 0; BTNode* root = BinaryTreeCreate(str, len, &i); BinaryTreePrevOrder( root); BinaryTreeDestory(&root); return 0; }