앞 순서와 중간 순서 결과에 따라 두 갈래 트리 재구성 (귀속 방법)

9716 단어 두 갈래 나무
가령 이미 앞의 차례와 중간의 차례가 왔다고 가정하면 어떻게 이 나무를 재건할 수 있습니까?
주어진 함수는 다음과 같이 정의됩니다.
void Rebuild(char* pPreOrder, // 
char
* pInOrder, //
int
nTreeLen, //
NODE
** pRoot) // NODE**

다음과 같이 반복적인 방법으로 해결합니다.
#include <iostream>

using namespace std;

struct NODE{
NODE
* pLeft;
NODE
* pRight;
char chValue;
};

int GetPos(char* str, char ch)
{
for(int i=0; i<strlen(str); i++)
{
if(ch==str[i])
{
return i;
}
}
return -1;
}
void Rebuild(char* pPreOrder, char* pInOrder, int nTreeLen, NODE** pRoot)
{
if(*pRoot==NULL)
return;
*pRoot=(NODE*)malloc(sizeof(NODE));
(
*pRoot)->chValue = pPreOrder[0];
int i=GetPos(pInOrder, pPreOrder[0]);
if(i>=nTreeLen-1)
(
*pRoot)->pRight=NULL;
if(i==0)
(
*pRoot)->pLeft=NULL;
Rebuild(
&pPreOrder[1], pInOrder, i, &(*pRoot)->pLeft);
Rebuild(
&pPreOrder[i+1], &pInOrder[i+1],nTreeLen-i-1, &(*pRoot)->pRight);
}

호출 예:
void PostOrderRetrieval(NODE* root)    // 
{
if(root==NULL)
return;
if(root->pLeft !=NULL)
PostOrderRetrieval(root
->pLeft);
if(root->pRight !=NULL)
PostOrderRetrieval(root
->pRight);
printf(
"%c
", root->chValue);
}

int main()
{
NODE
** root;
root
= (NODE**)malloc(sizeof(NODE*));
Rebuild(
"abdehcfgij", "dbheafcgji", 10, root);
PostOrderRetrieval(
*root);
free(
*root);
free(root);
}

좋은 웹페이지 즐겨찾기