二叉树（C语言）

目录

1. 二叉树定义

2. 代码实现

1. 二叉树定义

在堆（C语言）章节我们已经了解了堆的数据结构是完全二叉树。而二叉树的定义则更加广泛，限制也比完全二叉树少：

• 空树（节点数为0）
• 每个节点的子节点数不超过两个

例如以下这些都是二叉树：

2. 代码实现

// 二叉树的创建会放在之后的章节进行说明，这里先临时用古法建树 >"<

代码主要采用递归的方式实现各函数功能，文件内部有详细注释：

//BinaryTree.h文件

#pragma once #include<stdlib.h> #include<math.h> #include<stdio.h> typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType val; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; //新建树节点 BTNode* BuyNode(BTDataType val); //创建固定二叉树，返回根节点 BTNode* CreateBinaryTree(); //前序遍历 void PreOrder(BTNode* root); //中序遍历 void MidOrder(BTNode* root); //后序遍历 void PostOrder(BTNode* root); //计算节点个数 int TreeSize(BTNode* root); //计算叶子节点数 int LeafSize(BTNode* root); //计算树的高度 int TreeHeight(BTNode* root); //计算第K层节点个数 int LeafLevelKSize(BTNode* root, int k); //根据值查找节点 BTNode* TreeFind(BTNode* root, BTDataType x);

//BinaryTree.c文件

#include "BinaryTreeNode.h" //新建树节点 BTNode* BuyNode(BTDataType val) { BTNode* tmp = (BTNode*)malloc(sizeof(BTNode)); if(tmp == NULL) { perror("malloc fail"); exit(1); } tmp->val = val; tmp->left = NULL; tmp->right = NULL; return tmp; } //创建固定二叉树 BTNode* CreateBinaryTree() { 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 = node4; node2->left = node3; node4->left = node5; node4->right = node6; return node1; } //前序遍历 void PreOrder(BTNode* root) { if(!root) return; printf("%d ", root->val); //根 PreOrder(root->left); //左 PreOrder(root->right); //右 } //中序遍历 void MidOrder(BTNode* root) { if(!root) return; MidOrder(root->left); //左 printf("%d ", root->val); //根 MidOrder(root->right); //右 } //后序遍历 void PostOrder(BTNode* root) { if(!root) return; PostOrder(root->left); //左 PostOrder(root->right); //右 printf("%d ", root->val); //根 } //计算节点个数 int TreeSize(BTNode* root) { if(!root) return 0; //左子树节点数 + 右子树节点数 + 当前节点 return TreeSize(root->left) + TreeSize(root->right) + 1; } //计算叶子节点数 int LeafSize(BTNode* root) { //要考虑root为空的情况！否则会报错 if(!root) return 0; //左右都为空，即为叶子节点 if(!root->left && !root->right) return 1; return LeafSize(root->left) + LeafSize(root->right); } //计算树的高度 int TreeHeight(BTNode* root) { if(!root) return 0; //取左右子树中较深的一棵，算入当前层数 return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1; } //计算第K层节点个数 int LeafLevelKSize(BTNode* root, int k) { if(!root) return 0; //到达K层则将当前节点计入总数 if(k == 1) return 1; return LeafLevelKSize(root->left, k-1) + LeafLevelKSize(root->right, k-1); } //根据值查找节点 BTNode* TreeFind(BTNode* root, BTDataType x) { if(!root) return NULL; if(root->val == x) return root; BTNode* ret1 = TreeFind(root->left, x); if(ret1 != NULL) { return ret1; //找到就return，不必遍历右子树 } BTNode* ret2 = TreeFind(root->right, x); if(ret2 != NULL) { return ret2; } return NULL; //注意不要漏掉if条件之外的return！ }

这里附上一个测试文件：

#include "BinaryTreeNode.h" #include "BinaryTreeNode.c" int main() { BTNode* root = CreateBinaryTree(); PreOrder(root); printf("\n"); MidOrder(root); printf("\n"); PostOrder(root); printf("\n"); int size = TreeSize(root); printf("树的节点个数为%d个。\n", size); int leaf = LeafSize(root); printf("树的叶子节点个数为%d个。\n", leaf); int height = TreeHeight(root); printf("树的高度为%d。\n", height); int k = 0; printf("树的高度为%d，请输入你要查询的层数：\n", height); scanf("%d", &k); int LevelKNode = LeafLevelKSize(root, k); printf("第%d层的节点数为%d。\n", k, LevelKNode); int FindVal = 0; printf("请输入你要查找的值：\n"); scanf("%d", &FindVal); BTNode* FindOut = TreeFind(root, FindVal); if(!FindOut) { printf("没有找到。\n"); } else { printf("找到了。\n"); } return 0; }

// 感谢阅读~（￣︶￣）↗