非递归方式实现二叉树的创建与搜索，对于二叉树通常约定以前序遍历方式输入，若输入不正确是不会有什么显示的，这点要注意；
给出了C语言创建链表的俩种方式（不同于C++中引用传递）
一 创建二叉树方式：
方式一：输入指针
- void creatBT(BiTree *T)//建立一个二叉树
- {
- char ch;
- scanf("%c",&ch);//读入字符
- if(ch=='.')//.代表空子树
- *T = NULL;
- else
- {
- *T = (node *)malloc(sizeof(node));
- if(!T)
- {
- printf("开辟内存失败\n");
- exit(1);
- }
- (*T)->data = ch;//给T赋值
- creatBT(&(*T)->lchild);//给左子树赋值
- creatBT(&(*T)->rchild);//给右子树赋值
- }
- }
方式二：无参数传入，返回局部函数的指针地址
- BiTree creatBT()//建立一个二叉树
- {
- BiTree T;
- char ch;
- scanf("%c",&ch);//读入字符
- if(ch=='.')//.代表空子树
- T = NULL;
- else
- {
- T = (node *)malloc(sizeof(node));
- if(!T)
- {
- printf("开辟内存失败\n");
- exit(1);
- }
- T->data = ch;//给T赋值
- T->lchild = creatBT();//给左子树赋值
- T->rchild = creatBT();//给右子树赋值
- }
- return T;
- }
二 遍历代码（采取方式一的创建方式）
- #include <stdio.h>
- #include <stdlib.h>
- //定义二叉树的数据结构(递归方式)
- typedef struct node
- {
- char data;
- struct node *lchild;
- struct node *rchild;
- }node ,*BiTree;
- void creatBT(BiTree *T)//建立一个二叉树
- {
- char ch;
- scanf("%c",&ch);//读入字符
- if(ch=='.')//.代表空子树
- *T = NULL;
- else
- {
- *T = (node *)malloc(sizeof(node));
- if(!T)
- {
- printf("开辟内存失败\n");
- exit(1);
- }
- (*T)->data = ch;//给T赋值
- creatBT(&(*T)->lchild);//给左子树赋值
- creatBT(&(*T)->rchild);//给右子树赋值
- }
- }
- void pre_order(node *T)//前序遍历二叉树
- {
- if(T)
- {
- printf("%c ",T->data);
- pre_order(T->lchild);
- pre_order(T->rchild);
- }
- }
- void mid_order(node *T)//中序遍历
- {
- if(T)
- {
- mid_order(T->lchild);
- printf("%c ",T->data);
- mid_order(T->rchild);
- }
- }
- void back_order(node *T)
- {
- if(T)
- {
- back_order(T->lchild);
- back_order(T->rchild);
- printf("%c ",T->data);
- }
- }
- int main()
- {
- BiTree T = NULL;
- printf("请使用前序遍历的方式输入字符串，用.代替空值\n");
- creatBT(&T);//建立二叉树
- printf("建树成功\n");
- printf("\n前序遍历的结果是：\n");
- pre_order(T);
- printf("\n中序遍历的结果是：\n");
- mid_order(T);
- printf("\n后序遍历的结果是：\n");
- back_order(T);
- printf("\n");
- system("pause");
- return 0;
- }
若要采取方式二的创建方式main函数对应修改为
- int main()
- {
- BiTree T = NULL;
- printf("请使用前序遍历的方式输入字符串，用.代替空值\n");
- T = creatBT();//建立二叉树
- printf("建树成功\n");
- printf("\n前序遍历的结果是：\n");
- pre_order(T);
- printf("\n中序遍历的结果是：\n");
- mid_order(T);
- printf("\n后序遍历的结果是：\n");
- back_order(T);
- printf("\n");
- system("pause");
- return 0;
- }
结果一样的
小结：采用有参传入的时候由于在局部函数执行完后变量都会被释放，因此需要传入BiTree的指针，因而比较复杂，建议使用无参书传入，返回头节点，代码比较简洁容易理解
转载：http://blog.csdn.net/xsf50717/article/details/40019023
