//二叉樹處理頭文件
//包括二叉樹的結構定義,二叉樹的創建,遍歷算法(遞歸及非遞歸),
/*
作者：成曉旭
時間：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]);
}
}
//------------------------------非遞歸部分------------------------------
