C语言实现普通二叉树的数据结构

逐个分析： 

头文件及结构定义：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>//包含bool true false
#include<assert.h>typedef int data_t;
typedef struct BinaryTreeNode {data_t val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

二叉树的创建： 

BTNode* CreateTree(data_t x) {BTNode* p = (BTNode*)malloc(sizeof(BTNode));p->val = x;p->left = NULL;p->right = NULL;return p;
}

二叉树的前序遍历：
 

void PreFind(BTNode* root) {if (root == NULL)return;printf("%d ", root->val);PreFind(root->left);PreFind(root->right);
}

二叉树的后序遍历：
 

void PostFind(BTNode* root) {if (root == NULL) return;PostFind(root->left);PostFind(root->right);printf("%d ", root->val);
}

二叉树的中序遍历：
 

void InFind(BTNode* root) {if (root == NULL)return;InFind(root->left);printf("%d ", root->val);InFind(root->right);
}

求解二叉树的高度/深度：
 

int getHeight(BTNode* root) {if (root==NULL)return 0;int hleft = getHeight(root->left);int hright= getHeight(root->right);return (hleft>hright?hleft:hright) + 1;
}

求解二叉树中元素个数：
 

void getCount(BTNode* root, int* pSize) {if (root == NULL)return;getCount(root->left,pSize);getCount(root->right,pSize);++(*pSize);
}

求解二叉树中元素个数的另一种方法：

int getCount2(BTNode* root) {if (root == NULL)return 0;return getCount2(root->left) + getCount2(root->right) + 1;
}

判断一个二叉树是不是单值二叉树：Leetcode的原题链接
 

bool isUnivalTree(BTNode* root) {if (root == NULL)return true;if (root->left && root->val != root->left->val)return false;if (root->right && root->val != root->right->val)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}

求出第k层有多少个元素（根节点位于第一层）：

int getKLevel(BTNode* root, int k) {//求出第k层有多少个元素（根节点位于第一层）;if (root == NULL)return 0;if (k == 1)return 1;//k==1说明到了我们要找的第k层了，而且越过root==NULL说明这一层不是空，且下面可能还挂有其他更底层的节点，但没办法，到K层了，所以把这一层的元素个数记为1，return即可;int leftCnt = getKLevel(root->left, k - 1);int rightCnt= getKLevel(root->right, k - 1);return leftCnt + rightCnt;//这里不能再+1了！
}

main函数：
 

int main() {BTNode* p1 = CreateTree(10);BTNode* p2 = CreateTree(20);BTNode* p3 = CreateTree(30);BTNode* p4 = CreateTree(40);BTNode* p5 = CreateTree(50);p1->left = p2;p2->right = p3;p1->right = p4;p4->right = p5;PreFind(p1);puts("");InFind(p1);puts("");PostFind(p1);puts("");int size = 0;int* pSize = &size;getCount(p1, pSize);printf("getCount()元素个数:%d\n", *pSize);printf("getCount2()求出来元素个数:%d\n", getCount2(p1));int height = getHeight(p1);printf("树的高度:%d\n", height);printf("这棵树是不是单值二叉树:%d\n", isUnivalTree(p1));//单值二叉树当且仅当一个二叉树中所有节点值相等;puts("");puts("");puts("");int k;for(k = 1;k<=height;k++)printf("第%d层的元素个数为%d\n", k, getKLevel(p1, k));return 0;
}

总览代码：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>//包含bool true false
#include<assert.h>typedef int data_t;
typedef struct BinaryTreeNode {data_t val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* CreateTree(data_t x) {BTNode* p = (BTNode*)malloc(sizeof(BTNode));p->val = x;p->left = NULL;p->right = NULL;return p;
}
void PreFind(BTNode* root) {if (root == NULL)return;printf("%d ", root->val);PreFind(root->left);PreFind(root->right);
}
void PostFind(BTNode* root) {if (root == NULL) return;PostFind(root->left);PostFind(root->right);printf("%d ", root->val);
}
void InFind(BTNode* root) {if (root == NULL)return;InFind(root->left);printf("%d ", root->val);InFind(root->right);
}
int getHeight(BTNode* root) {if (root==NULL)return 0;int hleft = getHeight(root->left);int hright= getHeight(root->right);return (hleft>hright?hleft:hright) + 1;
}
void getCount(BTNode* root, int* pSize) {if (root == NULL)return;getCount(root->left,pSize);getCount(root->right,pSize);++(*pSize);
}
int getCount2(BTNode* root) {if (root == NULL)return 0;return getCount2(root->left) + getCount2(root->right) + 1;
}
bool isUnivalTree(BTNode* root) {if (root == NULL)return true;if (root->left && root->val != root->left->val)return false;if (root->right && root->val != root->right->val)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}
int getKLevel(BTNode* root, int k) {//求出第k层有多少个元素（根节点位于第一层）;if (root == NULL)return 0;if (k == 1)return 1;//k==1说明到了我们要找的第k层了，而且越过root==NULL说明这一层不是空，且下面可能还挂有其他更底层的节点，但没办法，到K层了，所以把这一层的元素个数记为1，return即可;int leftCnt = getKLevel(root->left, k - 1);int rightCnt= getKLevel(root->right, k - 1);return leftCnt + rightCnt;//这里不能再+1了！
}
int main() {BTNode* p1 = CreateTree(10);BTNode* p2 = CreateTree(20);BTNode* p3 = CreateTree(30);BTNode* p4 = CreateTree(40);BTNode* p5 = CreateTree(50);p1->left = p2;p2->right = p3;p1->right = p4;p4->right = p5;PreFind(p1);puts("");InFind(p1);puts("");PostFind(p1);puts("");int size = 0;int* pSize = &size;getCount(p1, pSize);printf("getCount()元素个数:%d\n", *pSize);printf("getCount2()求出来元素个数:%d\n", getCount2(p1));int height = getHeight(p1);printf("树的高度:%d\n", height);printf("这棵树是不是单值二叉树:%d\n", isUnivalTree(p1));//单值二叉树当且仅当一个二叉树中所有节点值相等;puts("");puts("");puts("");int k;for(k = 1;k<=height;k++)printf("第%d层的元素个数为%d\n", k, getKLevel(p1, k));return 0;
}