一、二叉树

链式存储结构

	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);//递归遍历右子树
		}
	}

非递归版

	void PreOrder2(BiTree T)
	{
		Stack S;
		BiTree p = T;
		InitStack(S);
		while(p || !IsEmpty(S)) //栈不空或p不空时循环
		{
			if(p) //一路向左遍历
			{
				visit(p);//先序遍历，先访问根结点
				Push(S,p);//并入栈
				p = p->lchild; //左孩子不空，一直向左走
			}
			else //p空，出栈回溯，并转向出栈结点的右子树
			{
				Pop(S,p); 
				p = p->rchild; //转向根结点的右子树进行先序遍历
			}
		}
	}

中序遍历

递归版

void InOrder(BiTree T)
{
	if(T != NULL)
	{
		InOrder(T->lchild); //递归遍历左子树
		visit(T); //访问根结点
		InOrder(T->rchild); //递归遍历右子树
	}
}

非递归版

void InOrder2(BiTree T)
{
	Stack S;
	BiTree p = T;
	while(p || !IsEmpty(S)) //栈不空或p不空时循环
	{
		if(p) //一路向左遍历
		{
			Push(S,p);
			p = p->lchild;
		}
		else //p空，出栈回溯，并转向出栈结点的右子树
		{
			Pop(S,p);
			visit(p); //访问根结点
			p = p->rchild;//转向根结点的右子树进行中序遍历
		}
	}
}

后序遍历

递归版

void PostOrder(BiTree T)
{
	if(T != NULL)
	{
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
}

非递归版

思想：按照“根右左”的顺序遍历，将结果保存到栈中，最后依次出栈访问，恰好得到“左右根”的访问顺序。

void PostOrder(BiTree T)
{
	Stack s1,s2;
	BiTree p = T;
	while(p || !IsEmpty(s1)) //栈不空或p不空时循环
	{
		if(p) //一路向右遍历
		{
			Push(s2,p);
			Push(s1,p);
			p = p->rchild;
		}
		else //p空，出栈回溯，并转向出栈结点的左子树
		{
			Pop(s1,p);
			p = p->lchild;//转向根结点的左子树进行遍历
		}
	}
	while(!IsEmpty(s2))
	{
		Pop(s2,p);
		visit(p);//访问每个结点
	}
}

层序遍历

void LevelOrder(BiTree T)
{
	Queue Q;
	BiTree p;
	InitQueue(Q);
	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
{
	ElemType data;
	struct ThreadNode *lchild,*rchild;
	int ltag,rtag;//左右线索标志，0表示左右孩子，1表示线索
}ThreadNode,*ThreadTree;

构造(以中序为例)

	void InThread(ThreadTree &p,ThreadTree &pre)
	{
		if(p != NULL)
		{
			InThread(p->lchild,pre); //递归，线索化左子树
			if(p->lchild == NULL) //若左子树为空，建立前驱结点
			{
				p->ltag = 1;
				p->lchild = pre;
			}
			if(p->rchild == NULL && pre != NULL) //建立上一个结点的后驱结点
			{
				pre->rtag = 1;
				pre->rchild = p;
			}
			InThread(p->rchild,p);//递归，线索化右子树，更新当前结点为刚刚访问的结点
		}
		
	}

主过程算法

void CreateInThread(ThreadTree T)
{
	ThreadTree pre = NULL;
	if(T != NULL)
	{
		InThread(T,pre);
		pre->rchild = NULL;//处理遍历的最后一个结点
		pre->rtag = 1;
	}
}

遍历(以中序为例)

求中序线索二叉树中中序序列下的第一个结点

TreeNode *Firstnode(ThreadNode *p)
{
	while(p->ltag == 0) p = p->lchild; //最左下结点(不一定叶结点)
	return p;
}

求中序线索二叉树中结点p的后继

TreeNode *nextnode(ThreadNode *p)
{
	if(p->rtag == 0) return Firstnode(p->rchild);
	else return p->rchild;
}

不含头结点的中序线索二叉树的中序遍历的算法

	void Inorder(ThreadNode *T)
	{
		for(ThreadNode *p = Firstnode(T);p != NULL;p = nextnode(p))
		{
			visit(p);
		}
	}

二、树和森林

存储结构

双亲表示法(顺序存储)

#define MAX_TREE_SIZE 100
typedef struct{
	ElemType data;
	int parent;
}PTNode;

typedef struct{
	PTNode nodes[MAX_TREE_SIZE];
	int n;
}PTree;

孩子兄弟表示法(链式存储) 树转换成森林

typdef struct CSNode{
	ElemType data;
	struct CSNode *firstchild,*nextsibling;//第一个孩子和右兄弟指针
}CSNode,*CSTree;

相互转换方法

树转换成二叉树：大家变小家，双亲管老大，大孩管小孩

1. 在兄弟之间加一条线
2. 对每个结点，只保留它与第一个孩子的连线，与其他孩子的连线全部删去
3. 以树根为轴心，顺时针旋转45°

森林转换成二叉树：先把每棵树转换成二叉树，再连接每棵二叉树的根结点

二叉树转换成森林

1. 断开右子树，直到无右结点为止
2. 连接每个结点左孩子的右孩子，直到无右子树为止
3. 删去每个结点最初存在的右链

树和森林的遍历与二叉树遍历的对应关系