- 线索二叉树--kuan -

2007-04-12 晴

struct TTreeNode
{
ElemType data;
int ltag,rtah;//线索标志域
TTreeNode *left;
TTreeNode *right;
};

void InThread(TTreeNode *HT)
{
static TTreeNode *pre = NULL;//定义指向前驱结点的指针pre
if(HT != NULL)//当左子树为空时结束递归
{
if(HT->ltag == 0)
InThread(HT->left);//当左子树非空，给左子树加中序线索

if(pre != NULL && pre->rtag == 1)
pre->right = HT;//给前驱结点加后继线索

if(HT->left == NULL)//给当前结点加前驱线索
{
HT->ltag = 1;
HT->left = pre;
}

if(HT->right == NULL)
HT->rtag = 1; //给右指针域为空的结点加右线索标记

pre=HT; //把刚过的当前结点置为前驱结点
if(HT->rtag == 0)
InThread(HT->right);
}
}

TTreeNode *InorderNext(TTreeNode *p)//返回p结点的中序后继结点
{
if(p->rtag == 1)
return p->right;//结合图来看
else
{
p=p->right;
while(p->ltag == 0)
p=p->left;
return p;
}
}

void ThInorder(TTreeNode *HT)//按中序线索遍历以HT为树根指针的二叉树时间O(n) 空间O(1)
{
if(HT != NULL)
{
while(HT->ltag == 0)
HT = HT->left; //查找出中序遍历中的第一个结点
do
{
cout<<HT->data<<' ';
HT=InorderNext(HT);//查找出HT结点的中序后继结点
}while(HT != NULL);//当HT为空时算法结束
}
}.

[全部]

# posted by kuan @ 2007-04-12 12:56:43 评论(0)

笔名：

评论：

最多1000字。当前字数：0
*

联系方式：