Обычно порядок определяется для бинарных деревьев. Допустим, что порядок «расширен» для (обычных) деревьев. Если дерево - единственный узел, то этот узел является обходом дерева по порядку. Если дерево T является деревом с поддеревьями T1, T2, ..., Tk и r как root, то в порядке T1 следует r, за которым следует упорядоченный обход T2, T3,. ., Tk - это порядок обхода T.
T дан в представлении правого брата левого ребенка. Структура данных для узла в C:
struct node {
int data;
struct node *left-child;
struct node *right-sibling;
}
Дерево представлено с указателем на root. Root не может иметь правого брата.
Вопрос в том, чтобы найти алгоритм обхода дерева по порядку. Рекурсия не допускается. (Рекурсивный алгоритм тривиален).
Я пытался адаптировать алгоритм для бинарных деревьев, для обычных деревьев.
Давайте рассмотрим следующее дерево:
1
/ | \
2 3 4
Порядок этого дерева 2 1 3 4.
Если мы рассмотрим соответствующее двоичное дерево:
1
/
2
\
3
\
4
, мы можем видеть, что порядок этого двоичного дерева равен 2 3 4 1. Мы можем видеть, что нет соответствия между порядком обычных деревьев и бинарными деревьями.
Я понятия не имею, как обходить обычное дерево в порядке.
То, что я сделал до сих пор:
Прогулка вокруг дерева - это порядок узлов, в которых мы начинаем с root, двигаясь против часовой стрелки и оставаясь как можно ближе к дереву. Мы печатаем узлы, когда сталкиваемся с ними.
Для того, чтобы по порядку мы перечислили лист при первой его передаче, но перечислим внутренний узел при второй передаче.
Вот код для обхода дерево. Это был быстрый взлом, поэтому я открыт для предложений и улучшений.
#include <stdio.h>
#include <stdlib.h>
typedef struct tree_node {
int data;
struct tree_node *left_child;
struct tree_node *right_sibling;
} tree_node;
typedef struct stack_node {
tree_node *data;
struct stack_node *next;
} stack_node;
void pop( stack_node **p_s )
{
if( *p_s == NULL ) {
printf("Error: The stack is empty\n");
}
else {
stack_node *tmp = *p_s;
*p_s = (*p_s)->next;
free( tmp );
}
}
tree_node *top( stack_node *s )
{
return s->data;
}
void push( tree_node *p_n, stack_node **p_s )
{
stack_node *tmp = malloc( sizeof( stack_node ) );
tmp->data = p_n;
tmp->next = *p_s;
*p_s = tmp;
}
tree_node *read_tree( void )
{
printf("Does this tree is empty (y/n):");
int c = getchar();
int c1;
while(( c1 = getchar() ) != '\n' && c1 != EOF );
if( c == 'y' ) return NULL;
else {
tree_node *tmp = malloc( sizeof( tree_node ) );
tree_node *root = tmp;
root->right_sibling = NULL;
stack_node *s = malloc( sizeof( stack_node ) );
s->data = root;
s->next = NULL; //Initialize the stack;
int num_nod;
state1:
tmp = top( s );
printf("Input the data for the node:");
scanf("%d", &(tmp->data) );
printf("How many children does this node have (0 for none):");
scanf("%d", &num_nod);
if( num_nod == 0 ) {
tmp->left_child = NULL;
goto state2;
}
else {
tree_node *tmp2 = malloc( sizeof( tree_node ) );
push( tmp2, &s );
tmp->left_child = tmp2;
for( int i = 1; i < num_nod; i++ ) {
tmp2->right_sibling = malloc( sizeof( tree_node ) );
tmp2 = tmp2->right_sibling;
}
tmp2->right_sibling = NULL;
goto state1;
}
state2: if( root == top( s ) ) return root;
tree_node *tmp2 = top( s );
tmp2 = tmp2->right_sibling;
pop( &s );
if( tmp2 == NULL )
goto state2;
else {
push( tmp2, &s );
goto state1;
}
}
}
void walk( tree_node *t )
{
if( t == NULL ) return;
stack_node *s = malloc( sizeof( stack_node ) );
s->data = t;
s->next = NULL; //Initialize the stack;
tree_node *tmp;
tree_node *tmp2;
tree_node *tmp3;
printf("%d ", t->data );//We have visited the root, so print it.
state1:
tmp = top( s );
tmp2 = tmp->left_child;
if( tmp2 == NULL ) {
goto state2;
}
else {
push( tmp2, &s );
printf("%d ", tmp2->data );
goto state1;
}
state2:
tmp = top( s );
tmp2 = tmp->right_sibling;
if( tmp == t ) {
return;
}
pop( &s );
tmp3 = top( s );
printf("%d ", tmp3->data );
if( tmp2 == NULL ) goto state2;
else {
push( tmp2, &s );
printf("%d ", tmp2->data );
goto state1;
}
}
int main()
{
tree_node *t = read_tree();
walk( t );
}
Мы можем реализовать алгоритм для заказа следующим образом. Вместо перечисления узлов в функции walk () мы можем хранить указатели на них в списке. Затем мы можем проанализировать список внутренних узлов и перечислить их только во второй раз, когда они появляются в списке. Но мне не нравится этот алгоритм. Он использует слишком много памяти и работает медленно. Любые идеи приветствуются.