두 갈래 나무와 관련된 흔한 문제

2185 단어
전기: 이 교과서에서는 주로 나무와 두 갈래 나무의 속성과 자주 사용하는 조작을 다루었다.다음은 두 갈래 나무에 대한 구체적인 예를 들자면 이 문제는 등급 시험이나 면접에서 자주 나타나니 많이 생각해 보세요.
제목 설명: 이미 알고 있는 두 갈래 나무의 앞차례 역력과 중간차례 역력은 각각 ABDEGCFH와 DBGEACHF이다. 그러면 이 두 갈래 나무의 뒷차례 역력은?
정답: DGEBHFCA
문제 해결 방법:
먼저 훑어보는 첫 번째 결점은 뿌리 결점이기 때문에 A는 뿌리이다.
그런 다음 A, (DBGE) A(CHF)를 중간 순서로 반복합니다.
DBGE는 왼쪽 하위 트리의 중간 경로이고 CHF는 오른쪽 하위 트리의 중간 경로입니다.
그리고 선순환에서 왼쪽 나무와 오른쪽 나무를 그어 A(BDEG)(CHF)를 만들면 B는 왼쪽 나무뿌리, C는 오른쪽 나무뿌리가 된다.
그런 다음 B와 C, (D) B(GE) A(HF)를 반복해서 찾습니다.
DBEG의 경우 B는 루트, D는 왼쪽 트리, EG는 오른쪽 트리의 중차 범람, CHF의 경우 C는 루트, HF는 오른쪽 트리의 중차 범람.아직 구분이 끝나지 않은 부분이 있기 때문에 계속 선서를 보십시오.
BDEG에 대해 B는 뿌리로 알고 D는 전체 왼쪽 나무로 알고 있기 때문에 EG는 오른쪽 나무의 선서 역력이고 E는 오른쪽 뿌리이며 대조 중서에 의하면 G는 E의 왼쪽 나무이고 CHF는 같은 이치이다.
그래서 나무의 구조는 A(B(D, E(G,), C(, F(H,)
그것 을 그림 으로 그려서 뒤 를 두루 돌아다니면 DGEBHFCA 이다
한 마디로 하면 선순 서열은 뿌리 결점을 확정하는 데 쓰이고, 중순 서열은 좌우 트리를 구분하는 데 쓰인다.
두 번째 제목: 두 갈래 나무를 세우고 그것을 훑어보기(선순, 중순, 후순), 출력 훑어보기 결과
[기본 요구사항]
키보드에서 입력(선순)을 받고 두 갈래 체인 테이블을 저장 구조로 삼아 두 갈래 트리(선순으로 구축)를 구축하고 귀속 알고리즘으로 이를 반복(선순, 중순, 후순)하여 반복 결과를 출력한다.
[테스트 데이터]
ABC DE G F(공백 문자)
결과 순서: ABCDEGF
중간 순서: CBEGDFA
후순: CGBFDBA
C 언어 설명 방법:
//예시적인 것은 먼저 훑어보는 것이고, 다른 것은 이 기초 위에서 고칠 수 있다.
#include
#include
typedef struct tnode
{ char data;
struct tnode *lchild;
struct tnode *rchild;
}tnode;
tnode *Tree_creat(tnode *t)
{ char ch;
ch=getchar();
if(ch==' ')
t=NULL;
else
{
if(!(t=(tnode *)malloc(sizeof(tnode))))
printf("Error!");
t->data=ch;//printf("[%c]",t->data);
t->lchild=Tree_creat(t->lchild);
t->rchild=Tree_creat(t->rchild);
}
return t;
}
void preorder(tnode *t)
{ if(t!=NULL)
{ printf("%c ",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
void main()
{
tnode *t=NULL;
t=Tree_creat(t);
preorder(t);
}

출처: 저는 우리입니다. 전재하려면 출처와 링크를 보류하세요!
본문 링크:http://www.54manong.com/?id=207
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646208", container: s }); })();
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646147", container: s }); })();

좋은 웹페이지 즐겨찾기