#include
#include
#include
#include
typedef char ElemType;
char Str[256]; //存放字符型二叉树
int Sk=1;
// 二叉树(二叉)链表的存储结构
typedef struct BiTNode
{
ElemType data; //叶子结点的值
struct BiTNode *Lchild; //左孩子链表指针
struct BiTNode *Rchild; //右孩子链表指针
bool Tag; //0:分支结点, 1:叶子结点
} *BiTree;
// 链栈(队列)类型
typedef struct SNode
{
struct BiTNode *tnode; //数据域
struct SNode *next; //指针域
int Level; //结点所在的层次
} *LinkStack;
// 构造一个带头结点的空链栈(队列)S
int StackInit(LinkStack &S)
{
S=(LinkStack) malloc(sizeof(SNode));
if(!S) return 0; //存储分配失败
S->next=NULL;
S->Level=1; //根结点的层序号
return 1;
}//StackInit
// 向链栈S的栈顶压入一个新的数据元素Tdata
int Push(LinkStack &S,BiTree Tdata)
{
LinkStack p=(LinkStack) malloc(sizeof(SNode));
if(!S) return 0;
p->tnode=Tdata;
p->next=S->next;
S->next=p;
return 1;
}//Push
// 弹出链栈S中的栈顶元素，并用Tdata返回
void Pop(LinkStack &S,BiTree &Tdata)
{
LinkStack p=S->next;
if(p)
{
S->next=p->next;
Tdata=p->tnode;
free(p);
}
else Tdata=NULL;
}//Pop
// 向链队列S插入新的数据元素Tdata和Tlevel
int Qinsert(LinkStack &S,BiTree Tdata,int Tlevel)
{
LinkStack p=(LinkStack) malloc(sizeof(SNode));
if(!p) return 0;
LinkStack q=S;
while(q->next) q=q->next;
p->tnode=Tdata;
p->Level=Tlevel;
q->next=p;
p->next=NULL;
return 1;
}//Qinsert
// 删除链队列S中的队首元素，并用Tdata和Tlevel返回
void Qdelete(LinkStack &S,BiTree &Tdata,int &Tlevel)
{
LinkStack p=S->next;
if(p)
{
S->next=p->next;
Tdata=p->tnode;
Tlevel=p->Level;
free(p);
}
else
{
Tdata=NULL;
Tlevel=0;
}
}//Pop
// 判断字符S1是否属于数据元素值域
int BiTreeElemTypeS(char S1)
{
if(isalpha(S1)||S1=='+'||S1=='-'||S1=='*'||S1=='/') return 1;
if(isdigit(S1)||S1==' '||S1=='^') return 1;
return 0;
}//BiTreeElemTypeS
// 判断两个运算符的大小：> 1，= 0，< -1
int InOperator(ElemType S1,ElemType S2)
{
if(S2=='*' || S2=='/') return 0;
if(S1=='*' || S1=='/') return 1;
if(S1=='+') return 0;
if(S1=='-' && S2=='+') return 0;
if(S1=='-') return 1;
if(S1=='(' && S2==')') return 0;
if(S1=='(' || S2=='(') return -1;
if(S1==')' && S2=='(') return 2;
if(S1==')' || S2==')') return 1;
return 2; //表示无效运算符
}//InOperator
// 去掉二叉树字符串中不符合要求的字符
void BiTreeString(char *St)
{
int j=0,k=0;
char ch=St[0];
while(ch && ch!=';')
{
if(ch=='('||ch==')'||ch==','||BiTreeElemTypeS(ch)==1)
{
St[k]=ch;
++k;
}
++j;
ch=St[j];
}
St[k]='\0';
j=k=0;
ch=St[0];
Str[0]=' ';
while(ch && ch!=';')
{
if(ch=='(' && St[j+1]==')') j+=2;
if(ch==',' && St[j+1]==')') ++j;
++k;
Str[k]=St[j];
++j;
ch=St[j];
}
Str[k+1]='\0';
}//BiTreeString
// 构造一个带头结点的空二叉树链表T
int BiTreeInit(BiTree &T)
{
T=(BiTree) malloc(sizeof(BiTNode));
if(!T) return 0;
T->Lchild=T->Rchild=NULL;
T->Tag=0;
return 1;
}//BiTreeInit
// 根据字符串型二叉树建立二叉树链表T的存储结构(递归算法)
void BiTreeCreate(BiTree &T)
{
BiTree p;
char ch=Str[Sk];
while(ch && ch!=';')
{
if(BiTreeElemTypeS(ch)==1)
{
BiTreeInit(p);
p->data=ch;
p->Tag=0;
if(Str[Sk-1]==',') T->Rchild=p;
else T->Lchild=p;
++Sk;
BiTreeCreate(p);
}
else if(ch=='(' && Str[Sk+1]==',') Sk+=2;
else if(ch==',' && Str[Sk+1]==')'||ch=='(') ++Sk;
else if(ch==')'||ch==',')
{
++Sk;
return;
}
ch=Str[Sk];
}
}//BiTreeCreate
// 根据层序输入建立二叉树链表T的存储结构(非递归算法)
// 输入结点值：无左或右孩子时输入空格，输入#或;结束
void BiTreeCreateL(BiTree Tl)
{
LinkStack S;
if(!StackInit(S)) return;
BiTree q,p=Tl;
char N; //存放结点值
int Lr=1,Ln=1,N1=1,Sk=1; //Lr左右标识 N1层号
printf("\nInput Root (Input #, Over.): ");
N=getche();
while(N!='#' && N!=';')
{
BiTreeInit(q);
q->data=N;
q->Tag=0;
if(Lr==1) p->Lchild=q;
if(Lr==2) p->Rchild=q;
if(Ln==Sk)
{
++N1;
printf("\nLevel %d:",N1);
Ln=0;
Sk*=2;
}
Qinsert(S,q,1);
Qinsert(S,q,2);
N=' ';
while(N==' ')
{
Qdelete(S,p,Lr);
++Ln;
if(Lr==1) N='L';
else N='R';
printf("\n %c.%c: ",p->data,N); N=getche();
}
}
free(S);
S->next=NULL;
}//BiTreeCreateL
//访问结点p的描述函数
void Visit(BiTree p)
{
printf("%c ",p->data);
}//Visit
// 根据二叉树链表输出字符串型二叉树T
void BiTreePrintS(BiTree T)
{
if(!T) return;
printf("%c",T->data);
if(T->Lchild)
{
printf("(");
BiTreePrintS(T->Lchild);
}
else
{
if(!T->Rchild) return;
else printf("(");
}
if(T->Rchild)
{
printf(",");
BiTreePrintS(T->Rchild);
printf(")");
}
while(!T->Rchild)
{
printf(")");
return;
}
}//BiTreePrintS
// 根据二叉树链表求二叉树T的深度(高度)
int BiTreeDepth(BiTree T)
{
if(!T) return 0;
int dep1=BiTreeDepth(T->Lchild);
int dep2=BiTreeDepth(T->Rchild);
if(dep2>dep1) dep1=dep2;
return dep1+1;
}//BiTreeDepth
// 根据字符串型二叉树求二叉树T的深度(高度)
int BiTreeDepthS(char *St)
{
char ch=St[1];
if(!BiTreeElemTypeS(ch)) return 0;
int i=0,j=0,k=1; //j记录"("的最大曾数
while(ch && ch!=';')
{
if(ch=='(')
{
++i;
if(i>j) j=i;
}
if(ch==')') --i;
++k;
ch=St[k];
}
return j+1;
}//BiTreeDepthS
// 将二叉树链表T中所有值为x的数据元素都替换为y
void BiTreeReplace(BiTree &T,ElemType x,ElemType y)
{
if(!T) return;
if(T->data==x) T->data=y;
if(T->Lchild) BiTreeReplace(T->Lchild,x,y);
else if(!T->Rchild) return;
if(T->Rchild) BiTreeReplace(T->Rchild,x,y);
while(!T->Rchild) return;
}//BiTreeReplace
// 求二叉树链表T中值为x的数据元素所在的层次
int BiTreeLevel(BiTree T,ElemType x)
{
if(!T) return 0;
if(T->data==x) return 1;
if(T->Lchild)
{
++Sk;
if(BiTreeLevel(T->Lchild,x)) return 1;
--Sk;
}
if(T->Rchild)
{
++Sk;
if(BiTreeLevel(T->Rchild,x)) return 1;
--Sk;
}
return 0;
}//BiTreeLevel
// 在二叉树T中查找数据元素x的递归算法(查找成功时返回该结点的指针)
BiTree BiTreeSearch(BiTree T, ElemType x)
{
if(!T) return NULL;
if(T->data==x) return T; //查找成功
BiTree p;
if(T->Lchild)
{
p=BiTreeSearch(T->Lchild,x);
if(p) return p;
}
if(T->Rchild)
{
p=BiTreeSearch(T->Rchild,x);
if(p) return p;
}
return NULL; //查找失败出口
}//BiTreeSearch
// 先序遍历二叉树T的递归算法
void PreOrder(BiTree T)
{
if(!T) return; //递归出口
Visit(T);
PreOrder(T->Lchild);
PreOrder(T->Rchild);
}//PreOrder
// 先序遍历二叉树T的非递归算法
void PreOrderS(BiTree T)
{
LinkStack S;
if(!StackInit(S)) return;
BiTree p=T->Lchild;
while(p)
{
while(p->Lchild)
{
Visit(p);
Push(S,p);
p=p->Lchild;
}
Visit(p);
while(p && !p->Rchild) Pop(S,p);
if(p && p->Rchild) p=p->Rchild;
}
}//PreOrderS
// 中序遍历二叉树T的递归算法
void InOrder(BiTree T)
{
if(!T) return;
InOrder(T->Lchild);
Visit(T);
InOrder(T->Rchild);
}//InOrder
// 中序遍历二叉树T的非递归算法
void InOrderS(BiTree T)
{
LinkStack S;
if(!StackInit(S)) return;
BiTree p=T->Lchild;
while(p)
{
while(p->Lchild)
{
Push(S,p);
p=p->Lchild;
}
Visit(p);
while(p && !p->Rchild)
{
Pop(S,p);
if(p) Visit(p);
}
if(p && p->Rchild) p=p->Rchild;
}
}//InOrderS
// 后序遍历二叉树T的递归算法
void PostOrder(BiTree T)
{
if(!T) return;
if(T->Lchild) PostOrder(T->Lchild);
if(T->Rchild) PostOrder(T->Rchild);
Visit(T);
}//PostOrder
// 后序遍历二叉树T的非递归算法
void PostOrderS(BiTree T)
{
LinkStack L;
if(!StackInit(L)) return;
LinkStack R;
if(!StackInit(R)) return;
BiTree q,p=T->Lchild;
while(p)
{
while(p->Lchild)
{
Push(L,p);
p=p->Lchild;
}
while(p && !p->Rchild)
{
Visit(p);
q=p;
while(R->next && R->next->tnode->Rchild==q)
{
Pop(R,q);
Visit(q);
}
Pop(L,p);
}
if(p && p->Rchild)
{
Push(R,p);
p=p->Rchild;
}
}
}//PostOrderS
// 层序遍历二叉树链表T的非递归算法
void LevelOrderS(BiTree T)
{
LinkStack S;
if(!StackInit(S)) return;
BiTree p=T->Lchild;
while(S && p)
{
Visit(p);
if(p->Lchild) Qinsert(S,p->Lchild,1);
if(p->Rchild) Qinsert(S,p->Rchild,2);
Qdelete(S,p,Sk); //Pop(S,p);
}
}//LevelOrderS
// 分层输出二叉树链表T的非递归算法
void BiTreeLevel(BiTree T)
{
LinkStack S;
if(!StackInit(S)) return;
int k=0,Ln=1; //Ln层次计数
BiTree p=T->Lchild;
while(S && p)
{
if(Ln!=k)
{
printf("\n");
k=Ln;
}
Visit(p);
if(p->Lchild) Qinsert(S,p->Lchild,k+1);
if(p->Rchild) Qinsert(S,p->Rchild,k+1);
Qdelete(S,p,Ln);
}
}//BiTreeLevel
// 先序后继线索化二叉树Tl的非递归算法
void PreOrderT(BiTree Tl)
{
LinkStack S;
if(!StackInit(S)) return;
BiTree p0,p=p0=Tl->Lchild;
while(p)
{
while(p->Lchild)
{
Push(S,p);
p=p->Lchild;
}
if(p->Rchild) p=p->Rchild;
else
{
while(p && !p->Rchild)
{
if(!p->Lchild) p0=p;
Pop(S,p);
}
if(p && p->Rchild)
{
p=p->Rchild;
if(!p0->Tag)
{
p0->Rchild=p;
p0->Tag=1;
}
}
}
}
}//PreOrderT
// 输出先序后继线索化二叉树Tl的数据元素值
void PreOrderPrint(BiTree Tl)
{
BiTree p=Tl->Lchild;
while(p)
{
Visit(p);
if(p->Lchild) p=p->Lchild;
else p=p->Rchild;
}
}//PreOrderPrint
void main()
{
char s0[]="A(B(D(,a),b),C(E(c,d),F(G(f),e)));";
BiTreeString(s0);
printf("\nStr= %s",s0);
BiTree p;
BiTreeInit(p);
BiTreeCreate(p);
printf("\n→T= ");
BiTreePrintS(p->Lchild);
printf("\n\nBiTreeDepth= %d",BiTreeDepth(p->Lchild));
printf("\nStringDepth= %d\n",BiTreeDepthS(Str));
BiTreeReplace(p,'e','s');
printf("\nReplace-T= ");
BiTreePrintS(p->Lchild);
Sk=0;
char s='d';
int k=BiTreeLevel(p->Lchild,s);
if (!k) printf("\n\nBiTreeLevel of %c is 0\n",s);
else printf("\n\nBiTreeLevel of %c is %d",s,Sk+1);
printf("\nElement %c at %d\n",s,BiTreeSearch(p,s));
printf("\nPre-T= ");
PreOrder(p->Lchild);
printf("\nPreST= ");
PreOrderS(p);
printf("\n\n In-T= ");
InOrder(p->Lchild);
printf("\nInS-T= ");
InOrderS(p);
printf("\n\nPost-T= ");
PostOrder(p->Lchild);
printf("\nPostST= ");
PostOrderS(p);
printf("\n\nLevel-T= ");
LevelOrderS(p);
Sk=BiTreeDepth(p->Lchild);
BiTreeLevel(p);
PreOrderT(p);
printf("\n\nPreThread= ");
PreOrderPrint(p);
printf("\n\n");
free(p);
} |
转播
