두 갈래 나무 비귀속 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 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 데이터 구조 2차원 트리의 실현 코드일.두 갈래 트리 인터페이스 2 노드 클래스 3. 두 갈래 나무 구현 이 글을 통해 여러분께 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.