我想了一會兒這個問題，但找不出算法。我的首選是迭代執行。到目前爲止，我已經弄清楚了一些事情，但在某些方面還不確定。BST中某個節點的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");
編輯：
轉動復發算法的迭代一個不難通過使用堆棧象下面這樣：
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;
}
但根據你的c省略和原始描述，我認爲你想要的是沒有堆棧的迭代算法。它是。
經過思考，搜索和嘗試，我寫了一個。當迭代地在沒有堆棧的情況下遍歷樹時，節點的父節點不再是無用的。在一條路徑中，一些節點不僅被訪問過一次，而且你需要在那個時候記錄它的方向。
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;
}
}
}
其用法與第一次重複相同。
如果您仍然困惑，主要是關於節點的方向，您可以繪製一棵樹並繪製預先遍歷紙張的路徑，這將有所幫助。
我不知道有剩餘的代碼中的bug，但它運作良好，下面的樹：
0
/ \
1 2
/\ /\
3 4 5 6
順便說一句，「WIRTE下來預購（或其他）樹的travese算法通過兩者的復發和迭代」是一個常見的面試問題，雖然解決由堆棧後者是permitted.but我覺得BST要求是爲了預travese不必要的。
我的算法的實現不使用的關鍵。因此，它可以在任何種類的二叉樹中使用，而不僅僅在二進制搜索樹中。 我使用的algorith是這樣的：
貝婁有我的解決方案。
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;
};
@wy：感謝您的答覆，是的，你說得對預購的繼任者是隻下一步一邊做序遍歷，並與你的幫助，我能夠用遞歸做，但仍然有興趣和思考如何做到這一點反覆@JackSparrow我已經更新了兩種迭代的人:) – JackSparrow
。 – vvy