데이터 구조 기 말 복습 - 이 진 트 리 복원 (우선 순위 와 중간 순서 에 따라 출력 우선 순 서 를 옮 겨 다 니 며)

1428 단어
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 100000;
char pre[maxn];     /**         */
char ino[maxn];     /**         */
//char post[maxn];    /**         */
typedef struct BiNode
{
    char data;
    BiNode *Left;
    BiNode *Right;
}BiNode, *BiTree;

BiTree build(char *pre, char *ino, int len)
{
    if(len <= 0)
        return NULL;
    BiTree T = new BiNode;
    T->data = *pre;
    char *root = pre;
    char *p = ino;
    while(p)
    {
        //              
        if(*p == *root)
            break;
        ++p;
    }
    //      
    int left_len = p - ino;
    T->Left = build(pre + 1, ino, left_len);
    T->Right = build(pre + 1 + left_len, p + 1, len - left_len - 1);
    return T;
}

//    
void postOrder(BiTree T)
{
    if(T)
    {
        postOrder(T->Left);
        postOrder(T->Right);
        printf(" %c", T->data);
    }
}


int main()
{
    /**N         */
    int N;
    scanf("%d %s %s", &N, pre, ino);
    BiTree T = build(pre, ino, N);
    printf("postorder:");
    postOrder(T);
    printf("
"); }

참고 블 로그:https://blog.csdn.net/qq_37708702/article/details/79644068

좋은 웹페이지 즐겨찾기