新建 文本文档.txt

这是一个用java做的二叉树的遍历的实例！

树、二叉树

二叉树的中序非递归遍历算法
int InTraverse(BiTree T)
{
Stack S;
InitStack(S);
while(T!==NULL || !Empty(S))
{
    while(T!=NULL)
{
Push(S, T);
T = T->lchild;
        }
        T = Top(S); Pop(S);
        Visit(T);
        T = T->rchild;
}
DestroyStack(S);
return 1;
}

// 二叉树上的定位查找
BiNode *FindInBiTree(BiTree T, ElemType e)
{
if (T==NULL) return NULL;
if (T->data==e) return T;
BiNode *q = FindInBiTree(T->lchild);
if (q!=NULL) return q;
q = FindInBiTree(T->rchild);
return q;
}

中序线索化二叉树
struct ThrBiNode
{
ElemType data;
ThrBiNode *lchild, *rchild;
int ltag : 1;    // 约定0表示子树指针，非0表示线索
int rtag : 1;
};
typedef ThrBiNode *ThrBiTree;


// 遍历中序线索二叉树
int ThrInTraverse(ThrBiTree T)
{
    if (T->lchild==T) return 1;
ThrBiNode *p = T->lchild;
while (p->ltag==0) p = p->lchild;
while (p!=T)
{
    Visit(p);
    if (p->rtag==0)
    {
        p = p->rchild;
        while (p->ltag==0) p = p->lchild;
    }
    else
        p = p->rchild;
}
return 1;
}

// 线索化二叉树
ThrBiNode *pre;
int Threading(ThrBiTree &T)
{
if (T==NULL) return 1;
Threading(T->lchild);
if (pre->rchild==NULL)
{
    pre->rchild = T;
    pre->rtag = 1;
}
if (T->lchild==NULL)
{
    T->lchild = pre;
    T->ltag = 1;
}
pre = T;
Threading(T->rchild);
return 1;
}

int InThread(ThrBiTree &T)
{
ThrBiNode *newhead = new ThrBiNode;
pre = newhead;
Threading(T);
newhead->lchild = T; newhead->ltag=1;
pre->rchild = newhead; pre->rtag = 1;
newhead->rchild = pre; newhead->rtag = 1;
T = newhead;
return 1;
}