//main.c
#include "LinkBinTree.h" int main(int argc, char **argv) { //const char *str = "ABC##DE##F##G#H##"; BinTree tree; InitBinTree(&tree, '#'); CreateBinTree_input(&tree); //CreateBinTree_read(&tree, str); PreOrder(tree); InOrder(tree); PostOrder(tree); return 0; } //LinkBinTree.h #ifndef _LINKBINTREE_H_ #define _LINKBINTREE_H_ #include <stdio.h> #include <stdbool.h> #include <stdlib.h> //此处不能使用typedef去"定义"数据的类型,提供一个typedef会传递此数据结构支持多种类型的信息，而创建二叉树节点的函数，却明确指定以固定%x的方式去 //格式化存储输入，这种声明与实现的不一致可能会带来不必要的烦恼 //typedef char Element; 禁止！！！ //二叉树节点类型结构 typedef struct _BinTreeNode { char data; struct _BinTreeNode *leftChild; //左孩子 struct _BinTreeNode *rightChild; //右孩子 }BinTreeNode; //二叉树管理结构，flag参数用于标记空节点，当数据等于flag的值时，节点为空 typedef struct _BinTree { BinTreeNode *root; char flag; }BinTree; //初始化函数，用于初始化二叉树管理变量 void InitBinTree(BinTree *tree, char flag); //创建函数,以输入字符方式创建 void CreateBinTree_input(BinTree *tree); //提供接口的封装函数 //创建函数，以读取字符串方式。。。。。。。。。暂停！C语言灰色地带来啦！！！ //void CreateBinTree_read(BinTree *tree, const char *string); //递归方式遍历二叉树 //先序遍历，对于二叉树进行: 根节点->左子树->右子树 的方式遍历二叉树中每一个节点 void PreOrder(BinTree tree); //中序遍历，对于二叉树进行: 左子树->根节点->右子树 的方式遍历二叉树中每一个节点 void InOrder(BinTree tree); //后序遍历，对于二叉树进行: 左子树->右子树->根节点 的方式遍历二叉树中每一个节点 void PostOrder(BinTree tree); #endif // _LINKBINTREE_H_//LinkBinTree.c
#include "LinkBinTree.h" void InitBinTree(BinTree *tree, char flag) { tree->root = NULL; tree->flag = flag; } static void Create_1(BinTree *tree, BinTreeNode **node) //创建方式的先序的 { char item; if( 1 != scanf("%c", &item) || item == tree->flag ) //如果输入字符与空节点标记值相等，则将节点置NULL并立即返回 { *node = NULL; return ; } //输入值不为标记，创建节点并创建左右孩子 *node = (BinTreeNode *)malloc(sizeof(BinTreeNode)); if( NULL == *node ) { *node = NULL; return ; } (*node)->data = item; Create_1(tree, &(*node)->leftChild); Create_1(tree, &(*node)->rightChild); } static BinTreeNode *Create_2(BinTree *tree) { char item; if( 1 != scanf("%c", &item) || item == tree->flag ) return NULL; BinTreeNode * p = (BinTreeNode *)malloc(sizeof(BinTreeNode)); if( NULL == p ) return NULL; p->data = item; p->leftChild = Create_2(tree); p->rightChild = Create_2(tree); return p; } void CreateBinTree_input(BinTree *tree) { printf("请输入各节点元素，#表示该节点为空节点\n"); Create_1(tree, &(tree->root)); //tree->root = Create_2(tree); } /*标准C语言并没有定义前置递增或者递减返回的是值还是变量！！！！这导致代码的行为完全依赖于编译器！！！！！！ *经测试，VS下返回的是变量，QtCreator与gcc返回的则是一个值！也就是说这段代码本身不具有移植性，所以也可以 *人为这个实现代码是不正确的！ * 在C++语言中就明确规定了，前置返回变量引用，后置返回值 */ /* * 第三个参数不能是一维指针，在同一层栈帧里参数是一定的，用同一参数调用多少次同一函数输出都是一样的，所以需要二维指针"改变"每次调用函数传递的参数 static void Create_3(BinTree *tree, BinTreeNode **node, const char **p) { if( NULL == *p || '\0' == *p || tree->flag == **p ) //传递进来的是空指针、是个空串或是空节点标记 { *node = NULL; return ; } *node = (BinTreeNode *)malloc(sizeof(BinTreeNode)); //为指针赋值一个可用的堆空间 if( NULL == *node ) { return ; } (*node)->data = **p; //为数据域赋值字符串中的字符 Create_3(tree, &((*node)->leftChild), &(++(*p))); //用下一个字符创建左子树？？？？？灰色地带 Create_3(tree, &((*node)->rightChild), &(++(*p))); } void CreateBinTree_read(BinTree *tree, const char *string) { Create_3(tree, &(tree->root), &string); // tree->root = Create_4(tree, &string); } */ static void PreOrder_(const BinTreeNode *node) { if( NULL == node ) return ; printf("%c", node->data); PreOrder_(node->leftChild); PreOrder_(node->rightChild); } void PreOrder(BinTree tree) { PreOrder_(tree.root); printf("\n"); } static void InOrder_(const BinTreeNode *node) { if( NULL == node ) return ; InOrder_(node->leftChild); printf("%c", node->data); InOrder_(node->rightChild); } void InOrder(BinTree tree) { InOrder_(tree.root); printf("\n"); } static void PostOrder_(const BinTreeNode *node) { if( NULL == node ) return ; PostOrder_(node->leftChild); PostOrder_(node->rightChild); printf("%c", node->data); } void PostOrder(BinTree tree) { PostOrder_(tree.root); printf("\n"); }