//sstack.h /*顺序堆栈的实现*/ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define NULL 0 #define INFEASIBLE -1 #define OVERFLOW -2 #include <stdio.h> #include <stdlib.h> //#include "bitree.h" #define STACK_INIT_SIZE 10 /*存储空间初始分配量*/ #define STACKINCREMENT 5 /*存储空间分配增量*/ typedef int Status; typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; /*左右孩子指针*/ }BiTNode ,*BiTree; typedef BiTNode ElemType; typedef struct SqStack { ElemType *base; /*在栈构造之前和销毁之后，base的值为NULL*/ ElemType *top ; /*栈顶指针*/ int stacksize; /*当前已分配的存储空间，以元素为单位*/ }SqStack,*SS;
/*构造一个空栈*/ Status InitStack(SqStack &S) { S.base=(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(! S.base) exit(OVERFLOW); /*存储分配失败*/ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } Status PrintStack(SqStack S) { ElemType *i; int j=0; printf("i element value"); for(i=S.base;i<S.top;) printf("\n%d %d",j++,*(i++)); return OK; }
/*若栈不空，则e返回S的栈顶元素，并返回OK；否则返回ERROR*/ Status GetTop(SqStack S,ElemType &e) { if(S.top==S.base) return ERROR; e= *(S.top-1); return OK; } /*插入元素e为新的栈顶元素*/ Status Push(SqStack &S,ElemType e) { if(S.top-S.base>=S.stacksize) /*栈满，追加存储空间*/ { S.base=(ElemType *) realloc(S.base,(S.stacksize+STACKINCREMENT) *sizeof(ElemType)); if(! S.base) exit(OVERFLOW); /*存储分配失败*/ S.top=S.base+S.stacksize; S.stacksize +=STACKINCREMENT; } *S.top++=e; return OK; } /*若栈不空，则删除S的栈顶元素，用e返回其值，并返回*/ Status Pop(SqStack &S,ElemType &e) { if (S.top==S.base) return ERROR; e=* --S.top; return OK; }
/*返回S的元素个数，即栈的长度*/ Status StackLength(SqStack S,int &e) { e=S.top-S.base; return OK; } /*显示S中第i元素的值*/ ElemType StackValue(SqStack S,int i) { return (*(S.base+i-1)); }
Status StackEmpty(SqStack S) { return S.top==S.base; } //bitree.h /*函数结果状态代码*/ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #include <stdio.h> #include <stdlib.h> #include "sstack.h"
typedef int Status; /*Status 是函数的类型，其值是函数结果状态代码*/ /*----二叉树的二叉链表存储表示----*/
SqStack S; BiTree CreateBiTree( BiTree R) { /*按先序次序输入二叉树中的结点的值（一个字符），空格字符表示空树， 构造二叉链表表示的二叉树R。*/ TElemType Nodedata; scanf("%c",&Nodedata); if (Nodedata=='$') R=NULL; else { if(!(R=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); R->data=Nodedata; R->lchild=CreateBiTree(R->lchild); R->rchild=CreateBiTree(R->rchild); } return (R); } Status PreOrderTraverse( BiTree T,Status (*Visit)(TElemType e)) { /*采用二叉链表存储结构，Visit是对结点操作的应用函数。 先序遍历二叉树T的递归算法，对每个结点调用函数Visit一次且一次。 一旦Visit()访问失败，则操作失败。*/ if(T) { if(Visit(T->data)) if(PreOrderTraverse(T->lchild,Visit)) if(PreOrderTraverse(T->rchild,Visit)) return OK; return ERROR; } else return OK;
}
Status InOrderTraverse( BiTree T,Status (*Visit)(TElemType e)) /*采用二叉链表存储结构，Visit是对结点操作的应用函数。 中序遍历二叉树T，对每个结点调用函数Visit一次且一次。 一旦Visit()访问失败，则操作失败。*/ { if(T) { if(InOrderTraverse(T->lchild,Visit)) if(Visit(T->data)) if(InOrderTraverse(T->rchild,Visit)) return OK; return ERROR; } else return OK; } Status PostOrderTraverse( BiTree T,Status (*Visit)(TElemType e)) /*采用二叉链表存储结构，Visit是对结点操作的应用函数。 后序遍历二叉树T，对每个结点调用函数Visit一次且一次。 一旦Visit()访问失败，则操作失败。*/ { if(T) { if(PostOrderTraverse(T->lchild,Visit)) if(PostOrderTraverse(T->rchild,Visit)) if(Visit(T->data)) return OK; return ERROR; } else return OK; }
Status LevelOrderTraverse( BiTree T,Status (*Visit)(TElemType e)) { /*采用二叉链表存储结构，Visit是对结点操作的应用函数。 层序遍历二叉树T，对每个结点调用函数Visit一次且一次。 一旦Visit()访问失败，则操作失败。*/ BiTree Qu[100]; int front,rear; front=1;rear=1; Qu[1]=T;rear++; while(front<rear && Qu[front]) { Visit(Qu[front]->data); if(Qu[front]->lchild) { Qu[rear++]=Qu[front]->lchild;} if(Qu[front]->rchild) { Qu[rear++]=Qu[front]->rchild;} front++; } return OK; } Status PrintElement(TElemType e) { printf("%5c ",e); return OK; } // //打印一个空格 void IndentBlanks(int num) { int i; for( i = 0;i < num; i++) printf(" "); }
Status PrintRNL(BiTree T,int level ) { //char *buffer; if(T) { PrintRNL(T->rchild,level+1); printf("\n"); IndentBlanks(level*6); printf("%c",T->data); PrintRNL(T->lchild,level+1); } return OK; }
void CountLeaf (BiTree T, int &count) { // use posorder descent if (T != NULL) { CountLeaf(T->lchild, count); // descend left CountLeaf(T->rchild, count); // descend right
// check if t is a leaf node (no descendants) // if so increment the variable count if (T->lchild == NULL && T->rchild == NULL) count++; } } void CountLink (BiTree T, int &count) { if (T != NULL) { if(T->lchild) CountLink(T->lchild, ++count); if(T->rchild) CountLink(T->rchild, ++count); }
} void CountLL (BiTree T, int &leaf,int &link1,int &link2) { if(T) { if(T->lchild && T->rchild) ++link2; else if(T->lchild && !T->rchild) ++link1; else if(T->rchild && !T->lchild) ++link1; else ++leaf; CountLL(T->lchild,leaf,link1,link2); CountLL(T->rchild,leaf,link1,link2); } }
int Depth (BiTree T) { int depthLeft, depthRight, depthval;
if (T == NULL) depthval = 0; else { depthLeft= Depth(T->lchild); depthRight= Depth(T->rchild); depthval = 1 + (depthLeft> depthRight?depthLeft:depthRight); } return depthval; }
Status InOrderTraverseF(BiTree T,Status(*Visit)(TElemType e)) { BiTNode p;//定义数据ElemType为结点 InitStack(S); p=*T; //如果结点的左域非空，结点进栈 while(p.lchild) { Push(S,p); p=*p.lchild; } while(&p) { Visit(p.data); //访问结点 if (p.rchild != NULL) { //当前结点置为右结点 p=*p.rchild; //如果结点的左域非空，结点进栈 while(p.lchild) { Push(S,p); p=*p.lchild; } } else if (!StackEmpty(S)) // move up the tree Pop(S,p); else return OK; } return OK;
}
Status PreOrderTraverseF( BiTree T,Status (*Visit)(TElemType e)) {
BiTNode p;//定义数据ElemType为结点 InitStack(S); p=*T; while(&p) { Visit(p.data); //访问结点 if(p.rchild) //右结点入栈 Push(S,*p.rchild); if (p.lchild != NULL) { //当前结点置为左结点 p=*p.lchild; } else if (!StackEmpty(S)) // move up the tree Pop(S,p); else return OK; } } Status PostOrderTraverseF( BiTree T,Status (*Visit)(TElemType e)) { BiTNode p;//定义数据ElemType为结点 int i=0; InitStack(S); p=*T; //如果结点的左域非空，结点进栈 while(p.lchild) { Push(S,p); p=*p.lchild; } Push(S,p); while(!StackEmpty(S)) { if (p.rchild != NULL && i!=1) { //当前结点置为右结点 p=*p.rchild; //如果结点的左域非空，结点进栈 while(p.lchild) { Push(S,p); p=*p.lchild; } Push(S,p); i=0; } else { Pop(S,p); i=0; Visit(p.data); } if (!StackEmpty(S)) // move up the tree { GetTop(S,p); i=1; } } return OK; }
//main() #include <stdio.h> #include <stdlib.h> #include "bitree.h" void main(void ) { BiTree T; int i,j,k; //BiTree PrintElement(TElemType e); int choice; while (1) { printf("\n 1. 建立一棵二叉树"); printf("\n 2. 先序遍历二叉树"); printf("\n 3. 中序遍历二叉树"); printf("\n 4. 后序遍历二叉树"); printf("\n 5. 层序遍历二叉树"); printf("\n 6. 计算二叉树的叶子数"); printf("\n 7. 计算二叉树的非空链域数"); printf("\n 8. 打印二叉树"); printf("\n 9. 二叉树的深度"); printf("\n 10. 二叉树的叶子、度为1、度为2的数量"); printf("\n 11. 退出"); printf("\n 请选择:"); scanf("%d",&choice); switch(choice){ case 1: printf("\n按先序遍历顺序建立一棵二叉树"); printf("\n顶点值为字符型,输入时$表示子树空:"); getchar(); T=CreateBiTree(T); //getchar(); break; case 2: printf("\n先序遍历二叉树"); PreOrderTraverseF(T,PrintElement); break; case 3: printf("\n中序遍历二叉树"); InOrderTraverseF(T,PrintElement); break; case 4: printf("\n后序遍历二叉树"); PostOrderTraverseF(T,PrintElement); break; case 5: printf("\n层序遍历二叉树"); LevelOrderTraverse(T,PrintElement); break; case 6: i=0; CountLeaf(T,i); printf("\n二叉树的叶子数为：%d",i); break; case 7: i=0; CountLink(T,i); printf("\n二叉树的非空链域数为：%d",i); break;
case 8: i=1; printf("\n二叉树"); PrintRNL(T,i); break; case 9: i=0; printf("\n二叉树的深度: %d",Depth(T)); break; case 10: i=j=k=0; CountLL(T,i,j,k); printf("\n二叉树的叶子数：%d\n度为1的结点数: %d\n度为2的结点数：%d",i,j,k); break; case 11: exit(0); default: break; } } }
