두 갈래 나무, 귀속, 비귀속 두루 다니며 깊이를 구하고 잎 노드를 출력한다

4302 단어
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
#define ElemType char// 

#define STACK_INIT_SIZE 100
#define _br_ printf("
") typedef char TElemType; /* * \param * \author Silent_Amour */ typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; typedef struct { BiTree *base; BiTree *top; int Size; } Stack; int initStack(Stack &S) { S.base = (BiTree *)malloc(STACK_INIT_SIZE*sizeof(BiTree)); if (!S.base)exit(-1); S.top = S.base; S.Size = STACK_INIT_SIZE; return 1; } int StackPop(Stack &S, BiTree &e) { if (!S.top || S.top == S.base) return -1; e = *--S.top; // printf(" %d,%d
", S.top, e); return 1; } int StackPush(Stack &S, BiTree e) { if (S.top-S.base>= S.Size) exit(-1); *S.top++ = e; // printf(" %d, :%d
", S.top, e); return 1; } int DisplayElem(TElemType e) { printf("%c ", e); return 1; } int creatBiTree(BiTree &T) { char ch; ch=getchar(); if (ch == '.') T = NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) exit(-1); T->data = ch; creatBiTree(T->lchild); creatBiTree(T->rchild); } return 1; } int PreOrderTraverse(BiTree T, int(*DisplayElem)(TElemType e)) { if (T) { if (DisplayElem(T->data)) if (PreOrderTraverse(T->lchild, DisplayElem)) if (PreOrderTraverse(T->rchild, DisplayElem)) return 1; return -1; } else return 1; } int InOrderTraverse(BiTree T, int(*DisplayElem)(TElemType e)) { if (T) { if (InOrderTraverse(T->lchild, DisplayElem)) if (DisplayElem(T->data)) if (InOrderTraverse(T->rchild, DisplayElem)) return 1; return -1; } else return 1; } int PostOrderTraverse(BiTree T, int(*DisplayElem)(TElemType e)) { if (T) { if (PostOrderTraverse(T->lchild, DisplayElem)) if (PostOrderTraverse(T->rchild, DisplayElem)) if (DisplayElem(T->data)) return 1; return -1; } else return 1; } int InOrderTraverse_Stack(BiTree T, int(*DisplayElem)(TElemType e)) { BiTree p = T; BiTree s[100]; int top=-1; while (p||top!=-1) { while (p) { s[++top]=p; p = p->lchild; } if(top!=-1) { p=s[top--]; if (!DisplayElem(p->data))return -1; p = p->rchild; } } return 1; } void InOrderUnrec(BiTree t) { Stack s; initStack(s); BiTree p=t; while (p!=NULL || s.top!=s.base) { while (p!=NULL) { StackPush(s,p); p=p->lchild; } if (s.top!=s.base) { StackPop(s,p); DisplayElem(p->data); p=p->rchild; } } } void PreOrderUnrec(BiTree t) { Stack s; initStack(s); BiTree p=t; while (p!=NULL || s.top!=s.base) { while (p!=NULL) { DisplayElem(p->data); StackPush(s,p); p=p->lchild; } if (s.top!=s.base) { // StackPop(s,p); p=p->rchild; } } } int Depth(BiTree t) { int ld=0,rd=0; BiTree s=t; if(!t) return 0; if(t) { ld=Depth(s->lchild); rd=Depth(s->rchild); } if(ld>=rd) return ld+1; return rd+1; } void disp_leaf(BiTree t) { BiTNode *p=t; if(p) { if(p->lchild==NULL&&p->rchild==NULL) printf("%c ",p->data); disp_leaf(p->lchild); disp_leaf(p->rchild); } } int main() { BiTree S; creatBiTree(S); printf(" :
"); PreOrderTraverse(S, DisplayElem); _br_; printf(" :
"); InOrderTraverse(S, DisplayElem); _br_; printf(" :
"); PostOrderTraverse(S, DisplayElem); _br_; printf(" ( ):
"); InOrderTraverse_Stack(S, DisplayElem); _br_; printf(" ( ):
"); InOrderUnrec(S); _br_; printf(" ( ):
"); PreOrderUnrec(S); _br_; printf(" :%d",Depth(S)); _br_; printf(" :
"); disp_leaf(S); free(S); return 0; }

좋은 웹페이지 즐겨찾기