一、二叉树我们需要实现的功能
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);
二、以下为具体功能的实现
1.创建新节点
该步骤创建一个新节点
typedef char BTDataType; typedef struct BinaryTree { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode;
2.构建二叉树
通过数组构建二叉树
1. // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树 2. BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
前序遍历：先遍历根，再遍历左子树和右子树
注:该步骤：当数组内容为#或者数组已经访问完，都应该返回NULL,当该数组中的内容不为‘#并且数组并未执行完毕，则开辟一块新的空间，类型为BTNode，此时根节点的数据为数组中的内容，并对其进行后置访问，根节点的左节点和根节点的右节点，分别进行遍历，最后我们返回根节点
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi) { if (a[*pi] == NULL || (*pi) >= n) { a[(*pi)++]; return NULL; } BTNode* root = (BTNode*)malloc(sizeof(BTNode)); if (root == NULL) { perror("fail:malloc"); return; } root->data = a[(*pi)++]; root->left = BinaryTreeCreate(a,n,pi); root->right = BinaryTreeCreate(a,n,pi); return root; }
3、二叉树的销毁
注：当根节点为空时，我们对其直接进行放回，如果根节点不为空，我们对其进行遍历，访问到最后一个节点，我们对其返回释放
void BinaryTreeDestory(BTNode* root) { if (root == NULL) return; BinaryTreeDestory(root->left); BinaryTreeDestory(root->right); //printf("%p %c\n", root, root->data); free(root); }
4.二叉树节点个数和二叉树叶子节点的个数
注：二叉树节点个数，如果根节点为空，则返回0，若根节点不为空我们，对其左右子树进行遍历，并且其往回进行遍历时，我们进行+1操作，最后的返回值即为二叉树节点的个数
// 二叉树节点个数 int BinaryTreeSize(BTNode* root) { if (root == NULL) { return 0; } return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right); } // 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->left == NULL&&root->right) { return 1; } }
5.前中后序遍历：二叉树的遍历
在之前我已经写过相关内容的博客，可以点击上面链接直接进行查看
// 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) return; printf("%c ", root->data); BinaryTreePrevOrder(root->left); BinaryTreePrevOrder(root->right); } // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) return; BinaryTreePrevOrder(root->left); printf("%c ", root->data); BinaryTreePrevOrder(root->right); } // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) { if (root == NULL) return; BinaryTreePrevOrder(root->left); BinaryTreePrevOrder(root->right); printf("%c ", root->data); }
6. 二叉树查找值为x的节点
注：查找第k层，我们将我们的问题化为小问题，也就是我们第一层的结点需要往下找k-1层，第二层的结点需要往下找k-2层，以此类推，只有当我们的k为1的时候返回的就是我们需要找的k层的结点的个数的总和
// 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) return NULL; if (root->data == x) return root; BTNode* ret1 = BinaryTreeFind(root->left, x); if (ret1) return ret1; BTNode* ret2 = BinaryTreeFind(root->right, x); if (ret2) return ret2; return NULL; }
7.层序遍历
注：此时我们采用非递归的方式进行实现，主要用到了队列， 我们清楚队列，是先进先出的方式，我们将数据存储进队列当中，再对其进行取出
Queue.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> //前置声明 struct BinaryTreeNode; typedef struct BinaryTreeNode* QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct { QNode* head; QNode* tail; }Queue; //初始化 void QueueInit(Queue* pq); //销毁 void QueueDestroy(Queue* pq); //放数据 void QueuePush(Queue* pq, QDataType x); //删除 void QueuePop(Queue* pq); //长度 int QueueSize(Queue* pq); //取头 QDataType QueueFront(Queue* pq); //取尾 QDataType QueueBack(Queue* pq); //判断空 bool QueueEmpty(Queue* pq);
Queue.c
#include"queue.h" //初始化 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } //销毁 void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } //放数据 void QueuePush(Queue* pq, QDataType x) { assert(pq); //开辟空间 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } //添加数据 newnode->data = x; newnode->next = NULL; //链接 if (pq->tail == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } } //判断空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } //删除 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* 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); QNode* cur = pq->head; int count = 0; while (cur) { ++count; cur = cur->next; } return count; }
层序遍历的实现
注：先创建一个队列，对其进行初始化，如果根节点不为空，我们将其放入新创建的队列当中，我们将队列进行循环处理，取出队列当中的首元素，对其进行打印，并销毁，再对二叉树进行递归放入队列当中，如果根节点的左子树中存在数据，我们将其取出放入队列中，如果二叉树的根节点的右子树中，包含数据，我们也对其进行取出放入队列当中，再对队列，进行首元素提取，打印，打印完之后再对该元素进行销毁
void BinaryTreeLevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root) { QueuePush(&q, root); } //如果队列不为空，进入。 while (!QueueEmpty(&q)) { //取出 打印 BTNode* front = QueueFront(&q); printf("%c ", front->data); QueuePop(&q); if (front->left) { QueuePush(&q, front->left); } if (front->right) { QueuePush(&q, front->right); } } printf("\n"); //销毁队列 QueueDestroy(&q); }
8.判断是否为完全二叉树
1.如果后面全是空，则是完全二叉树；
2.如果后面还有非空，则不是完全二叉树。
int BinaryTreeComplete(BTNode* root) { Queue q; QueueInit(&q); if (root) { QueuePush(&q, root); } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); if (front) { QueuePush(&q, front->left); QueuePush(&q, front->right); } else { //遇到NULL，跳出。 break; } } //1.如果后面全是空，则是完全二叉树； //2.如果后面还有非空，则不是完全二叉树。 while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); if (front) { QueueDestroy(&q); return false; } } QueueDestroy(&q); return true; }
代码汇总：
bt.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<string.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);
bt.c
#include"bt.h" #include"queue.h" // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树 BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi) { if (a[*pi] == NULL || (*pi) >= n) { a[(*pi)++]; return NULL; } BTNode* root = (BTNode*)malloc(sizeof(BTNode)); if (root == NULL) { perror("fail:malloc"); return; } root->data = a[(*pi)++]; root->left = BinaryTreeCreate(a,n,pi); root->right = BinaryTreeCreate(a,n,pi); return root; } // 二叉树销毁 void BinaryTreeDestory(BTNode* root) { if (root == NULL) { return; } BinaryTreeDestory(root->left); BinaryTreeDestory(root->right); free(root); } // 二叉树节点个数 int BinaryTreeSize(BTNode* root) { if (root == NULL) return 0; return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right); } // 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right) return 1; return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right); } // 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k) { assert(k >= 1); if (root == NULL) return 0; 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* ret1 = BinaryTreeFind(root->left, x); if (ret1) return ret1; BTNode* ret2 = BinaryTreeFind(root->right, x); if (ret2) return ret2; return NULL; } // 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) return; printf("%c ", root->data); BinaryTreePrevOrder(root->left); BinaryTreePrevOrder(root->right); } // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) return; BinaryTreePrevOrder(root->left); printf("%c ", root->data); BinaryTreePrevOrder(root->right); } // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) { if (root == NULL) return; BinaryTreePrevOrder(root->left); BinaryTreePrevOrder(root->right); printf("%c ", root->data); } // 层序遍历 void BinaryTreeLevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root != NULL) { //如果根节点不为空，我们对其进行存储 QueuePush(&q,root); } while (!QueueEmpty(&q)) { //取出 打印 BTNode* front = QueueFront(&q); printf("%c",front->data); QueuePop(&q); if (front->left) { QueuePush(&q,front->left); } if (front->right) { QueuePush(&q,front->right); } } printf("\n"); QueueDestroy(&q); } // 判断二叉树是否是完全二叉树 int BinaryTreeComplete(BTNode* root) { Queue q; QueueInit(&q); if (root) { QueuePush(&q, root); } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); if (front) { QueuePush(&q, front->left); QueuePush(&q, front->right); } else { //遇到NULL，跳出。 break; } } //1.如果后面全是空，则是完全二叉树； //2.如果后面还有非空，则不是完全二叉树。 while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); if (front) { QueueDestroy(&q); return false; } } QueueDestroy(&q); return true; }
Queue.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> //前置声明 struct BinaryTreeNode; typedef struct BinaryTreeNode* QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct { QNode* head; QNode* tail; }Queue; //初始化 void QueueInit(Queue* pq); //销毁 void QueueDestroy(Queue* pq); //放数据 void QueuePush(Queue* pq, QDataType x); //删除 void QueuePop(Queue* pq); //长度 int QueueSize(Queue* pq); //取头 QDataType QueueFront(Queue* pq); //取尾 QDataType QueueBack(Queue* pq); //判断空 bool QueueEmpty(Queue* pq);
Queue.c
#include"queue.h" //初始化 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } //销毁 void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } //放数据 void QueuePush(Queue* pq, QDataType x) { assert(pq); //开辟空间 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } //添加数据 newnode->data = x; newnode->next = NULL; //链接 if (pq->tail == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } } //判断空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } //删除 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* 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); QNode* cur = pq->head; int count = 0; while (cur) { ++count; cur = cur->next; } return count; }
Test.c
#include"bt.h" #include"queue.h" int main() { char ch[] = "ABD##E#H##CF##G##"; //gets(ch); int n = strlen(ch); int i = 0; //BinaryTreeCreate BTNode* root = BinaryTreeCreate(ch, n, &i); //进行前序遍历，输出遍历结果。 BinaryTreePrevOrder(root); printf("\n"); //进行中序遍历，输出遍历结果。 BinaryTreeInOrder(root); printf("\n"); //进行后序遍历，输出遍历结果。 BinaryTreePostOrder(root); printf("\n"); //结点个数 int ret = BinaryTreeSize(root); printf("%d\n", ret); //叶结点的个数 int ret1 = BinaryTreeLeafSize(root); printf("%d\n", ret1); //第k个结点 int ret2 = BinaryTreeLevelKSize(root, 2); printf("%d\n", ret2); //借用队列实现层序遍历 BinaryTreeLevelOrder(root); // 判断二叉树是否是完全二叉树 int ret3 = BinaryTreeComplete(root); printf("%d\n", ret3); BTNode* c = BinaryTreeFind(root, ch[2]); printf("%c", c->data); BinaryTreeDestory(root); root = NULL; return 0; }
