链式二叉树的结构体

typedef char BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left;//指向左孩子节点 struct BinaryTreeNode* right;//指向右孩子节点 }BTNode;

链式二叉树的头文件

#include <stdio.h> #include <string.h> #include <assert.h> #include <stdlib.h> typedef char BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left;//指向左孩子节点 struct BinaryTreeNode* right;//指向右孩子节点 }BTNode; void PreOrder(BTNode* root);//先序遍历 void Inorder(BTNode* root);//中序遍历 void PostOrder(BTNode* root);//后序遍历 int BinaryTreeSize(BTNode* root);//节点个数 int BinaryLeafSize(BTNode* root)//二叉树叶子节点个数 int BinaryTreeLevel(BTNode* root);//二叉树的高度 int BinaryTreeLevelLSize(BTNode* root, int k);//二叉树第K层节点个数 BTNode* BinaryTreeNodeFind(BTNode* root, BTDataType x);//查找值为x的节点 void BinaryTreeDestroy(BTNode* root);//销毁二叉树 void LevelOrder(BTNode* root);//层序遍历 bool CompleteBinaryTree(BTNode* root);//判断是否为完全二叉树

接口实现

二叉树节点个数

思路分析：二叉树总节点个数 = 根节点 + 左子树节点个数 + 右子树节点个数，

通过递归遍历左右子树，如果节点不存在那么就返回0，存在就+1

int BinaryTreeSize(BTNode* root)//节点个数 { if (root == NULL) { return 0; } return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right); }

二叉树叶子节点的个数

思路分析：

叶子节点特征：度为0，也就是说无左右孩子节点

叶子节点总个数 = 左子树叶子节点个数 + 右子树叶子节点个数

传入一个根节点，当左右孩子节点都为NULL，那么就返回1

如果传入的根节点为NULL，那么直接返回0

int BinaryLeafSize(BTNode* root)//二叉树叶子节点个数 { if (root == NULL) { return 0; } if (root && root->left == NULL && root->right == NULL) { return 1; } return BinaryLeafSize(root->left) + BinaryLeafSize(root->right); }

二叉树的高度

思路分析：

二叉树的高度 = 根节点 + 左右子树中较为高的那一个高度

由于要去比较左右子树的高度，故应该用left_level和right_level去存储左右子树的高度，并进行比较，用max去存储最高的那一个数值，并和根节点进行相加

int BinaryTreeLevel(BTNode* root)//二叉树的高度 { if (root == NULL) { return 0; } int left_level = BinaryTreeLevel(root->left); int right_level = BinaryTreeLevel(root->right); int max = left_level > right_level ? left_level : right_level;//比较左右子树的高度 return 1 + max; }

二叉树第k层的节点个数

思路分析：

根节点所在的是第一层，对于整棵树而言，第k层就是第k层

但是从根节点的左右孩子节点来看，是第（k-1）层

求第k层的节点个数 = 左子树的（k-1）层节点数+ 右子树的（k-1）层节点数

特殊情况：如果是求第一层的节点个数，即只有根节点，直接返回1就可以，如果根节点不存在返回0

int BinaryTreeLevelkLSize(BTNode* root, int k)//二叉树第K层节点个数 { //边界保护 if (k <= 0) { return 0; } if (k == 1 && root) { return 1; } if (root == NULL) { return 0; } return BinaryTreeLevelkLSize(root->left, k - 1) + BinaryTreeLevelkLSize(root->right, k - 1); }

查找值为x的结点

思路分析：

首先从根结点开始查，若不是根节点，则在左右子树开始遍历

若在左子树查找到，那么就不用在右子树查找，直接返回x结点所在的地址

若未在左子树查找到，那么就在右子树查找

BTNode* BinaryTreeNodeFind(BTNode* root, BTDataType x)//查找值为x的节点 { if (root->data == x) { return root; } if (root == NULL) { return NULL; } //如果程序进行到这里，仍未找到那么就排除根节点 //开始查找左子树 BTNode* LeftFind = BinaryTreeNodeFind(root->left, x); if (LeftFind) { return LeftFind; } //开始查找右子树 BTNode* RightFind = BinaryTreeNodeFind(root->right, x); if (RightFind) { return RightFind; } //在根节点和左右子树均未找到 return NULL; // }

二叉树销毁

思路分析：

由于需要通过影响形参去改变实参，故此时需要二级指针，释放内存后将根节点置于空NULL

注意：

若要先释放根结点，那么就找不到它的左右子树

