3

我正在尝试这个问题一段时间，但无法弄清楚算法。我的偏好是迭代地进行。到目前为止，我已经弄清楚了一些事情，但在某些方面不确定。

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

  • 首先遍历树找到节点
  • 在遍历树时，跟踪前一个节点。
  • 如果找到该节点，请检查是否存在左子节点，那么这就是后继返回。
  • 如果左孩子不存在，则检查右孩子是否存在，即是继任者并返回。
  • 如果节点（留给父节点）并且没有左子节点或右子节点，那么我们之前已经保存了 prev 节点，那么 prev 或 prev 的右子节点就是后继节点。
  • 但是如果我们找到的节点在父节点的右边并且没有左右子节点，如何找到这个节点的后继节点呢？

这个算法可能有很多缺陷，因为我仍然没有正确理解所有的情况。如果有人有任何想法或算法，请分享。

提前致谢。

4

2 回答 2

1

当您在 preorder 中找到一个节点时，找到它的后继只是遍历它的下一个节点。

我首先想到的是pre-oder中节点及其后继值的关系，但我发现它似乎不太清楚，就像in-order中的关系一样。我认为在节点及其后继者（如果存在）之间只有一步：继续遍历。所以我设计了这个算法。

我下面的算法是基于前序遍历的，它可以在二叉树上运行，而不仅仅是 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");

编辑：

通过使用如下堆栈将递归算法转换为迭代算法并不困难：

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

但是根据您的评论和原始描述，我认为您想要的是没有堆栈的迭代算法。在这里。

经过思考，搜索和尝试，我写了一个。当没有 stack 迭代遍历树时，节点的父节点不再无用。在一条路径中，有些节点不仅被访问一次，还需要记录它当时的方向。

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

顺便说一句，“通过递归和迭代写下树的预排序（或其他）遍历算法”是一个常见的面试问题，尽管允许通过堆栈解决后者。但我认为 BST 要求在 pre-订单遍历。

于 2013-08-29T03:14:29.660 回答
0

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

  1. 如果给定节点不存在，则返回 NULL
  2. 如果节点有左孩子，则返回左孩子
  3. 如果节点有右孩子，则返回右孩子
  4. 返回其右孩子存在但尚未处理的最近祖先的右孩子

下面是我的解决方案。

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;
};
于 2017-06-15T23:29:09.383 回答