二叉树创建及遍历算法(递归及非递归)
//二叉树处理头文件
//包括二叉树的结构定义,二叉树的创建,遍历算法(递归及非递归),
/*
 作者：成晓旭
 时间：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()<非递归算法>
 已知二叉树的前,中序遍历序列串,构造对应的二叉树
 <编程思想>:
  首先,在前序遍历序列中的首元素是二叉树的根节点,接着
 ,在中序遍历序列中找到此节点,那么在此节点以前的节点必为
 其左孩子节点,以后的必为其右孩子节点;
  然后,在中序遍历序列中,根节点的左子树和右子树再分别
 对应子树前序遍历序列的首字符确定子树的根节点,再由中序
 遍历序列中根节点的位置分别确定构成它们的左子树和右子树
 的节点;
  依次类推,确定二叉树的全部节点,构造出二叉树.
 参数描述：
  char *pre: 前序遍历序列
  char *mid: 中序遍历序列
  int n: 遍历序列中节点个数
 返回值:
  dCreateBranchTree3 = 新建二叉树的根节点指针
*/
BTNode *dCreateBranchTree3(char *pre,char *mid,int n)
{
 BTNode *p;
 char *t;
 int left;
 if(n<=0)
  return(NULL);
 p = (BTNode *)malloc(sizeof(BTNode));
 p->data = *pre;
 for(t=mid;t<mid+n;t++)