数据结构与算法：数据结构补充

遍历二叉树的递归算法先序遍历二叉树的递归算法
void PreOrderTraverse(BiTree T)
{
if (T){
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
中序遍历二叉树的递归算法
void InOrderTraverse(BiTree T)
{
if (T) {
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}
}
后序遍历二叉树的递归算法
void PostOrderTraverse(BiTree T)
{
if (T) {
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c",T->data);
}
}
非递归算法先序遍历：算法1，将右子树根结点 入栈，(栈所需最大容量为n/2+1)；算法2将根结点入栈
先序遍历的非递归算法1
void preorder(BiTree T)
{ SqStack S; BiTree P=T;
InitStack(S); Push(S,NULL);
while (P)
{ printf("%c",P->data);
if (P->rchild)
Push(S,P->rchild);
if (P->lchild)
P=P->lchild;
else Pop(S,P);
}
}
先序遍历的非递归算法2
void preorder(BiTree T){
int top=0;
BiTree stack[20],P=T;
do { while (P){
printf("%c",P->data);
stack[top]=P; top++;
P=P->lchild; }
if (top){
top--; P=stack[top];
P=P->rchild;}
}while (top || P);
}
中序遍历：在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈中弹出，访问，再遍历右子树中序遍历的非递归算法1
void inorder(BiTree T){
SqStack S; BiTree P=T;
InitStack(S);
do{ while(P){
* (S.top) = P; S.top++;
P=P->lchild; }
if (S.top){
S.top--; P=*(S.top);
printf("%c",P->data);
P=P->rchild;}
}while((S.top!=S.base) || P);
}
中序遍历的非递归算法2
void inorder(BiTree T)
{ SqStack S; BiTree P=T;
InitStack(S);
while( P || !Empty(S))
{ if (P) { Push(S,P);
P=P->lchild; }
else { Pop(S,P);
printf("%c",P->data);
P=P->rchild;}
}
}
后序非递归遍历时，每遇到一个结点，先把它推入栈中，让PopTim=0。在遍历其左子树前，改结点的PopTim=1，将其左孩子推入栈中。在遍历完左子树后，还不能访问该结点，必须继续遍历右子树，此时改结点的PopTim=2，并把其右孩子推入栈中。在遍历完右子树后，结点才退栈访问。
后序遍历的非递归算法1
void Postorder(BiTree T)
{ BiTree p=T,q=NULL;
SqStack S; InitStack(S); Push(S,p);
while (!StackEmpty(S))
{ if (p && p!=q) { Push(S,p); p=p->lchild; }
else { Pop(S,p);
if (!StackEmpty(S))
if (p->rchild && p->rchild!=q)
{ Push(S,p); p=p->rchild; }
else {printf("%c",p->data); q=p;}
}
}
}
后序遍历的非递归算法2
void postorder(BiTree T)
{BiTree P=T,q; int flag; SqStack S; InitStack(S);
do {
while (P){ *(S.top)=P;S.top++;P=P->lchild;}
q=NULL; flag=1;
while ((S.top!=S.base) && flag)
{ P=*(S.top-1);
if (P->rchild == q)
{ printf("%c",P->data); S.top--; q=p;}
else { P=P->rchild; flag=0;}
}
}while ((S.top!=S.base));
}
先序建立二叉树的递归算法
Status CreateBiTree(BiTree &T)
{ char ch; scanf("%c",&ch);
if (ch==' ') T=NULL;
else { if (!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
二叉树的显示输出
void PrintBiTree(BiTree T,int n)
{
int i; char ch=' ';
if (T) {
PrintBiTree(T->rchild,n+1);
for (i=1;i<=n;++i) {printf("%5c",ch);}
printf("%c\n",T->data);
PrintBiTree(T->lchild,n+1);
}
}
遍历二叉树的应用利用二叉树后序遍历计算二叉树的深度
int Depth(BiTree T){
int depl,depr;
if (T){
depl=Depth(T->lchild);
depr=Depth(T->rchild);
if (depl>=depr) return (depl+1);
else return (depr+1);
}
return 0;
}
求二叉树结点个数
int Size(BiTree T)
{
if (T==NULL) return 0;
else return 1 + Size (T->lchild ) + Size ( T->rchild);
}
说明：
1）遍历的第一个和最后一个结点第一个结点：
先序：根结点；
中序：沿着左链走，找到一个没有左孩子的结点；
后序：从根结点出发，沿着左链走，找到一个既没有左孩子又没有右孩子的结点。
最后一个结点：
中序：从根结点出发，沿着右链走，找到一个没有右孩子的结点；
后序：根结点。
先序：从根结点出发，沿着右链走，找到一个没有右孩子的结点；如果该结点有左孩子，再沿着其左孩子的右链走，以此类推，直到找到一个没有孩子的结点求中序的第一个结点的算法：
P=T;
while (P->lchild) P=P->lchild;
printf(P->data);
求中序的最后一个结点的算法：
P=T；
while(P->rchild) P=P->rchild;
Printf(P->data);
复制二叉树
void CopyTree(BiTree T,BiTree &T1)
{ if (T)
{ T1=(BiTree)malloc(sizeof(BiTNode));
if (!T1) { printf("Overflow\n"); exit(1); }
T1->data=T->data;
T1->lchild=T1->rchild=NULL;
CopyTree(T->lchild,T1->lchild);
CopyTree(T->rchild,T1->rchild);
}
}