故按照左右根顺序释放，和后序遍历的顺序一致

void BinaryTreeDestroy(BTNode** root)//销毁二叉树 { if (*root = NULL) { return; } BinaryTreeDestroy(&(*root)->left);//注意！！！：此处传入二级指针 BinaryTreeDestroy(&(*root)->right);//注意！！！：此处传入二级指针 free(*root); *root = NULL; }

层序遍历

层序遍历结果：

思路分析

传入根节点之后，直接打印根节点的存储数据内容

而后再将根结点的左右孩子传入，打印左右孩子的存储数据内容

再将根结点的左右孩子的左右孩子结点地址传入，打印左右孩子的左右孩子存储数据内容

往后重复这个内容

故可以考虑借助队列来实现这段内容

循环往复：再取队头，将队头的左右孩子结点入队列，再打印队头，出队头，直到队列为空

准备工作：

先将队列元素修改为二叉树的结点元素

typedef BTNode* PtrDataType; typedef struct PtrQueueNode { PtrDataType data; struct PtrQueueNode* next; } PQNode; typedef struct PtrQueue { PQNode* phead; PQNode* ptail; int size; } PQueue;

而后再写入层序遍历所需要的队列执行相关函数

void PQueueInit(PQueue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; } BTNode* BuyNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { perror("Fail!"); exit(-1); } node->data = x; node->left = NULL; node->right = NULL; return node; } void PQueuePush(PQueue* pq, PtrDataType x) { assert(pq); PQNode* newnode = (PQNode*)malloc(sizeof(PQNode)); if (newnode == NULL) { perror("malloc fail"); exit(1); } newnode->data = x; newnode->next = NULL; if (pq->phead == NULL) { pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } bool PQueueEmpty(PQueue* pq) { assert(pq); return pq->phead == NULL; } void PQueuePop(PQueue* pq) { assert(pq); assert(!PQueueEmpty(pq)); PQNode* next = pq->phead->next; free(pq->phead); pq->phead = next; if (pq->phead == NULL) pq->ptail = NULL; pq->size--; } PtrDataType PQueueFront(PQueue* pq) { assert(pq); assert(!PQueueEmpty(pq)); return pq->phead->data; } void PQueueDestroy(PQueue* pq) { assert(pq); PQNode* cur = pq->phead; while (cur) { PQNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; }

准备工作完成后，开始进行层序遍历函数的书写

void LevelOrder(BTNode* root)//层序遍历 { PQueue q; PQueueInit(&q); if (root) { PQueuePush(&q, root); } while (!PQueueEmpty(&q)) { BTNode* top = PQueueFront(&q); printf("%c ", top->data); if (top->left) PQueuePush(&q, top->left); if (top->right) PQueuePush(&q, top->right); PQueuePop(&q); } printf("\n"); PQueueDestroy(&q); }

判断是否为完全二叉树

完全二叉树的结点与序号是一一对应的关系，同样通过借助队列来完成判断

与 层序遍历的区别在于，不管结点内容是否为空，都将入队处理

完全二叉树的本质是：

按层序遍历给结点编号时，所有结点必须占据“前 n 个位置”，中间不能有空位，后面也不能再冒出结点。

若第二次循环顺利结束，接下来均为NULL，则为完全二叉树

所以判断逻辑是：

• 按层序把结点入队，空孩子也入队。

• 第一次遇到NULL时，说明从这里开始进入“空位区”。

• 如果这个NULL后面还有任何非空结点，就说明：

  • 前面已经出现了空位；

  • 后面却又出现了真实结点；

  • 层序序列中出现了“非空—空—非空”的情况；

  • 这不符合完全二叉树。

• 如果第一次遇到NULL后，队列剩余元素全是NULL，说明所有真实结点都连续排在前面，后面全是空位，符合完全二叉树。

bool CompleteBinaryTree(BTNode* root)//判断是否为完全二叉树 { PtrQueue q; PQueueInit(&q); PQueuePush(&q, root);//根结点入队 while (!PQueueEmpty(&q)) { BTNode* top = PQueueFront(&q);//取队头 if (top == NULL) {//队头为空，跳出循环 break; } PQueuePush(&q, top->left);//入队左孩子 PQueuePush(&q, top->right);//入队右孩子 PQueuePop(&q);//出队列 } while (!PQueueEmpty(&q)) { BTNode* top = PQueueFront(&q);//取队头 if (top != NULL) { return false; } PQueuePop(&q); } PQueueDestroy(&q); return true; }