二叉树（C语言）

目录1. 二叉树定义2. 代码实现1. 二叉树定义在堆C语言章节我们已经了解了堆的数据结构是完全二叉树。而二叉树的定义则更加广泛限制也比完全二叉树少空树节点数为0每个节点的子节点数不超过两个例如以下这些都是二叉树2. 代码实现// 二叉树的创建会放在之后的章节进行说明这里先临时用古法建树 代码主要采用递归的方式实现各函数功能文件内部有详细注释//BinaryTree.h文件#pragma once #includestdlib.h #includemath.h #includestdio.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; }// 感谢阅读~︶↗