두 갈래 나무 비귀속 M

22330 단어 두 갈래 나무
  1 #include<stdio.h>

  2 #include<stdlib.h>

  3 #define Stack_Size 100

  4 #define StackIncrement 10

  5 #define OK 1

  6 #define TRUE 1

  7 #define FALSE 0

  8 #define ERROR 0

  9 #define OVERFLOW -2

 10 typedef int Status;

 11 typedef char TElemType;

 12 typedef struct BiTNode

 13 {

 14     TElemType data;

 15     BiTNode *lchild,*rchild; 

 16 }BiTNode,*BiTree; 

 17 typedef struct 

 18 {

 19     BiTree *base;

 20     BiTree *top;

 21     int stacksize;

 22 }SqStack;

 23 //

 24 Status InitStack(SqStack &S)

 25 {

 26     S.base=(BiTree *)malloc(Stack_Size*sizeof(BiTree));

 27     if(!S.base)  exit(OVERFLOW);

 28     S.top=S.base;

 29     S.stacksize=Stack_Size;

 30     return OK;

 31 }

 32 Status StackEmpty(SqStack &S)

 33 {

 34     if(S.top==S.base)

 35     return TRUE;

 36     return FALSE;

 37 }

 38 Status StackLength(SqStack S)

 39 {

 40     return (S.top-S.base);

 41 }

 42 Status GetTop(SqStack S,BiTree &e)

 43 {

 44     if(S.top==S.base)  return ERROR;

 45     e=*(S.top-1);

 46     return OK;

 47 }

 48 Status Push(SqStack &S,BiTree e)

 49 {

 50     if((S.top-S.base)==S.stacksize)

 51     {

 52     S.base=(BiTree *)realloc(S.base,(S.stacksize+StackIncrement)*sizeof(BiTree));

 53     if(!S.base)  exit(OVERFLOW);

 54     S.top=S.base+S.stacksize;

 55     S.stacksize+=StackIncrement;

 56     }

 57     *S.top++=e;

 58     return OK;

 59 }

 60 Status Pop(SqStack &S,BiTree &e)

 61 {

 62     if(S.top==S.base)  return ERROR;

 63     e=*--S.top;

 64     return OK;

 65 }

 66 Status PrintSqStack(SqStack S)

 67 {

 68     int i,length=StackLength(S);

 69     for(i=length-1;i>=0;i--)

 70     printf("%c",S.base[i]->data);

 71     putchar('
'); 72 return OK; 73 } 74 // 75 Status CreateBiTree(BiTree &T) 76 { 77 char ch; 78 ch=getchar(); 79 if(ch==' ') T=NULL; 80 else{ 81 if(!(T=new BiTNode)) exit(OVERFLOW); 82 T->data=ch; 83 CreateBiTree(T->lchild); 84 CreateBiTree(T->rchild); 85 } 86 return OK; 87 } 88 // 89 Status PreOrderTraverse(BiTree T) 90 { 91 SqStack S; 92 BiTree p; 93 InitStack(S); 94 p=T; 95 while(p||!StackEmpty(S)) 96 { 97 if(p) {printf("%c",p->data);Push(S,p);p=p->lchild;} 98 else 99 { 100 Pop(S,p); 101 p=p->rchild; 102 } 103 } 104 return OK; 105 } 106 Status InOrderTraverse(BiTree T) 107 { 108 SqStack S; 109 BiTree p; 110 InitStack(S); 111 p=T; 112 while(p||!StackEmpty(S)) 113 { 114 if(p) {Push(S,p);p=p->lchild;} 115 else 116 { 117 Pop(S,p); 118 printf("%c",p->data); 119 p=p->rchild; 120 } 121 } 122 return OK; 123 } 124 Status PostOrderTraverse(BiTree T) 125 { 126 SqStack S1,S2; 127 BiTree p; 128 InitStack(S1);InitStack(S2); 129 p=T; 130 while(p||!StackEmpty(S1)) 131 { 132 if(p) {Push(S2,p);Push(S1,p);p=p->rchild;} 133 else 134 { 135 Pop(S1,p); 136 p=p->lchild; 137 } 138 } 139 PrintSqStack(S2); 140 return OK; 141 } 142 // 143 Status CountLeaf(BiTree T) 144 { 145 int count=0; 146 if(T) 147 { 148 if((!T->lchild)&&(!T->rchild)) 149 count++; 150 count+=CountLeaf( T->lchild); 151 count+=CountLeaf( T->rchild); 152 } 153 return count; 154 } 155 Status Depth(BiTree T) 156 { 157 int depthval=0; 158 int depthLeft,depthRight; 159 if(!T) depthval = 0; 160 else 161 { 162 depthLeft = Depth( T->lchild ); 163 depthRight= Depth( T->rchild ); 164 depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight); 165 } 166 return depthval; 167 } 168 Status main() 169 { 170 BiTree T; 171 int count,depthval; 172 puts(" :"); 173 CreateBiTree(T); 174 puts(" :"); 175 PreOrderTraverse(T); 176 puts("
:
"); 177 InOrderTraverse(T); 178 puts("
:
"); 179 PostOrderTraverse(T); 180 count=CountLeaf(T); 181 printf(" :%d
",count); 182 depthval=Depth(T); 183 printf(" :%d
",depthval); 184 system("pause"); 185 return OK; 186 }

좋은 웹페이지 즐겨찾기