中序线索化二叉树;
static void* prev;
template
void inorder_thread_aux(Tbtnode* root)
{
if(root == 0)
return;
inorder_thread_aux(root->lc_);
//线索化root->lc_ 和prev->rc_;
if(root->lc_ == 0)
root->setlc((Tbtnode*)prev, false);
if(prev != 0 && ((Tbtnode*)prev)->rc_ == 0)
((Tbtnode*)prev)->setrc(root, false);
prev = root;
inorder_thread_aux(root->rc_);
}
static void* prev;
template
void inorder_thread(Tbtnode* root)
{
prev = 0;
inorder_thread_aux(root);
//线索化最后一个节点prev;
((Tbtnode*)prev)->setrc(0, false);
}
遍历中序线索化二叉树:
template
NT* first(NT* root)
{
if(!root) return root;
for(; root->haslc(); root = root->lc_) { }
return root;
}
template
NT* next(NT* node)
{
if(node->hasrc()) return first(node->rc_);
return node->rc_;
}
template
void inorder_v2(Tbtnode* root,
void (*visit)(Tbtnode*))
{
for(root = first(root); root != 0;
root = next(root))
visit(root);
}
中序线索化二叉树;
static void* prev;
template
void inorder_thread_aux(Tbtnode* root)
{
if(root == 0)
return;
inorder_thread_aux(root->lc_);
//线索化root->lc_ 和prev->rc_;
if(root->lc_ == 0)
root->setlc((Tbtnode*)prev, false);
if(prev != 0 && ((Tbtnode*)prev)->rc_ == 0)
((Tbtnode*)prev)->setrc(root, false);
prev = root;
inorder_thread_aux(root->rc_);
}
static void* prev;
template
void inorder_thread(Tbtnode* root)
{
prev = 0;
inorder_thread_aux(root);
//线索化最后一个节点prev;
((Tbtnode*)prev)->setrc(0, false);
}
遍历中序线索化二叉树:
template
NT* first(NT* root)
{
if(!root) return root;
for(; root->haslc(); root = root->lc_) { }
return root;
}
template
NT* next(NT* node)
{
if(node->hasrc()) return first(node->rc_);
return node->rc_;
}
template
void inorder_v2(Tbtnode* root,
void (*visit)(Tbtnode*))
{
for(root = first(root); root != 0;
root = next(root))
visit(root);
}