二叉树（C实现）
2021-04-23 本文已影响0人
大成小栈
假设要生成的二叉树如下图；
1. 二叉树的数据结构
如图，在树的每个节点中，需要保存的数据只有一个整数；
struct BinaryTree {
int data; // Data area
//TODO
};
所以在结构体里面，我们的代码应该类似上面的写法；通过观察我们还发现，每一个节点都指向左右两边（除了最后的叶子节点外）。
因此，我们需要让它有两个指针域：
struct BinaryTree {
int data; // Data area
void *left;
void *right;
};
上面的定义格式似乎是正确的，但是，类型好像并不是我们想要的；
例如：当left指向左边的子节点时，子节点应该也是一个包含数据域的节点，因此我们需要再定义一个与它本身相同的结构体：
struct BinaryTree {
int data; // Data area
struct BinaryTree *left;
struct BinaryTree *right;
};
所以，我们会这样去定义它，显然，这是一个递归定义。如果我们要实例化一个节点，我们可以:
struct BinaryTree *tree;
显然，我们需要定义一个实例时写那么长的类型名字，实在让人难受，因此，我们可以这样：
typedef struct BinaryTree TreeNode;
TreeNode *tree;
到此为止我们的数据结构就定义好了！
你现在的代码应该是下面的样子：
struct BinaryTree {
int data; // Data area
struct BinaryTree * left;
struct BinaryTree * right;
};
typedef struct BinaryTree TreeNode;
2. 二叉树的生成
接下来我们需要把数据插入到对应的位置上，我们希望树左边分支的的数据总是比树右边分支的要小。因此，我们代码会像下面这样写：
void insert(TreeNode ** tree, int val) {
TreeNode * temp = NULL;
if(!(*tree)) {
//TODO
return ;
}
if (val < (*tree)->data) {
//TODO
} else if (val > (*tree)->data) {
//TODO
}
}
第一个if语句判断这个树节点是否存在；
若是不存在，我们应该生成一个节点，然后添加到树上来；
第二个if-else呢，则是判断目标数据是大于当前节点还是小于，若小于，存左分支，若大于存右分支。
if(!(*tree)) {
temp = (TreeNode *)malloc(sizeof(TreeNode));
temp->left = temp->right = NULL;
temp->data = val;
*tree = temp;
return ;
}
temp的作用是临时变量正如其名；
malloc分配内存，初始化节点左右指针域为空，以及数据域为val；
最后*tree=temp 把节点安装到树上；
并且返回上一级；
对于已经存在的树节点，我们需要往左右两分子扩展；
if (val < (*tree)->data) {
insert(&(*tree)->left,val);
} else if (val > (*tree)->data) {
insert(&(*tree)->right,val);
}
可以看出，只对小于和大于两个方向的数据进行操作；
你也许会考虑到万一等于呢？注意，在这里应该是数据的唯一性有要求的，它类似于数学里的集合，不会有重复的。
那么这个函数的所有代码如下：
void insert(TreeNode ** tree, int val) {
node * temp = NULL;
if(!(*tree)) {
temp = (TreeNode *)malloc(sizeof(TreeNode));
temp->left = temp->right = NULL;
temp->data = val;
*tree = temp;
return ;
}
if (val < (*tree)->data) {
insert(&(*tree)->left,val);
}else if (val > (*tree)->data) {
insert(&(*tree)->right,val);
}
}
节点创建好了（此处用malloc创建），在堆中分配的内存，我们需要手动释放，那显然需要用到free函数与之对应。
所以，我们释放节点的函数应该是这样：
void deltree(TreeNode * tree) {
if(tree) {
free(tree);
}
}
但是，仔细观察发现直接释放free就只是释放了根节点，
因此，我们需要这样做：
void deltree(TreeNode * tree) {
if(tree) {
deltree(tree->left);
deltree(tree->right);
free(tree);
}
}
这样我们找到左边的根啦，又继续往左边找；
找不到啦，就往右边找；
再找不到啦，就执行到free释放节点然后返回上一级；
好啦！树也有函数建，也有办法“砍”了！
接下来是怎么展示我们的树啦！
3. 二叉树的递归遍历
树的遍历有三种：前序、中序、后序。首先，我们需要判断tree是否空；
void preOrder(TreeNode * tree) {
if(tree) {
//TODO
}
}
// 前序
void preOrder(TreeNode * tree) {
if(tree) {
printf("%d ",tree->data);
print_preorder(tree->left);
print_preorder(tree->right);
}
}
// 中序
void inOrder(TreeNode * tree) {
if(tree) {
print_inorder(tree->left);
printf("%d ",tree->data);
print_inorder(tree->right);
}
}
// 后序
void postOrder(TreeNode * tree) {
if(tree) {
print_postorder(tree->left);
print_postorder(tree->right);
printf("%d ",tree->data);
}
}
// 测试方法
int main(void) {
TreeNode * root;
TreeNode * tmp;
//int i;
root = NULL;
/* Inserting nodes into tree */
insert(&root,9);
insert(&root,4);
insert(&root,15);
insert(&root,6);
insert(&root,12);
insert(&root,17);
insert(&root,2);
printf("Pre Order Display\n");
preOrder(root);
printf("\n");
printf("In Order Display\n");
inOrder(root);
printf("\n");
printf("Post Order Display\n");
postOrder(root);
printf("\n");
/* Deleting all nodes of tree */
deltree(root);
}
////运行结果如下：
//Pre Order Display
//9 4 2 6 15 12 17
//In Order Display
//2 4 6 9 12 15 17
//Post Order Display
//2 6 4 12 17 15 9
4. 二叉树的迭代遍历
简单的递归遍历如下：
void preOrder(Tree *root){
if(root){
Visit(root->data); //printf
preOrder(root->lchild);
preOrder(root->rchild);
}
}
void inOrder(Tree *root){
if(root){
inOrder(root->lchild);
Visit(root->data); //printf
inOrder(root->rchild);
}
}
void postOrder(Tree *root){
if(root){
postOrder(root->lchild);
postOrder(root->rchild);
Visit(root->data); //printf
}
}
迭代遍历：
//// 前序遍历
void preOrder(Tree *root){
Stack s;
Tree *cur=root;
Tree *top=NULL;
if(root==NULL) return ;
Init(&s);
while(cur || !StackEmpty(&s)){
while(cur){
Visit(cur->data);
Push(&s,cur);
cur=cur->lchild;
}
top=StackTop(&s);
Pop(&s);
cur=top->rchild;
}
}
//// 中序遍历
void inOrder(Tree *root){
Stack s;
Tree *cur=root;
Tree *top=NULL;
if(root==NULL) return ;
Init(&s);
while(cur || !StackEmpty(&s)){
while(cur){
Push(&s,cur);
cur=cur->lchild;
}
top=StackTop(&s);
Visit(cur->data);
Pop(&s);
cur=top->rchild;
}
}
//// 后序遍历
void postOrder(Tree *root){
Stack s;
Tree *cur=root;
Tree *top=NULL;
Tree *prev=NULL;
if(root==NULL) return ;
Init(&s);
while(cur || !StackEmpty(&s)){
while(cur){
Push(&s,cur);
cur=cur->lchild;
}
top=StackTop(&s);
if(top->rchild==NULL || top->rchild==prev){
Visit(top->data);
prev=top;
Pop(&s);
}
else{
cur=top->rchild;
}
}
}
5. 二叉树的广度遍历
？？
6. 计算二叉树的高度
递归的方式来计算二叉树高度（只有一个根节点的二叉树高为1）。
//二叉树节点定义
typedef int ElementType;
typedef struct bitnode
{
ElementType data; //数据域
struct bitnode *left, *right; //指针域
} bitnode, *bitree; //bitnode为结构体，bitree为指向结构体bitnode的指针
//先序创建一棵二叉树
bitree CreateTree() {
bitree T;
ElementType item;
cin >> item;
if( item == 0 ) {
T = NULL; //T为空树
}
else {
T = (bitree)malloc(sizeof(bitnode));
T->data = item;
T->left = CreateTree(); //递归创建左子树
T->right = CreateTree(); //递归创建右子树
}
return T; //返回根节点
}
//释放树的空间
bitree FreeTree(bitree T) {
if( T ) {
FreeTree(T->left); //递归释放其左子树
FreeTree(T->right); //递归释放其右子树
free(T); //释放掉根节点
T = NULL; //释放掉指向根节点的指针，避免野指针
}
return T;
}
//计算一棵树的高度
int TreeHeight(bitree T) {
if( T == NULL ) //空树，返回0
return 0;
if( T->left == NULL && T->right == NULL ) //树根返回1
return 1;
return max(TreeHeight(T->left), TreeHeight(T->right)) + 1; //树的高度 = MAX(左子树的高度，右子树的高度) + 1;
}
int main() {
bitree root;
int height = 0;
root = CreateTree();
height = TreeHeight(root);
cout << "树的高度为:" << height << endl;
root = FreeTree(root);
if(root == NULL)
cout << "释放成功" << endl;
return 0;
}
