建立任意二叉树的二叉链表存储，并对其进行先序、中序、后序遍历，程序操作如下:
创新互联专注于凌源网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供凌源营销型网站建设，凌源网站制作、凌源网页设计、凌源网站官网定制、微信小程序开发服务，打造凌源网络公司原创品牌,更为您提供凌源网站排名全网营销落地服务。
#include "stdio.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 10 //栈的初始长度
#define STACKINCREMENT 5 //栈的追加长度
typedef struct bitree{
char data;
struct bitree *lchild,*rchild;
}bitree; //二叉树结点定义
typedef struct {
bitree **base;
bitree **top;
int stacksize;
}sqstack; // 链栈结点定义top栈顶 base栈底 且栈元素是指向二叉树结点的二级指针
//建立一个空栈
int initstack(sqstack *s)
{s-base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree)); //栈底指向开辟空间
if(!s-base) exit(1); //抛出异常
s-top=s-base; //栈顶=栈尾 表示栈空
s-stacksize=STACK_INIT_SIZE; //栈长度为开辟空间大小
return 1;
}
//进栈
int push(sqstack *s,bitree *e)
{if(s-top-s-base=s-stacksize) //如果栈满 追加开辟空间
{s-base=(bitree *)realloc (s-base,(s-stacksize+STACKINCREMENT)* sizeof(bitree));
if(!s-base) exit(1); //抛出异常
s-top=s-base+s-stacksize; //感觉这一句没用
s-stacksize+=STACKINCREMENT;}
*(s-top)=e;s-top++; //进栈 栈顶后移
return 1;
}
//出栈
int pop(sqstack *s,bitree **e)
{if(s-top==s-base) return 0; //栈空 返回0
--s-top;*e=*(s-top); //栈顶前移 取出栈顶元素给e
return 1;}
//取栈顶
int gettop(sqstack *s,bitree **e) //去栈顶元素 注意top指向的是栈顶的后一个
{if(s-top==s-base) return 0; //所以 s-top-1
*e=*(s-top-1);
return 1;
}
/*------------------------非递归-----先序建立二叉树----------------------------------*/
bitree *createprebitree()
{sqstack m;
initstack(m);
while(h||m.base!=m.top)
{if(h) {push(m,h);printf("%c",h-data);h=h-lchild;}
else{pop(m,h);
h=h-rchild;}
}
}
/*------------------------非递归-----中序输出二叉树----------------------------*/
void inordertraverse(bitree *h)
{sqstack m;
initstack(m);
while(h||m.base!=m.top)
{if(h) {push(m,h);h=h-lchild;}
else {
pop(m,h);
printf("%c",h-data);
h=h-rchild;
}
}
}
/*---------------------非递归----后序遍历二叉树----------------------------------*/
void postordertraverse(bitree *h)
{
sqstack m;
initstack(m);
while(h||m.base!=m.top)
{if(h) {
push(m,h);
h=h-lchild;}
else {
bitree *r; //使用r结点表示访问了右子树 代替标志域
gettop(m,h);
if(h-rchildh-rchild!=r)
{h=h-rchild;
push(m,h);
h=h-lchild;}
else{pop(m,h);
printf("%c",h-data);
r=h;h=NULL;}
}
}
二叉树建立方法：
一、我们要明确的一点是只有中序是无法创建二叉树的，它要结合先序，两者相联系才可以。
二、根据二叉树的图，得出先序的顺序是ABDECFG，而与此同时的中序DBEAFCG，根据这个建立。
三、然后就是要根据二叉树的原则编写代码，你要知道的是前序遍历序列中的首元素是二叉树的根节点。
四、然后你要做的是在中序遍历序列中找到这个节点，他是中间的分水岭，前面其左节点,后面是右节点。
五、最后要做的是建立根节点的左子树和右子树，再由中序 遍历序列中根节点的位置确定我们前面提到的子树的节点，这样二叉树就差不多建立完成了。
在二叉树中有一种平衡二叉树，通过平衡算法可以让二叉树两边的节点平均分布，这样就能让所有的索引查找都在一个近似的时间内完成。而MySQL这类数据库采用了二叉树的升级版B+Tree的形式，每个节点有三个支叶，不过其算法原理仍然是平衡树的原理。
重庆分公司
重庆分公司
