二叉树的实现（C语言版）
今天给大家说一下二叉树的实现，这个使用c语言写的，话不多说，先看看代码：
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int type;
typedef struct tree
{//数据域type val;//左孩子指针struct tree* left;//右孩子指针struct tree* right;
}tree;
//创建二叉树
void creat(tree** root);
//二叉树的高度
int high(tree** root);
//二叉树的左右孩子交换
void swap(tree** root);
//前序遍历
void printfront(tree* root);
//中序遍历
void printmid(tree* root);
//后序遍历
void printback(tree* root);
//叶子结点
int leafnode(tree* root);
//单分支节点
int onenode(tree* root);
//总结点
int sumnode(tree* root);
#define _CRT_SECURE_NO_WARNINGS 1
#include "tree.h"
//创建二叉树
void creat(tree** root)
{assert(root);int ret = 0;printf("是否要生成左孩子或是右孩子0,1->\\n");scanf("%d", &ret);if (0 == ret){*root = NULL;printf("取消生成左孩子或是右孩子\\n");return;}else{tree* tem = (tree*)malloc(sizeof(tree));assert(tem);*root = tem;printf("请输入你要保存的值->:\\n");scanf("%d", &((*root)->val));creat(&(*root)->left);creat(&(*root)->right);}
}
//二叉树的高度
int high(tree** root)
{if (*root == NULL)return 0;else{int left = high(&(*root)->left);int right = high(&(*root)->right);if (left > right)return left + 1;else if (right > left)return right + 1;elsereturn left + 1;}
}
//交换二叉树的左右子树
void swap(tree** root)
{if (*root == NULL)return;else{tree* node = (*root)->left;(*root)->left = (*root)->right;(*root)->right = node;swap(&(*root)->left);swap(&(*root)->right);}
}
//前序遍历
void printfront(tree* root)
{if (root == NULL)return;else{printf("%d->", root->val);printfront(root->left);printfront(root->right);}
}
//二叉树的中序遍历
void printmid(tree* root)
{if (root == NULL)return;else{printmid(root->left);printf("%d->", root->val);printmid(root->right);}
}
//二叉树的后序遍历
void printback(tree* root)
{if (root == NULL)return;else{printback(root->left);printback(root->right);printf("%d->", root->val);}
}
//计算二叉树的叶子结点
int leafnode(tree* root)
{if (root == NULL)return 0;else if (root->left == root->right)return 1;else{int left = leafnode(root->left);int right = leafnode(root->right);return left + right;}
}
//计算单分支节点的个数
int onenode(tree* root)
{if (root == NULL)return 0;else if (root->left == NULL && root->right != NULL)return 1;else if (root->right == NULL && root->left != NULL)return 1;else{int left = onenode(root->left);int right = onenode(root->right);return left + right;}
}
//计算二叉树的总结点数
int sumnode(tree* root)
{if (root == NULL)return 0;else{int left = sumnode(root->left);int right = sumnode(root->right);return left + right + 1;}
}#define _CRT_SECURE_NO_WARNINGS 1
#include "tree.h"
void test1()
{tree* root;//创建二叉树creat(&root);//二叉树的高度printf("二叉树的高度:");int treehigh=high(&root);printf("%d\\n",treehigh);//二叉树的前序遍历printf("二叉树的前序遍历:");printfront(root);printf("\\n");//二叉树的左右子树交换printf("二叉树左右子树的交换：");swap(&root);printf("\\n");//二叉树的前序遍历printf("二叉树的前序遍历:");printfront(root);printf("\\n");//二叉树的中序遍历printf("二叉树的中序遍历:");printmid(root);printf("\\n");//二叉树的后序遍历printf("二叉树的后序遍历:");printback(root);printf("\\n");//二叉树的总结点数printf("二叉树的总结点数:");int sum = sumnode(root);printf("%d\\n", sum);//二叉树的叶子结点数printf("二叉树的叶子节点数：");int leaf = leafnode(root);printf("%d\\n", leaf);//二叉树的单分支节点printf("二叉树的单分支节点：");int one = onenode(root);printf("%d\\n", one);
}
int main()
{test1();return 0;
}老样子，写的比较正规一些，用了三个文件来实现的，就不详细说了。
先是头文件，相信学完c的你们很快就能看懂吧，这里就不详细说了，先看看tree.c这个文件，这个文件我是用来实现函数的，而test.c是测试的。所以，这里也不用多说了吧！
来说一下代码思路以及讲解吧！首先，要写二叉树的话必不可少的是要知道二叉树的存储结构，他是一个非线性的结构，但是我们可以根据图来看，很容易就能理解的是二叉树像是一种递归的结构，所以创建他的时候我们就用递归来创建，首先，先创建一个二叉树节点的指针，使他指向是这个二叉树的根节点，此时我们就可以创建了，因为是递归性质，所以我们不能无限的递归下去，要有限制条件，而且使他越来越接近这个递归条件，所以我用了ret这个变量来控制他的递归，选择条件是0或1,1是继续生成，0则是取消。
其次，这里要注意的是，我没有专门处理ret，所以只要你的选择是非0的数，都可以生成左右孩子，如果生成孩子的话，就很简单了，我们就申请空间，判断（这里说一下，因为个人感觉用if语句判断是否申请成功感觉很麻烦，所以直接断言，如果没有成功的话就直接退出程序）是否申请成功，然后分别把他的左右指针域用递归来继续生成。
第二，二叉树的遍历分为两大类，一种是递归，一种用队列来遍历，这里队列的遍历没有写，大家可以自己写一下，（很简单，需要先实现一个队列），递归的话就比较简单了，分为前序，中序，后序。前序：先是访问根节点，在左子树，最后是右子树，中序：左，根，右。后序：左，右，根。这个就很简单，这里也不再详细说。看代码就懂了。
剩下的就是计算树的高度了，这个其实很简单，脑海中想象出一颗树，先算左子树的高度，再算右子树的高度，最后比较左右子树的高度，然后让高的那个子树+1，就可以了。这里的+1是加上根节点的高度。
然后是交换左右子树，这个也比较简单，就是判断这个树是否为空，如果是空树的话就直接结束，否则交换左右子树，需要一个变量，就和两个数的交换是一样的道理，然后递归。
叶子结点的思路也很简单，就是左右指针的指向都是NULL就好了，但是这个里我写的是左右指针相等，其实原理相同，都是一样。没有什么区别。
单分支节点，个人感觉思路和算叶子结点的思路很像 ，要么左指针为空，右指针不空，要么右指针为空，左指针不空的话就返回1，然后递归接好了
计算总结点数，也是一样的道理，这里就不多说。
下面要说的是一个我个人认为困惑了我很久的知识点，那就是二叉树的交换，为什么可以交换呢？我其实刚开始有点懵，困惑了我很长时间，我在网上也搜了很多，有的人说是二叉树中不全是有序的，但是我还是不理解，因为二叉树的一个概念就是左右孩子是有次序的，不能颠倒。后来我也问了我的一个老师，他的回答让我拨云见日，他说如果换了，就不是同一个二叉树了。我也仔细想了一下。觉得他说的很详细，而我对这个的理解是这样的，同一个二叉树中，是不能交换的，如果硬要换，那么他就会形成一个新的二叉树，跟原来的二叉树不一样。这个一定要注意。
其次就是前中后序遍历中，不一定要用打印函数把这个值打印出来，他可以做很多的操作，比如线索话二叉树的时候，可以进行线索化的操作，也可以进行找前驱节点，所以，这里要灵活一些。
然后就是在创建二叉树的时候，我把左右指针赋值为NULL的操作写到了当你选择不生成孩子的时候那个里面，这是因为，如果你写到了你选生成孩子的那个里面的时候，你要用递归去生成左孩子或右孩子的时候，在给函数传参的时候，会有对空指针的解引用，所以，一定要写到Ret==0的那个里面。
以上就是个人对二叉树的理解，有不足之处希望大家可以指出，希望大家支持，谢谢！！！！！