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

Question

实际上在一次采访中，我被要求编写一个代码，通过该代码，二叉搜索树中的每个节点都有一个额外的指针，即 "next" 我们必须将每个节点的指针连接到它的前序后继节点，任何人都可以建议我的代码，因为我无法这样做。树节点具有以上结构：-

 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

正如尤金所说：所以用先序遍历遍历树并连接。为此，你需要知道你最后访问了哪个节点，如果有的话。

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

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指针接下来应该被更新的节点。更新不会发生在第一个访问的节点上。最后访问的节点的 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使其再次生效。）

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

Connect preorder predecessor with its successor in a binary search tree

c

tree