二叉树创建及遍历算法

//二叉树处理头文件
//包括二叉树的结构定义,二叉树的创建,遍历算法(递归及非递归),
/*
　作者：成晓旭
　时间：2001年10月7日(18:49:38-20:00:00)
　内容：完成二叉树创建,二叉树的前,中,后序遍历(递归)
　时间：2001年10月7日(21:09:38-22:09:00)
　内容：完成二叉树的前,中序遍历(非递归)
　时间：2001年10月8日(10:09:38-11:29:00)
　内容：完成查找二叉树的静,动态查找(非递归)
*/
#include "stdlib.h"

#define MAXNODE 20
#define ISIZE 8
#define NSIZE0 7
#define NSIZE1 8
#define NSIZE2 15
//SHOWCHAR = 1(显示字符) SHOWCHAR = 0(显示数字)
#define SHOWCHAR 1
//二叉树结构体
struct BTNode
{
　int data;
　BTNode *rchild;
　BTNode *lchild;
};
//非递归二叉树遍堆栈
struct ABTStack
{
　BTNode *ptree;
　ABTStack *link;
};
char TreeNodeS[NSIZE0] = {''A'',''B'',''C'',''D'',''E'',''F'',''G''};
char PreNode[NSIZE0] = {''A'',''B'',''D'',''E'',''C'',''F'',''G''};
char MidNode[NSIZE0] = {''D'',''B'',''E'',''A'',''C'',''G'',''F''};
int TreeNodeN0[NSIZE1][2] = {{0,0},{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7}};
int TreeNodeN1[NSIZE1][2] = {{0,0},{4,1},{2,2},{6,3},{1,4},{3,5},{5,6},{7,7}};
int TreeNode0[NSIZE1][2] = {{''0'',0},{''D'',1},{''B'',2},{''F'',3},{''A'',4},{''C'',5},{''E'',6},{''G'',7}};
int TreeNode1[NSIZE1][2] = {{''0'',0},{''A'',1},{''B'',2},{''C'',3},{''D'',4},{''E'',5},{''F'',6},{''G'',7}};
int TreeNode2[NSIZE2][2] = {{''0'',0},{''A'',1},{''B'',2},{''C'',3},{''D'',4},{''E'',5},{''F'',6},{''G'',7},{''H'',8},{''I'',9},{''J'',10},{''K'',11},{''L'',12},{''M'',13},{''N'',14}};
int InsertNode[ISIZE] = {-10,-8,-5,-1,0,12,14,16};
//char *prestr = "ABDECFG";
//char *midstr = "DBEACGF";
/*
　二叉树创建函数dCreateBranchTree1()<递归算法>
　参数描述：
　 int array[]: 二叉树节点数据域数组
　 int i:　　 当前节点的序号
　 int n:　　 二叉树节点个数
　返回值:
　 dCreateBranchTree1 = 新建二叉树的根节点指针
　备注:
　 根节点 = array[(i+j)/2];
　 左子节点 = [array[i],array[(i+j)2-1]]
　 右子节点 = [array[(i+j)/2+1,array[j]]
*/
BTNode *dCreateBranchTree1(char array[],int i,int n)
{
　BTNode *p; /*二叉树节点*/
　if(i>=n)
　 return(NULL);
　p = (BTNode *)malloc(sizeof(BTNode));
　p->data = array[i];
　p->lchild = dCreateBranchTree1(array,2*i+1,n);
　p->rchild = dCreateBranchTree1(array,2*i+2,n);
　return(p);
}
/*
　二叉树创建函数dCreateBranchTree2()<递归算法>
　参数描述：
　 int array[]: 二叉树节点数据域数组
　 int i:　　 当前节点的序号
　 int n:　　 二叉树节点个数
　返回值:
　 dCreateBranchTree2 = 新建二叉树的根节点指针
　备注:
　 根节点 = array[(i+j)/2];
　 左子节点 = [array[i],array[(i+j)2-1]]
　 右子节点 = [array[(i+j)/2+1,array[j]]
*/
BTNode *dCreateBranchTree2(char array[],int i,int j)
{
　BTNode *p; /*二叉树节点*/
　if(i>j)
　 return(NULL);
　p = (BTNode *)malloc(sizeof(BTNode));
　p->data = array[(i+j)/2];
　p->lchild = dCreateBranchTree2(array,i,(i+j)/2-1);
　p->rchild = dCreateBranchTree2(array,(i+j)/2+1,j);
　return(p);
}
/*
　二叉树创建函数dCreateBranchTree3()<非递归算法>
　已知二叉树的前,中序遍历序列串,构造对应的二叉树
　

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!