두 갈래 나무, 귀속, 비귀속 두루 다니며 깊이를 구하고 잎 노드를 출력한다
#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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.