데이터 구조 이 진 트 리 의 옮 겨 다 니 기
5594 단어 데이터 구조
/**********************************************************************
(1)
(2)
(3) ： ， ，
************************************************************************/
#include <cstdio>
#include <cstdlib>
const int MAX=20;
//
typedef struct Node
{
char ch; //
struct Node *plchild; //
struct Node *prchild; //
}BiTreeNode;
//
//1.
// ABD#G##EH##I##CF#J###
void CreateBiTree_PreOrder(BiTreeNode * &T) //
{
char ch;
scanf("%c",&ch);
if('#'==ch)
T=NULL;
else {
T=new BiTreeNode;
if(NULL==T)
exit(-1);
T->ch=ch;
CreateBiTree_PreOrder(T->plchild); //
CreateBiTree_PreOrder(T->prchild); //
}
}
//2.
/* ：a(b(c,d),e(f(,g),h(i)))
'(': ， 。 ， flag=1
',': 。 flag=2
')': ， 。
default: ， ，
*/
void CreateBiTree_ByString(BiTreeNode* &T, char str[])
{
BiTreeNode* Stack[MAX]; //
int top=0,flag=0;
BiTreeNode* p=NULL; //
while(*str)
{
switch(*str)
{
case '(':
Stack[top++]=p;
flag=1; //
break;
case ',':
flag=2; //
break;
case ')':
--top; //
break;
default:
{
p=new BiTreeNode;
if(NULL==p)
return ;
if(T==NULL)
T=p;
p->ch=*str;
p->plchild=NULL;
p->prchild=NULL;
switch(flag) // flag
{
case 1:
Stack[top-1]->plchild=p; //
break;
case 2:
Stack[top-1]->prchild=p; //
break;
}
break;
}
}
++str;
}
}
//
void PreOrderTraverse_Recur(BiTreeNode *T)
{
if(T)
{
printf("%2c",T->ch);
PreOrderTraverse_Recur(T->plchild);
PreOrderTraverse_Recur(T->prchild);
}
}
//
/* : ， 。 ， ， 。
， NULL. 。
*/
void PreOrderTraverse_NoRecur(BiTreeNode *T)
{
BiTreeNode* Stack[MAX]; //
int top=0;
BiTreeNode *p=T;
while( p || top >0)
{
while(p)
{
printf("%2c",p->ch); //
Stack[top++]=p; //
p=p->plchild; //
}
if(top>0) //top
{ //
p=Stack[--top]; // NULL 。
p=p->prchild; //
}
}
}
//
void InOrderTraverse_Recur(BiTreeNode *T)
{
if(T) // NULL
{
InOrderTraverse_Recur(T->plchild); //
printf("%2c",T->ch); //
InOrderTraverse_Recur(T->prchild); //
}
}
//
/* ： ( ， ）
， , NULL. 。
*/
void InorderTraverse_NoRecur(BiTreeNode *T)
{
BiTreeNode* Stack[MAX];
int top=0;
BiTreeNode *p=T;
while( p || top>0 )
{
while(p)
{
Stack[top++]=p; //
p=p->plchild; //
}
if(top>0)
{
p=Stack[--top]; //
printf("%2c",p->ch); //
p=p->prchild; //
}
}
}
//
void AfterOrderTraverse_Recur(BiTreeNode *T)
{
if(T)
{
AfterOrderTraverse_Recur(T->plchild);
AfterOrderTraverse_Recur(T->prchild);
printf("%2c",T->ch);
}
}
//
/* ： 。 NULL, ，
q 。
*/
void AfterOrderTraverse_NoRecur(BiTreeNode *T)
{
BiTreeNode* Stack[MAX];
int top=0;
BiTreeNode *p=T,*q=NULL; // q
while(p || top>0)
{
while(p) //
{
Stack[top++]=p;
p=p->plchild;
}
if(top>0)
{
p=Stack[top-1]; //
if(p->prchild==NULL || p->prchild == q) //
{
printf("%2c",p->ch);
q=p;
p=NULL;
top--;
}
else //
p=p->prchild;
}
}
}
//
void DestoryBiTree(BiTreeNode* &T)
{
if(T)
{
if(T->plchild)
DestoryBiTree(T->plchild);
if(T->prchild)
DestoryBiTree(T->prchild);
delete T;
T=NULL;
}
}
int main()
{//ABD#G##EH##I##CF#J###
BiTreeNode *T=NULL;
CreateBiTree_PreOrder(T);
puts(" :");
PreOrderTraverse_Recur(T);
puts("");
puts(" :");
PreOrderTraverse_NoRecur(T);
puts("");
puts(" :");
InOrderTraverse_Recur(T);
puts("");
puts(" :");
InorderTraverse_NoRecur(T);
puts("");
puts(" :");
AfterOrderTraverse_Recur(T);
puts("");
puts(" :");
AfterOrderTraverse_NoRecur(T);
puts("");
DestoryBiTree(T); //
puts("
-- ------------");
BiTreeNode *T2=NULL;
char str[]="a(b(c,d),e(f(,g),h(i)))";
CreateBiTree_ByString(T2,str);
puts(" :");
PreOrderTraverse_Recur(T2);
puts("");
puts(" :");
PreOrderTraverse_NoRecur(T2);
puts("");
puts(" :");
InOrderTraverse_Recur(T2);
puts("");
puts(" :");
InorderTraverse_NoRecur(T2);
puts("");
puts(" :");
AfterOrderTraverse_Recur(T2);
puts("");
puts(" :");
AfterOrderTraverse_NoRecur(T2);
puts("");
//DestoryBiTree(T2); //
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
