在二叉搜索树中将前序前驱与其后继连接

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;
}

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

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

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 使其再次有效。)