Как закодировать двоичное дерево поиска из заданных обходов PreOrder и PostOrder

Итак, вопрос очень похож на ребус. Но прежде всего нам нужно понять нашу проблему и какую информацию мы можем из нее извлечь.

Позвольте мне привести вам простой пример,

Предзаказ[] = {1, 2, 4, 5, 3, 6, 7}

PostOrder[] = {4, 5, 2, 6, 7, 3, 1}

Здесь корень прямо сейчас равен 1, потому что он должен был выполнить предварительный заказ при создании обхода PreOrder по его определению. Кроме того, он будет последним в обходе PostOrder.

Затем вы можете заметить, что человек справа от 1 является его левым дочерним элементом в предварительном порядке, т. е. 2. Точно так же 3 должен быть правым дочерним элементом 1, называемым сейчас Root.

Таким образом, мы можем легко найти корень, левый дочерний элемент и правый дочерний элемент сразу из заданной последовательности. Следующее, что мы хотим увидеть, это левый дочерний элемент в PostOrder и правый дочерний элемент в PreOrder. Тогда мы получим обходы секционированного порядка примерно так:

Предзаказ[] = {1, |2, 4, 5,| 3, 6, 7}

PostOrder[] = {4, 5, 2,| 6, 7, 3,| 1}

Отсюда мы получаем мотивацию для чего-то вроде рекурсии. Итак, теперь нам нужно написать функцию, которая поможет нам в распространении этой рекурсии. Теперь нам нужно решить, какие параметры должна принимать наша функция для распространения этой рекурсии. Ему нужны оба секционированных массива обходов, вот и все. Это все, что нам нужно. Поскольку C не позволяет нам нарезать массивы, мы будем работать с индексами. Это хорошо.

Но если мы продолжаем рекурсию, нам нужно подумать и о завершении. Вот возможные случаи прекращения, о которых мы можем подумать.

Завершение 1 (когда в массиве остается 1 элемент): Итак, если ваша программа работала правильно, то все готово, но рекурсивный характер убьет все. Итак, это условие наступит, когда останется только один элемент. Затем мы создадим узел, но он левый дочерний, а правый дочерний нужно установить равным нулю, и наша программа завершится.

Завершение 2 (когда в массиве остаются два элемента): поскольку мы кодируем Двоичное дерево поиска, мы можем предположить, что левый дочерний элемент всегда будет первым. И здесь наша программа также обрывается.

Ниже приведена полная программа и работающая демонстрация, но я настоятельно рекомендую вам зайти сюда только после того, как вы потратите на это почти неделю, в противном случае идите и поищите что-нибудь еще для оттачивания своих навыков.

typedef struct Tree_Node
{
 int data;
 struct Tree_Node* Left_Child;
 struct Tree_Node* Right_Child;
}Tree_Node;
void Make(Tree_Node **imp, int *PreO, int *PostO, int pr_st, int pr_fin, int pt_st, int pt_fin)
{
 printf(“Call no %d\n”, i++);
 if( pr_st==pr_fin ) //Termination Case 1 when single element remains
 {
 Tree_Node*t;
 t = (Tree_Node*)malloc(sizeof(Tree_Node));
 t->data = PreO[pr_st];
 t->Left_Child = t->Right_Child = NULL;
 *imp = t; //Actual Linking
 return;
 }
 else if( pr_st+2 == pr_fin ) //Termination Case 2 when three element remains
 {
 Tree_Node *t, *tlc, *trc;
 t = (Tree_Node*)malloc(sizeof(Tree_Node));
 tlc = (Tree_Node*)malloc(sizeof(Tree_Node));
 trc = (Tree_Node*)malloc(sizeof(Tree_Node));
 t->data = PreO[pr_st];
tlc->data = PreO[pr_st+1];
 trc->data = PreO[pr_st+2];
tlc->Right_Child = tlc->Left_Child = NULL;
 trc->Right_Child = trc->Left_Child = NULL;
t->Left_Child = tlc;
 t->Right_Child = trc;
 (*imp) = t; //Actual Linking
 return;
 }
 else if( pr_st+1 == pr_fin ) //Termination Case 3 when two element remains,
 {
 Tree_Node*t, *t1;
 t = (Tree_Node*)malloc(sizeof(Tree_Node));
 t1 = (Tree_Node*)malloc(sizeof(Tree_Node));
t->Right_Child = t->Left_Child = NULL;
 t1->Right_Child = t1->Left_Child = NULL;
t->data = PreO[pr_st];
 t1->data = PreO[pr_fin];
 t->Left_Child = t1;
(*imp) = t; //Actual Linking
 return;
 }
 else //No termination, further Propagation
 {
 Tree_Node*t;
 t = (Tree_Node*)malloc(sizeof(Tree_Node));
 t->data = PreO[pr_st];
 t->Left_Child = t->Right_Child = NULL;
 (*imp) = t; //Actual Linking
int lc_p = Give_Me_Index( PreO[pr_st+1], PostO); //finding the position of left child in PostOrder
 int rc_p = Give_Me_Index( PostO[pt_fin-1], PreO); //finding the position of right child in PreOrder
Make(&t->Left_Child, PreO, PostO, pr_st+1, rc_p-1, pt_st, lc_p);
 Make(&t->Right_Child, PreO, PostO, rc_p, pr_fin, lc_p+1, pt_fin-1);
 return;
 }
}
int Give_Me_Index(int num, int A[])
{
 int p = 0;
 while( A[p]!=num ){ p++; } //go ahead until you find it
 return p;
}
void Inorder(Tree_Node* x)
{
 if(x)
 {
 if(x->Left_Child) Inorder(x->Left_Child);
 printf(“..%d..\n”, x->data); //data in the middle
 if(x->Right_Child) Inorder(x->Right_Child);
 }
}
int main()
{
 int n = 11;
 Tree_Node* Root;
int PreO[] = {1, 2, 4, 3, 5, 6, 13, 8, 7, 11, 12};
 int PostO[] = {2, 5, 13, 8, 6, 3, 11, 12, 7, 4, 1};
Make(&Root, &PreO, &PostO, 0, n-1, 0, n-1);
 Inorder(Root);
 Delete(Root);
 return 0;
}

Ниже приведена демонстрация описанной выше программы.

Спасибо, что прочитали эту статью, и я надеюсь, что она поможет вам, иначе Google и Youtube всегда будут рядом.

Приятного обучения (: — — — :)

/* Пишите мне по любым вопросам [email protected] */