BST中节点的PreOrder后继者-Java 学习之路

我正在尝试这个问题，但无法弄清楚算法 . 我的偏好是迭代地做 . 直到现在，我已经找到了一些东西，但在某些方面还不确定 .

目前，我的算法看起来像：

首先遍历树以查找节点
遍历树时，跟踪上一个节点 .
如果找到节点，检查是否存在左子节点，那么它是后继节点 .
如果留下的孩子不在场，那么检查是否有正确的孩子，即继承孩子 .
如果节点（留给父节点）并且之前已经保存了prev节点，则prev或prev的右子节点是后继节点 .
但是，如果我们找到的节点是父权的权利，并且没有左或右子，如何找到该节点的后继者呢？

可能是这个算法存在很多缺陷，因为我还没有正确理解所有情况 . 如果有人有任何想法或算法，请分享 .

提前致谢 .

2 回答

当你在预订中找到一个节点时，找到它的后继只是 travesing to its next node .

我首先想到的是一个节点与其后继者的 Value 观之间的关系，但我发现它似乎不太清楚，就像有序中的关系一样 . 我认为节点及其后继者（如果存在）只有一步：只需继续进行 . 所以我设计了这个算法 .

我的算法基于preorder 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;
}

but according to your comment and original description, I think the one you want is iterative algorithm without a stack.here it is.

经过思考，搜索和尝试，我写了一篇 . 当在没有堆栈的情况下迭代地遍历树时，节点的父节点不再是无用的 . 在路径中，一些节点不仅访问一次，而且您需要在那时记录其方向 .

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

顺便说一句，“通过递归和迭代对树的预订（或其他）travese算法”是一个常见的访谈问题，虽然允许通过堆栈解决后者 . 但我认为BST要求在前期是不必要的 . 订购travese .

回复于 2024-05-02T08:43:41+08:00

我的算法实现不使用密钥 . 因此，可以在任何类型的二叉树中使用它，而不仅仅是在二叉搜索树中 . 我使用的算法是这样的：

如果给定节点不存在，则返回NULL
如果节点已离开子节点，则返回左子节点
如果节点有正确的孩子，则返回右孩子
返回最右边的祖先，其右孩子在场，但尚未处理

贝娄有我的解决方案 .

TreeNode<ItemType>*  CBinaryTree<ItemType>::succesorPreOrder(TreeNode<ItemType> *wStartNode)
{

//if given node is not present, return NULL
if (wStartNode == NULL) return NULL;
/* if node has left child, return left child */
if (wStartNode->left != NULL) return wStartNode->left;
/* if node has right child, return right child */
if (wStartNode->right != NULL) return wStartNode->right;
/* if node isLeaf
return right child of the closest ancestor whose right child is present and not yet processed*/
if (isLeaf(wStartNode)) {
    TreeNode<ItemType> *cur = wStartNode;
    TreeNode<ItemType> *y = wStartNode->parent;

    while (y->right == NULL && y->parent!=NULL){
        cur = y;
        y = y->parent;
    }
    while (y != NULL && cur == y->right) {
        cur = y;
        y = y->parent;
    }
    return y->right;
}

}

bool CBinaryTree<ItemType>::isLeaf(TreeNode<ItemType> *wStartNode){
if (wStartNode->left == NULL && wStartNode->right == NULL) return true;
else return false;
};

回复于 2024-05-02T08:43:41+08:00

BST中节点的PreOrder后继者

2 回答

相关问题