二叉树成立及遍历算法[VC/C++编程]

//二叉树处理头文件
//包含二叉树的构造定义,二叉树的成立,遍历算法(递归及非递归),
/*
　作者:成晓旭
　时间: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++)
　 if(*t==*pre) break;　 /*在中序遍历序列中查找根节点*/
　left = t - mid;　 /*左子树的节点个数*/
　p->lchild = dCreateBranchTree3(pre+1,t,left);
　p->rchild = dCreateBranchTree3(pre+1+left,t+1,n-1-left);
　return(p);
}
/*
　二叉树成立函数CreateBranchTree()<非递归算法>
　参数描写:
　 int array[]: 二叉树节点数据域数组
　 int n:　　 二叉树节点个数
　返回值:
　 CreateBranchTree = 新建二叉树的根节点指针
*/
BTNode *CreateBranchTree(int array[][2],int n)
{
　BTNode *head,*p;
　BTNode *NodeAddr[MAXNODE]; //节点地址暂时缓冲区
　int i,norder,rorder;
　head = NULL;
　printf("二叉树原始数据<新建次序>:\t");
　for(i=1;i<=n;i++)
　{
　 p = (BTNode *)malloc(sizeof(BTNode));
　 if(p==NULL)
　 {
　　 printf("\n新建节点时内存溢出!\n");
　　 return(NULL);
　 }
　 else
　 {
　　 p->data = array[i][0];
　　 p->lchild = p->rchild = NULL;
　　 norder = array[i][1];
　　 NodeAddr[norder] = p;
　　 if(norder>1)
　　 {
　　　 rorder = norder / 2; /*非根节点:挂接在自己的父节点上*/
　　　 if(norder % 2 == 0)
　　　　 NodeAddr[rorder]->lchild = p;
　　　 else
　　　　 NodeAddr[rorder]->rchild = p;
　　 }
　　 else
　　　 head = p; /*根节点*/
　　 if(SHOWCHAR)
　　　 printf("%c　　　 ",p->data);
　　 else
　　　 printf("%d　　　 ",p->data);
　 }
　}
　return(head);
}
//------------------------------递归部份------------------------------
/*
　二叉树前序遍历函数dpre_Order_Access()<递归算法>
　参数描写:
　 BTNode *head: 二叉树的根节点指针
*/
void dpre_Order_Access(BTNode *head)
{
　if(head!=NULL)
　{
　 if(SHOWCHAR)
　　 printf("%c　　　 ",head->data);
　 else
　　 printf("%d　　　 ",head->data);
　 dpre_Order_Access(head->lchild); /*递归遍历左子树*/
　 dpre_Order_Access(head->rchild); /*递归遍历右子树*/
　}
}
/*
　二叉树中序遍历函数dmid_Order_Access()<递归算法>
　参数描写:
　 BTNode *head: 二叉树的根节点指针
*/
void dmid_Order_Access(BTNode *head)
{
　if(head!=NULL)
　{
　 dmid_Order_Access(head->lchild); /*递归遍历左子树*/
　 if(SHOWCHAR)
　　 printf("%c　　　 ",head->data);
　 else
　　 printf("%d　　　 ",head->data);
　 dmid_Order_Access(head->rchild); /*递归遍历右子树*/
　}
}
/*
　二叉树后序遍历函数dlast_Order_Access()<递归算法>
　参数描写:
　 BTNode *head: 二叉树的根节点指针
*/
void dlast_Order_Access(BTNode *head)
{
　if(head!=NULL)
　{
　 dlast_Order_Access(head->lchild); /*递归遍历左子树*/
　 dlast_Order_Access(head->rchild); /*递归遍历右子树*/
　 if(SHOWCHAR)
　　 printf("%c　　　 ",head->data);
　 else
　　 printf("%d　　　 ",head->data);
　}
}
//------------------------------递归部份------------------------------
//------------------------------非递归部份------------------------------
/*
　二叉树前序遍历函数pre_Order_Access()<非递归算法>
　参数描写:
　 BTNode *head: 二叉树的根节点指针
*/
void pre_Order_Access(BTNode *head)
{
　BTNode *pt;
　ABTStack *ps,*top;
　pt = head;
　top = NULL;
　printf("\n二叉树的前序遍历后果<非递归>:\t");
　while(pt!=NULL ||top!=NULL)　 /*二叉树未遍历完,或仓库非空*/
　{
　 while(pt!=NULL)
　 {
　　 if(SHOWCHAR)
　　　 printf("%c　　　 ",pt->data);　 /*拜候根节点*/
　　 else
　　　 printf("%d　　　 ",pt->data);　 /*拜候根节点*/
　　 ps = (ABTStack *)malloc(sizeof(ABTStack));　 /*根节点进栈*/
　　 ps->ptree = pt;
　　 ps->link = top;
　　 top = ps;
　　 pt = pt->lchild; /*遍历节点右子树,经过的节点顺次进栈*/
　 }
　 if(top!=NULL)
　 {
　　 pt = top->ptree; /*栈顶节点出栈*/
　　 ps = top;
　　 top = top->link;
　　 free(ps); /*释放栈顶节点空间*/
　　 pt = pt->rchild; /*遍历节点右子树*/
　 }
　}
}
/*
　二叉树中序遍历函数mid_Order_Access()<非递归算法>
　参数描写:
　 BTNode *head: 二叉树的根节点指针
*/
void mid_Order_Access(BTNode *head)
{
　BTNode *pt;
　ABTStack *ps,*top;
　int counter =1;
　pt = head;
　top = NULL;
　printf("\n二叉树的中序遍历后果<非递归>:\t");
　while(pt!=NULL ||top!=NULL)　 /*二叉树未遍历完,或仓库非空*/
　{
　 while(pt!=NULL)
　 {
　　 ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
　　 ps->ptree = pt;
　　 ps->link = top;
　　 top = ps;
　　 pt = pt->lchild; /*遍历节点右子树,经过的节点顺次进栈*/
　 }
　 if(top!=NULL)
　 {
　　 pt = top->ptree; /*栈顶节点出栈*/
　　 ps = top;
　　 top = top->link;
　　 free(ps); /*释放栈顶节点空间*/
　　 if(SHOWCHAR)
　　　 printf("%c　　　 ",pt->data); /*拜候根节点*/
　　 else
　　　 printf("%d　　　 ",pt->data); /*拜候根节点*/
　　 pt = pt->rchild; /*遍历节点右子树*/
　 }
　}
}
/*
　二叉树后序遍历函数last_Order_Access()<非递归算法>
　参数描写:
　 BTNode *head: 二叉树的根节点指针
*/
void last_Order_Access(BTNode *head)
{
　BTNode *pt;
　ABTStack *ps,*top;
　int counter =1;
　pt = head;
　top = NULL;
　printf("\n二叉树的后序遍历后果<非递归>:\t");
　while(pt!=NULL ||top!=NULL)　 /*二叉树未遍历完,或仓库非空*/
　{
　 while(pt!=NULL)
　 {
　　 ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
　　 ps->ptree = pt;
　　 ps->link = top;
　　 top = ps;
　　 pt = pt->lchild; /*遍历节点右子树,经过的节点顺次进栈*/
　 }
　 if(top!=NULL)
　 {
　　 pt = top->ptree; /*栈顶节点出栈*/
　　 ps = top;
　　 top = top->link;
　　 free(ps); /*释放栈顶节点空间*/
　　 printf("%c　　　 ",pt->data); /*拜候根节点*/
　　 pt = pt->rchild; /*遍历节点右子树*/
　 }
　}
}
/*
　二叉查找树静态查找函数static_Search_STree()<非递归算法>
　参数描写:
　 BTNode *head: 二叉查找树的根节点指针
　 int key:　 查找关键码
　返回值:
　 static_Search_STree = 键值为key的节点指针(找到)
　 static_Search_STree = NULL(没有找到)
*/
BTNode *static_Search_STree(BTNode *head,int key)
{
　while(head!=NULL)
　{
　 if(head->data == key)
　 {
　　 printf("\n数据域=%d\t地址=%d\t\n",head->data,head);
　　 return(head); /*找到*/
　 }
　 if(head->data > key)
　　 head = head->lchild; /*持续沿左子树搜索*/
　 else
　　 head = head->rchild; /*持续沿右子树搜索*/
　}
　return(NULL); /*没有查找*/
}
/*
　二叉查找树动态查找函数dynamic_Search_STree()<非递归算法>
　参数描写:
　 BTNode *head:　 二叉查找树的根节点指针
　 BTNode **parent: 键值为key的节点的父节点指针的指针
　 BTNode **head:　 键值为key的节点指针的指针(找到)或NULL(没有找到)
　 int key:　　 查找关键码
　注意:
　 *parent == NULL 且 *p == NULL 没有找到(二叉树为空)
　 *parent == NULL 且 *p != NULL 找到(找到根节点)
　 *parent != NULL 且 *p == NULL 没有找到(叶节点)<可在parent后插入节点>
　 *parent != NULL 且 *p != NULL 找到(中间层节点)
*/
void dynamic_Search_STree(BTNode *head,BTNode **parent,BTNode **p,int key)
{
　*parent = NULL;
　*p = head;
　while(*p!=NULL)
　{
　 if((*p)->data == key)
　　 return; /*找到*/
　 *parent = *p; /*以当前节点为父,持续查找*/
　 if((*p)->data > key)
　　 *p = (*p)->lchild; /*持续沿左子树搜索*/
　 else
　　 *p = (*p)->rchild; /*持续沿右子树搜索*/
　}
}
/*
　二叉查找树插入节点函数Insert_Node_STree()<非递归算法>
　参数描写:
　 BTNode *head: 二叉查找树的根节点指针
　 int key:　 查找关键码
　返回值:
　 Insert_Node_STree = 1 插入成功
　 Insert_Node_STree = 0 插入失利(节点已经存在)
*/
int Insert_Node_STree(BTNode *head,int key)
{
　BTNode *p,*q,*nnode;
　dynamic_Search_STree(head,&p,&q,key);
　if(q!=NULL)
　 return(0);　 /*节点在树中已经存在*/
　nnode = (BTNode *)malloc(sizeof(BTNode)); /*新建节点*/
　nnode->data = key;
　nnode->lchild = nnode->rchild = NULL;
　if(p==NULL)
　 head = p; /*原树为空,新建节点为查找树*/
　else
　{
　 if(p->data > key)
　　 p->lchild = nnode; /*作为左孩子节点*/
　 else
　　 p->rchild = nnode; /*作为右孩子节点*/
　}
　return(1); /*插入成功*/
}
/*
　二叉查找树插入一批节点函数Insert_Batch_Node_STree()<非递归算法>
　参数描写:
　 BTNode *head: 二叉查找树的根节点指针
　 int array[]: 被插入的数据域数组
　 int n:　　 被插入的节点数目
*/
void Insert_Batch_Node_STree(BTNode *head,int array[],int n)
{
　int i;
　for(i=0;i<n;i++)
　{
　 if(!Insert_Node_STree(head,array[i]))
　　 printf("\n插入失利<键值为%d的节点已经存在>!\n",array[i]);
　}
}
//------------------------------非递归部份------------------------------