, когда вы находите узел в предварительном порядке, найти его преемника - это только , направляющийся на следующий узел.
То, о чем я думал сначала, является отношением узла и его преемников в pre-oder, но я обнаружил, что это кажется не очень ясным, как отношения в порядке. Я думаю, что есть только один шаг между узлом и его преемником (если существует): просто двигайтесь по пути. Поэтому я разрабатываю этот алгоритм.
Мой алгоритм ниже основан на предзаказе travesal, он может работать на двоичном дереве, а не только на BST.
#define NOT_FOUND -1
#define NEXT 0
#define FOUND 1
struct node {
struct node *p;//parent,but useless here
struct node *l;//left child
struct node *r;//right child
int value;
};
int travese(struct node* bnode, int* flag,int value)
{
if(bnode == NULL)
return 0;
else
{
if(*flag == FOUND)
//when the successor is found,do pruning.
return 1;
else if(*flag == NEXT) {
printf("successor:%d\n",bnode->value);
*flag = FOUND;
return 1;
}
else if(*flag == NOT_FOUND && bnode->value == value)
*flag = NEXT;
travese(bnode->l,flag,value);
travese(bnode->r,flag,value);
}
return 0;
}
и использовать его:
int flag = NOT_FOUND;
travese(root,&flag,value);
if(flag == NEXT || flag == NOT_FOUND)
printf("no successor.\n");
EDIT:
поворот алгоритма рекуррентного к повторяющемуся не сложен с помощью стека, как показано ниже:
int preorder_travese_with_stack(struct node* bnode, int* flag,int value)
{
if(bnode == NULL)
return 0;
struct stack s;//some kind of implement
push(s,bnode);
while(NotEmpty(s) && *flag) {
struct node *curNode = pop(s);
if(*flag == NEXT) {
printf("successor:%d\n",curNode->value);
*flag = FOUND;
return 1;
}
else if(*flag == NOT_FOUND && curNode->value == value)
*flag = NEXT;
push(s,curNode->r);
push(s,curNode->l);
}
return 0;
}
, но в соответствии с вашим c omment и оригинальное описание, я думаю, что тот, который вам нужен, - это итеративный алгоритм без стека. Вот он.
После того, как я подумал, искал и пытался, я написал один. Если трассировать дерево итеративно без стека, родитель узла больше не бесполезен. В пути некоторые узлы посещаются не только один раз, и вам необходимо записать его направление в это время.
int preorder_travese_without_stack(struct node *root,int value,int *flag)
{
int state=1;
//state: traveral direction on a node
//1 for going down
//2 for going up from its left chlid
//3 for going up from its right child
struct node *cur = root;
while(1) {
if(state == 1) //first visit
{
//common travese:
//printf("%d ",cur->value);
if(cur->value == value && *flag == NOT_FOUND)
*flag = NEXT;
else if (*flag==NEXT) {
*flag = FOUND;
printf("successor:%d\n",cur->value);
break;
}
}
if((state == 1)&&(cur->l!=NULL))
cur = cur->l;
else if((state==1)&&(cur->l==NULL))
{
state = 2;
continue;
}
else if(state==2) {
if(cur->r != NULL) {
cur=cur->r;
state = 1;
}
else
{
if(cur->p!=NULL)
{
if(cur==cur->p->r)
state = 3;
//else state keeps 2
cur=cur->p;
}
else //cur->p==NULL
{
if(cur->p->r!=NULL)
{
cur=cur->p->r;
state = 1;
}
else
break;
//end up in lchild of root
//because root's rchild is NULL
}
}
continue;
}
else //state ==3
{
if(cur->p!=NULL)
{
if(cur==cur->p->l)
state = 2;
else
state = 3;
cur=cur->p;
continue;
}
else
break;
}
}
}
использование такое же, как и первое повторение.
Если вы еще не сбиты с толку, в основном о направлении узла, вы можете нарисовать дерево и нарисовать траекторию предварительного заказа на бумаге, это поможет.
Я не уверен, что есть ошибки, оставленные в коде, но она хорошо работает на ниже дерева:
0
/ \
1 2
/\ /\
3 4 5 6
Кстати, "wirte вниз предварительный заказ (или еще) travese алгоритм дерева как путем повторения, так и итерации »является общей проблемой интервью, хотя разрешение последней на стек разрешено. Но я думаю, что требование BST не является необходимым в предзаказывании.
@wy: Спасибо за Ваш ответ и да, вы правы предзаказ Преемник будет только следующим шагом, делая обход и вы помощь я могу сделать это с помощью рекурсии, но по-прежнему заинтересован и думая, как это сделать итеративно :) – JackSparrow
@JackSparrow Я обновил два итерационных. – vvy