一:二叉树的遍历. 由于递归算法很简单，在这里就不例举了，主要看一下非递归算法(其实也就是用栈实现，因为递归本身就是一种栈) 1.先序遍历: 思想:(1)从根节点依次遍历当前节点的左子树，边遍历访问，并且压入栈 (2).再访问当前栈顶结点的右子树,然后再返回
一:二叉树的遍历.
由于递归算法很简单，在这里就不例举了，主要看一下非递归算法(其实也就是用栈实现，因为递归本身就是一种栈)
1.先序遍历:
思想:(1)从根节点依次遍历当前节点的左子树，边遍历访问，并且压入栈
(2).再访问当前栈顶结点的右子树,然后再返回到(1)执行,直至栈空
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int base,top;
}SqStack;
void PreOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec思想:(1)从根节点遍历左子树，边遍历边入栈
(2)弹出栈顶元素，并访问，然后访问当前栈顶的右子树,回到(1)
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int base,top;
}SqStack;
void InOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
push(s,p);
p=p->lchild;
}//endwhile
if (!StackEmpty(s))
{
p=pop(s);
visite(p->data); //访问根结点
p=p->rchild; //通过下一次循环实现右子树遍历
}//endif
}//endwhile
}//InOrderUnrec3.后序遍历(其实还不是特清楚，代码来自百度):(需要设置一个标志量表示当前节点的右子树是否被访问)
#define maxsize 100
typedef enum{L,R} tagtype;//标记的类型，为R时表示当前结点的
typedef struct
{
Bitree ptr;
tagtype tag;
}stacknode;
typedef struct
{
stacknode Elem[maxsize];
int base,top;
}SqStack;
void PostOrderUnrec(Bitree t)
{
SqStack s;
stacknode x;
StackInit(s);
p=t;
do
{
while (p!=null) //遍历左子树
{
x.ptr = p;
x.tag = L; //标记为左子树
push(s,x);
p=p->lchild;
}
while (!StackEmpty(s) && s.Elem[s.top].tag==R)//如果
{
x = pop(s);
p = x.ptr;
visite(p->data); //tag为R，表示右子树访问完毕，故访问根结点
}
if (!StackEmpty(s))
{
s.Elem[s.top].tag =R; //遍历右子树
p=s.Elem[s.top].ptr->rchild;
}
}while (!StackEmpty(s));
}//PostOrderUnrec
二.线索二叉树:
含有n个结点的二叉树,一共有2n个指针域,有n+1个处于Null状态，为了使空间不浪费，可以让这些空的指针域指向二叉树各种遍历的前驱或后继结点,这样又可以方便查找每一个元素，而不必采用遍历，节省了时间
1.存储结构:
typedef enum { Link, Thread } PointerThr;
// Link==0:指针，Thread==1:线索
typedef struct BiThrNode{
TElemType data;
Struct BiThrNode *lchild, *rchild; // 左右孩子指针
PointerThr LTag, RTag; // 左右标志,当LTag=Thread时，表示线索,为Link时表示指向下一结点
} BiThrNode, *BiThrTree;1）若结点有左子树，则lchild指向其左孩子；
否则， lchild指向其直接前驱(即线索)；
2).若结点有右子树，则rchild指向其右孩子；
否则，rchild指向其后继(即线索)；
例：
2.线索二叉树的中序遍历算法:
Status IOTraver_T( BiThrTree T,Status (*Visit)(TElemType e) )
{ //T指向头结点，头结点的左链lchild指向根结点，中序遍历 //二叉线索树T的非递归算法，对每个数据元素调用函数Visit。
p = T->lchild; //p指向根结点
while (p != T) { //空树或遍历结束时，p = = T
while (p->LTag==Link) p = p->lchild;
if (!Visit(p->data)) return ERROR; //访问其左子树为空的结点
while (p->RTag==Thread && p->rchild!=T)
{ p = p->rchild; Visit(p->data); } //访问后继结点
p = p->rchild;
}
return OK;
} // IOTraver_T3.线索二叉树的生成算法:
void InThreading (BiThrTree p)//中序并线索化
{
if (p)
{
InThreading( p->lchild ); // 左子树线索化
if ( !p->lchild )
{ p->LTag=Thread; p->lchild=pre; } // 前驱线索
if ( !pre->rchild )
{ pre->RTag=Thread; pre->rchild=p; } //后继线索
pre = p; // 保持pre指向p的前驱
InThreading(p->rchild); //右子树线索化
}
} // InThreadingStatus InorderThreading(BiThrTree & Thrt, BiThrTree T)
{ //中序遍历二叉树T,并将其中序线索化, Thrt 指向头结点.
if ( ! (Thrt = (BiThrTree) malloc ( sizeof (BiThrnode) ) ) exit ( OVERFLOW ) ;
Thrt ->LTag = Link; Thrt ->RTag = Thead; // 建头结点
Thrt ->rchild = Thrt ; //右指针回指
if ( !T ) Thrt ->lchild = Thrt ; // 若二叉树空,则左指针回指
else {
Thrt ->lchild = T; pre = Thrt; //将头结点与树相连
<strong>InThreading(T); </strong> // 中序遍历进行中序线索化，调用上面的函数
pre ->rchild = Thrt;
pre ->RTag = Thread; //最后一个结点线索化
Thrt ->rchild = pre;
}
return OK;
} // InOrderThreading
