头文件:link_tree.h
#ifndef __LINK_TREE_H__
#define __LINK_TREE_H__
#include <stdio.h>
#include <stdlib.h>
typedef char datatype;//类型重定义
typedef struct tree_node
{datatype data;//数据域,存储数据struct tree_node *left;//存放链式二叉树左节点的指针struct tree_node *right;//存放链式二叉树右节点的指针
}tree_node,*node_p;
node_p create_tree();//创建链式二叉树
void show_first(node_p T);//先序遍历
void show_middle(node_p T);//中序遍历
void show_behind(node_p T);//后序遍历
void destroyTree(node_p T);//销毁链式二叉树
#endif
功能函数:link_tree.c
#include "link_tree.h"
//创建链式二叉树
node_p create_tree()
{datatype data;scanf("%c",&data);if(data == '#')//设定一个值来判断是不是要继续创建左右子树{return NULL;}//从堆区申请空间存放链表节点node_p T=(node_p)malloc(sizeof(tree_node));if(NULL == T){printf("链表节点创建失败!\n");return NULL;}T->data=data;//存放数据域T->left=create_tree();//递归创建左子树T->right=create_tree();//递归创建右子树return T;
}
//先序遍历(根->左->右)
void show_first(node_p T)
{if(NULL == T){return;}printf("%c ",T->data);//先输出根节点show_first(T->left);//递归输出左子树节点show_first(T->right);//递归输出右子树节点
}
//中序遍历(左->根->右)
void show_middle(node_p T)
{if(NULL == T){return;}show_middle(T->left);//递归输出左子树节点printf("%c ",T->data);//输出根节点show_middle(T->right);//递归输出右子树节点
}
//后序遍历(左->右->根)
void show_behind(node_p T)
{if(NULL == T){return;}show_middle(T->left);//递归输出左子树节点show_middle(T->right);//递归输出右子树节点printf("%c ",T->data);//输出根节点
}
//销毁二叉树
void destroyTree(node_p T){if (T == NULL) {return;}// 递归销毁左子树destroyTree(T->left);// 递归销毁右子树destroyTree(T->right);// 释放当前节点的内存free(T);
}
主函数:main.c
#include "link_tree.h"int main(int argc, const char *argv[])
{node_p T=create_tree();//创建二叉树show_first(T);//先序遍历printf("\n");show_middle(T);//中序遍历printf("\n");show_behind(T);//后序遍历printf("\n");destroyTree(T);//销毁二叉树return 0;
}