树

二叉树的遍历
先序
typedef struct BiTnode{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

void PreOrder(BiTree T){
if(T!=NULL){
visit(T); //访问根结点（可改变访问顺序、中序、后序）
PreOrder(T->lchild); //递归遍历左子树
PreOrder(T->rchild); //递归遍历右子树
}
}

层序遍历

一个队列
层层入队

typedef struct BiTnode{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//链式队列结点
typedef struct LinkNode{
BiTNode * data;
typedef LinkNode *next;
}LinkNode;

typedef struct{
LinkNode *front, *rear;
}LinkQueue;

//主函数
void LevelOrder(BiTree T){
LinkQueue Q;
InitQueue (Q); //初始化辅助队列
BiTree p;
EnQueue(Q,T); //将根节点入队
while(!isEmpty(Q)){ //队列不空则循环
DeQueue(Q,p); //队头结点出队
visit(p); //访问出队结点
if(p->lchild != NULL)
EnQueue(Q,p->lchild); //左孩子入队
if(p->rchild != NULL)
EnQueue(Q,p->rchild); //右孩子入队
}
}

线索二叉树

二叉树线索化：先序、中序、后序。

typedef struct ThreadNode{
int data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag; // 左、右线索标志
}ThreadNode, *ThreadTree;

//全局变量pre, 指向当前访问的结点的前驱
TreadNode *pre=NULL;

//先序遍历二叉树，一边遍历一边线索化
void PreThread(ThreadTree T){
if(T!=NULL){
visit(T);
if(T->ltag == 0) //lchild不是前驱线索
PreThread(T->lchild);
PreThread(T->rchild);
}
}

void visit(ThreadNode *q){
if(q->lchid = NULL){ //左子树为空，建立前驱线索
q->lchild = pre;
q->ltag = 1;
}

if(pre!=NULL && pre->rchild = NULL){
pre->rchild = q; //建立前驱结点的后继线索
pre->rtag = 1;
}
pre = q;
}

//先序线索化二叉树T
void CreateInThread(ThreadTree T){
pre = NULL; //pre初始为NULL
if(T!=NULL);{ //非空二叉树才能进行线索化
PreThread(T); //先序线索化二叉树
if(pre->rchild == NULL)
pre->rtag=1; //处理遍历的最后一个结点
}
}