实现链式结构二叉树（二叉链）上篇
前言
二叉树基本概念
代码位置
[gitee](BinaryTree · petrichor/2024-summer-c-language - 码云 - 开源中国 (gitee.com))
二叉链的概念与结构
概念
⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址。
结构
typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode;
回顾二叉树
⼆叉树分为空树和⾮空⼆叉树，⾮空⼆叉树由根结点、根结点的左⼦树、根结点的右⼦树组成的
根结点的左⼦树和右⼦树分别⼜是由⼦树结点、⼦树结点的左⼦树、⼦树结点的右⼦树组成的，因此，⼆叉树定义是递归式的，后续链式⼆叉树的操作中基本都是按照该概念实现的。
二叉链的实现
BinaryTree.h(其中方法会一一讲到)
- 定义二叉链结构
- 将存储数据类型重命名(方便之后替换->例如我们要求二叉链内存储char类型数据，只用改一行代码即可)
- 所写的函数的声明，声明的时候参数只需要类型就可以了，名字加不加都一样
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> //定义二叉树的链式结构 //二叉树结点的结构 typedef int BTDataType; typedef struct BinaryTreeNode { int data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; //前序遍历 void PreOrder(BTNode* root); //中序遍历 void InOrder(BTNode* root); //后序遍历 void PostOrder(BTNode* root); // ⼆叉树结点个数 int BinaryTreeSize(BTNode* root); // ⼆叉树结点个数 //void BinaryTreeSize(BTNode* root, int* psize); // ⼆叉树叶子结点个数 int BinaryTreeLeafSize(BTNode* root); // ⼆叉树第k层结点个数 int BinaryTreeLevelKSize(BTNode* root, int k); //⼆叉树的深度/⾼度 int BinaryTreeDepth(BTNode* root); // ⼆叉树查找值为x的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // ⼆叉树销毁 void BinaryTreeDestory(BTNode** root); //层序遍历 void LevelOrder(BTNode* root); //判断二叉树是否为完全二叉树 bool BinaryTreeComplete(BTNode* root);
test.c
- 用来测试我们写的函数(函数的调用)
- 这一部分就是自己写的时候用的测试用例，随便什么都行
最好是写一个方法测试一次，不然找错误的时候会很痛苦😜
#define _CRT_SECURE_NO_WARNINGS 1 #include"Binary.h" BTNode * buyNode(BTDataType x) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); if (newnode == NULL) { perror("malloc fail!"); exit(1); } newnode->data = x; newnode->left = newnode->right = NULL; return newnode; } void test01() { BTNode* node1 = buyNode(1); BTNode* node2 = buyNode(2); BTNode* node3 = buyNode(3); BTNode* node4 = buyNode(4); //BTNode* node5 = buyNode(5); //BTNode* node6 = buyNode(6); node1->left = node2; node1->right = node3; node2->right = node4; //node2->right = node5; //node3->left = node6; //PreOrder(node1); //printf("\n"); //InOrder(node1); //printf("\n"); //PostOrder(node1); //int size = 0; //BinaryTreeSize(node1, &size); //printf("size : %d\n", size); size = 0; //BinaryTreeSize(node1, &size); //printf("size : %d\n", size); //printf("size:%d\n", BinaryTreeSize(node1)); //printf("size:%d\n", BinaryTreeSize(node1)); //printf("size:%d\n", BinaryTreeSize(node1)); //printf("leaf size: %d\n", BinaryTreeLeafSize(node1)); //printf("第K层size : %d\n", BinaryTreeLevelKSize(node1, 2)); //printf("depth/height:%d\n", BinaryTreeDepth(node1)); //BTNode* find =BinaryTreeFind(node1, 33); //printf("%s\n", find == NULL ? "未找到！" : "找到了！"); //LevelOrder(node1); bool ret = BinaryTreeComplete(node1); printf("%s\n", ret == false ? "不是完全二叉树" : "是完全二叉树"); BinaryTreeDestory(&node1); } int main() { test01(); return 0; }
BinaryTree.c
函数方法的实现，重点重点！！！
二叉树的遍历
⼆叉树的操作离不开树的遍历，我们先来看看⼆叉树的遍历有哪些⽅式
按照规则，⼆叉树的遍历有：前序/中序/后序的递归结构遍历：
- 前序遍历(PreorderTraversal亦称先序遍历)：访问根结点的操作发⽣在遍历其左右⼦树之前
访问顺序为：根结点、左⼦树、右⼦树
2.中序遍历(InorderTraversal)：访问根结点的操作发⽣在遍历其左右⼦树之中（间）
访问顺序为：左⼦树、根结点、右⼦树
3.后序遍历(PostorderTraversal)：访问根结点的操作发⽣在遍历其左右⼦树之后
访问顺序为：左⼦树、右⼦树、根结点
前序遍历
- 核心思想就是递归：先递推，再回归
以前序遍历为例，传入根节点，依据前序遍历根左右的规则，我们只需先打印根节点，然后再将左结点当做一课新树的根节点进行相同操作，右子树同理
递归另一要素即终止条件，我们什么时候开始回归？
很容易想到，当我们在某一叶子结点的函数栈帧时，其左右结点都为空，在以此叶子结点为根节点开始前序遍历时，它的下一次递推创建的函数栈帧传过去的根节点就是空指针，不需要继续遍历，即当root==NULL时，直接返回即可。
void PreOrder(BTNode* root) { if (root == NULL) { return; } printf("%d ", root->data); PreOrder(root->left); PreOrder(root->right); }
图解：
中序遍历
//中序遍历--左根右 void InOrder(BTNode* root) { if (root == 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); }
二叉树的构建
- 二叉树的构建也是递归实现的
- 以一道题目为例
描述
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述：
输入包括1行字符串，长度不超过100。
输出描述：
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。
- 思路：分治思想，递归构建二叉树，构建二叉树先malloc出根节点然后再构建左子树，右子树即可。因为字符串需要构建之后指针向后移动找到下一个字符，所以需要一个count指针标记字符位置，构建之后指针向后移动，指针指向’#‘或者’\0’代表到了空节点了，完成返回NULL即可
#include<stdio.h> typedef struct TreeNode { char val; struct TreeNode* left; struct TreeNode* right; }TreeNode; TreeNode* maketree(char*arr,int*count) { if(arr[*count]=='#'||arr[*count]=='\0') { (*count)++; return NULL; } TreeNode* newnode = (TreeNode*)malloc(sizeof(TreeNode)); newnode->val = arr[(*count)++]; newnode->left = maketree(arr,count); newnode->right = maketree(arr,count); return newnode; } void Inorder(TreeNode* root) { if(root==NULL) { return; } Inorder(root->left); printf("%c ",root->val); Inorder(root->right); } int main() { char arr[101]; scanf("%s",arr); int count = 0; TreeNode* tree = maketree(arr,&count); Inorder(tree); return 0; }
- 重点还是递归，先构建根结点，再对左右子树构建，每次需要时申请一个结点空间即可，否则返回空指针
二叉树结点个数
- 要求二叉树结点个数，即当下结点+左子树+右子树
- 当结点某一子树为空时，返回0即可，递推结束
int BinaryTreeSize(BTNode* root) { if (root == NULL) { return 0; } return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right); }
二叉树的叶子结点个数
既然是叶子结点，那么度为0
- 要求叶子结点，就是求左右子树叶子结点之和，依次递推下去
- 满足叶子结点条件或是某一子树为空结束递推
// ⼆叉树叶⼦结点个数 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层结点个数
- 要求第k层节点个数，即左右子树作为单独的树，它们的k-1层结点之和
而左子树也有自己的左右子树，右子树同理，即这四棵子树作为单独的树，它们的第k-2层结点之和
以此类推可以写出递推方式
- 结束条件
当k==1时说明已经递推到第k层了
以及在递推过程中遇到空节点，返回0即可
// ⼆叉树第k层结点个数 int BinaryTreeLevelKSize(BTNode* root, int k) { if (root == NULL) { return 0; } if (k == 1) { return 1; } return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1); }
二叉树深度/高度
- 要求高度，即子树高度的最大值+1，子树高度的最大值又是其子树高度最大值+1，以此类推
- 当递推到空节点时结束——>返回0（空节点不算高度）
- 回归时每次返回左右子树高度取最大值+1
//⼆叉树的深度/⾼度 int BinaryTreeDepth(BTNode* root) { if (root == NULL) { return 0; } int leftDep = BinaryTreeDepth(root->left); int rightDep = BinaryTreeDepth(root->right); return leftDep > rightDep ? leftDep + 1 : rightDep + 1; }
BinaryTree.c（完整版）
#define _CRT_SECURE_NO_WARNINGS 1 #include "Binary.h" #include "Queue.h" //前序遍历---根左右 void PreOrder(BTNode* root) { if (root == NULL) { return; } printf("%d ", root->data); PreOrder(root->left); PreOrder(root->right); } //中序遍历--左根右 void InOrder(BTNode* root) { if (root == 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 size = 0; //int BinaryTreeSize(BTNode* root) //{ // if (root == NULL) // { // return 0; // } // ++size; // BinaryTreeSize(root->left); // BinaryTreeSize(root->right); // return size; //} //错误的写法 //void BinaryTreeSize(BTNode* root,int* psize) //{ // if (root == NULL) // { // return 0; // } // ++(*psize); // BinaryTreeSize(root->left,psize); // BinaryTreeSize(root->right,psize); //} // ⼆叉树结点个数 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 == NULL) { return 1; } return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right); } // ⼆叉树第k层结点个数 int BinaryTreeLevelKSize(BTNode* root, int k) { if (root == NULL) { return 0; } if (k == 1) { return 1; } return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1); } //⼆叉树的深度/⾼度 int BinaryTreeDepth(BTNode* root) { if (root == NULL) { return 0; } int leftDep = BinaryTreeDepth(root->left); int rightDep = BinaryTreeDepth(root->right); return leftDep > rightDep ? leftDep + 1 : rightDep + 1; } // ⼆叉树查找值为x的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) { return NULL; } if (root->data == x) { return root; } BTNode* leftFind = BinaryTreeFind(root->left, x); if (leftFind) { return leftFind; } BTNode* rightFind = BinaryTreeFind(root->right, x); if (rightFind) { return rightFind; } return NULL; } // ⼆叉树销毁 void BinaryTreeDestory(BTNode** root) { if (*root == NULL) { return; } BinaryTreeDestory(&((*root)->left)); BinaryTreeDestory(&((*root)->right)); free(*root); *root = NULL; }
