c-在二元搜索树中连接预购前序与后继

Question

事实上，在一次采访中，我被要求编写一个代码，通过该代码，二进制搜索树中的每个节点都有一个额外的指针，即"下一个"，我们必须将每个节点的指针连接到其预购后继节点，有人能建议我使用该代码吗？因为我无法这样做。树节点具有以上结构：-

 struct node {
        int data ;
        struct node *left,*right;
        struct node *next; //this pointer should point to pre order successor 
        };

谢谢。

多亏了你们破解了这个解决方案，下面是用c:-编写的整个代码

#include <stdio.h>
#include <stdlib.h>
struct node
{
        int data;
        struct node *left,*right,*next;
};
struct node* getNode(int data)
{
        struct node* temp=(struct node*)malloc(sizeof(struct node));
        temp->left=temp->right=NULL;
        temp->data=data;
        return temp;
}
void insert(struct node**root,int data)
{
    if(!*root)
    {
        *root=(struct node*)malloc(sizeof(struct node));
        (*root)->left=(*root)->right=NULL;
        (*root)->data=data;
    }
    else if(data<(*root)->data)
        insert(&((*root)->left),data);
    else if(data>(*root)->data)
        insert(&((*root)->right),data);
}
struct node* preorderSuccessor(struct node* root,struct node* p)
{
    int top,i;
    struct node *arr[20];
    if(!root || !p)
        return NULL;
    if(p->left)
        return p->left;
    if(p->right)
        return p->right;
    top=-1;
    while(root->data!=p->data)
    {
        arr[++top]=root;
        if(p->data<root->data)
            root=root->left;
        else
            root=root->right;
    }
    for(i=top;i>=0;i--)
    {
        if(arr[i]->right)
        {
            if(p!=arr[i]->right)
                return arr[i]->right;
        }
        p=arr[i];
    }
    return NULL;
}
void connect(struct node* parent,struct node *r)
{
        if(r)
        {       connect(parent ,r->left);    
                r->next = preorderSuccessor(parent,r);
                connect(parent,r->right);
        }
}

int main()
{
        struct node* root=NULL,*temp=NULL;
        int arr[]={10,11,2,3,9,8,4,5},size,i;
        size=sizeof(arr)/sizeof(arr[0]);
        for(i=0;i<size;i++) 
          insert(&root,arr[i]);
        connect(root,root);
        struct node *ptr = root;
        while(ptr){
          // -1 is printed if there is no successor
          printf("Next of %d is %d n", ptr->data, ptr->next? ptr->next->data: -1);
          ptr = ptr->next;
        }

        return 0;
}

Answer 1

正如Eugene所说：所以用预序遍历遍历树并连接要做到这一点，你需要知道你最后访问了哪个节点（如果有的话）。

您可以通过传递对上一个节点的引用，使用通常的递归方法来实现这一点。这必须是在整个递归过程中有效的变量的地址，因为前一个节点不一定离根更近。您可以使用全局变量，但在包装函数中创建的变量可能更好：

void connect_r(struct node *node, struct node **whence)
{
    if (node) {
        if (*whence) (*whence)->next = node;
        *whence = node;
        connect_r(node->left, whence);
        connect_r(node->right, whence);
    }
}
void connect(struct node *head)
{
    struct node *p = NULL;
    connect_r(head, &p);
    if (p) p->next = NULL;
}

connect中的指针p（其地址被传递给递归函数connect_r）保持其next指针接下来应该被更新的节点。更新不会发生在第一个访问的节点上。并且最后访问节点的CCD_ 5成员必须在递归之后显式地设置为CCD_。

或者，您可以使用堆栈迭代连接节点：

void connect(struct node *head)
{
    struct node *p = NULL;
    struct node **prev = &p;
    struct node *stack[32];    // To do: Prevent overflow
    size_t nstack = 0;
    if (head) stack[nstack++] = head;
    while (nstack) {
        struct node *node = stack[--nstack];
        *prev = node;
        prev = &node->next;
        if (node->right) stack[nstack++] = node->right;
        if (node->left) stack[nstack++] = node->left;
    }
    *prev = NULL;
}

连接的next指针是当前树的快照。节点的插入、删除和重新排列将使next链无效。（但是，只要树的左右链接一致，就可以通过调用connect使其再次有效。）