这是一个将二叉搜索树转换为排序双向链表的功能。想法是进行一次遍历并将访问节点放入一个大小为2的圆形数组中。然后调整左右指针以转换为双向链表。当前节点的右指针从不修改并稍后访问。问题出在哪里?将BST转换为排序的双向链表(调试)
void TreetoQueue(node* tnode)
{static node* arr[2]={NULL,NULL};
static int index=0;
if(tnode==NULL) return;
TreetoQueue(tnode->left);
arr[index]=tnode; //current node
if(arr[1]!=NULL)
{ if(index==0)
{arr[1]->right=arr[0]; //modify right pointer of inorder predecessor to point to current node
arr[0]->left=arr[1]; //modify current node's left pointer to point to inorder predecessor
}
if(index==1)
{arr[0]->right=arr[1];
arr[1]->left=arr[0];
}
cout<<"index-"<<index<<" "<<arr[0]->val<<" "<<arr[1]->val<<"\n";
}
index=(index+1)%2;
TreetoQueue(tnode->right);
}
_______5______
/ \
___3__ 6__
/ \ \
1 4 _9
/\
7 10
index-1 1 3
index-0 4 3
index-1 4 5
index-0 6 5
index-1 6 7
index-0 9 7
index-1 9 10
node->left->left->right is NULL //Intended to be 3
node->left->right->left is NULL//intended to be 3
node->left->right->right is NULL//intended to be 5
编辑:它可以作为intended.Only,我不得不改变根开始list.I用于其他功能做this.Could无我有一个额外的功能来实现这一点?
node* TreetoQueue2(node* root)
{node* head=root;
while(head->left!=NULL)
head=head->left;
TreetoQueue(root);
return head;
}
你说'如果(ARR [1]!= NULL)'。最初它被声明为NULL。之后我不会看到它改变。有什么我失踪? – noMAD 2012-03-07 22:42:19
arr [index] = tnode和index =(index + 1)%2.arr [1]可以在输出中看到 – bl3e 2012-03-07 22:59:46
您可以解释一下您奇怪的缩进方案吗? – 2012-03-07 23:03:48