};
bool StackInit(SStack &S) { //初始化栈，即构造空栈
S.base=new SElemType[StackInitSize];
if (!S.base) return false;
S.top=S.base; S.stacksize=StackInitSize; return true;
SElemType data; SNode *next; //相当于线性表的prior
} *LStack;
void StackInit(LStack &S) { S=NULL;}
链栈的入栈
void Push(LStack &S,SElemType e) {
LStack q;
q=new SNode; q->data=e; q->next=S; S=q;
cout << ',';
PreOrderLists( T->rchild, visit );
cout << ')';
}
}
else
cout << '#';
}
先序遍历二叉树
void preorder(BiTree T,void visit(ElemType))
{
if(!T)
return ;
visit (T->data);
{
Queue q;
Tree x,y;
if(!T)
return;
QueueInit(q);
Enqueue(q,T);
while(Dequeue(q,x))
{
visit(x->data)
for(y=x->firstchild;y;y=y->nextsibling)
Enqueue(q,y);
}
}
先序遍历输出二叉树
&&MirrorSimilar(t1->rchild,t2->lchild);
}
广度优先搜索遍历
Viod BFSTraverse(ALGraph &G,void ,void visit(VexType))
{
int i,j,k;
ArcPtr p;
Queue q;
for(i=1;i<=G.Vexnum;i++)
preorder(T->lchild, visit);
preorder(T->rchild, visit);
}
判断两个二叉树是否相似
bool Similar( BiTree T1, BiTree T2 )
{
if( !T1 && !T2 )
return true;
if( !T1 || !T2 )
return false;
void PreOrderLists( BiTree T, void visit( TElemType ) )
{
if( T )
{
visit( T->data );
if( T->lchild || T->rchild )
{
cout << '(';
PreOrderLists( T->lchild, visit );
}
}Байду номын сангаас
}
链栈的出栈
bool Pop(LStack &S, SElemType &e) {
LStack q;
if (!S) return false;
e=S->data; q=S; S=S->next;
delete q; return true;
}
层序遍历树
Void TreeLevelOrder(tree T,void visit(TelemType))
{
k=p->adjvex;
if(!G.Vexs[k].visited)
{
visit(G>Vexs[k].data);
G.Vexs[k].visited=true;
Enqueue(q.k);
}
}
}
}
深度优先搜索遍历
void DFS(ALGraph &G, int i, void visit(VexType))
(S.stacksize+StackInc)*sizeof(SElemType));
if (!newbase) return false;
S.base=newbase; S.top=S.base+S.stacksize;
S.stacksize+=StackInc;
}
*S.top=e; S.top++; return true;
G.Vexs[i].visited=false;
for(i=1;i<=G.Vexnum;i++)
if(!G.vex[i].visited)
{
visit(G.Vexs[i].data);
G.Vexs[i].visited=true;
Enqueue(q,i);
while(Dequeue(q,j))
for(p=G.Vexs[j].firstarc;p;p=p->nextarc)
循环队链的出队
bool Dequeue( CSQueue &q, QElemType &e )
{
int front;
if( q.length == 0 )
return false;
front = ( q.rear + 1 - q.length + MAXQSIZE ) % MAXQSIZE;
e = q.elem[ front ];
q.length --;
return true;
}
循环队链的入队
bool Enqueue( CSQueue &q, QElemType e )
{
if( q.length == MAXQSIZE )
return false;
q.rear = ( q.rear + 1 ) % MAXQSIZE;
q.elem[ q.rear ] = e;
T->rchild = p;
Swap( T->rchild );
Swap( T->lchild );
}
二叉树的深度
int depth( BiTree T )
{
if( !T )
return 0;
int dl, dr;
dl = depth( T->lchild );
dr = depth( T->rchild );
delete p;
return true;
}
顺序栈的类型定义与基本操作：
const StackInitSize=100;
const StackInc=10;
struct SStack {
SElemType *base,*top; //栈底指针,栈顶指针
int stacksize; //当前分配的存储空间
return dl > dr? dl+1:dr+1;
}
计算树的深度
int TreeDepth( tree T )
{
if( !T )
return 0;
int d = 1;
tree p;
int depth = 1;
for( p = T->firstchild; p; p = p->nextsibling )
{ int j;
Arcptr p;
visit(G.Vexc[i].data);
G.Vexs[i].visited=true;
for(p=G.Vexs[i].firstarc ;p; p=p->nextarc)
{
J=p->adjvex;
if(!G.Vex[j].visited)
DFS(G,j,visit);
{
int i = -1;
CreateBiTree( T, s, i );
}
判断二叉树是否镜像相似
bool MirrorSimilar(BiTree t1,Bitree t2)
{
return (!t1&&!t2)||t1&&t2&&MirrorSimilar(t1->lchild,t2->rchild)
{
d = d + TreeDepth( p );
if( d > depth )
depth = d;
d = 1;
}
if( d >depth )
depth = d;
return depth;
}
构造二叉树
void CreateBiTree( BiTree &T, TElemType s[], int &i )
}
链队的出队
bool Dequeue( LQueue &q, QElemType &e )
{
LQueuePtr p;
if( q.rear->next == q.rear )
return false;
p = q.rear->next;
e = p->next->data;
q.rear->next = p->next;
{
i++;
if( s[i] =='#' )