读书人
栏目▼

二叉树创建及遍历算法(递归及非递归),

发布时间： 2012-02-20 21:18:23 作者： rapoo

二叉树创建及遍历算法(递归及非递归)
//二叉树处理头文件
//包括二叉树的结构定义,二叉树的创建,遍历算法(递归及非递归),
/*
作者：成晓旭
时间：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()<非递归算法>

[解决办法]
不会，学习！
[解决办法]

C/C++ code
#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; /*遍历节点右子树*/   }  } }
读书人网 >.NET

热点推荐

触屏版 | 电脑版

读书人网 m.reader8.net