一，树顺序和链式存储结构的定义
//树用儿子-兄弟表示法，就成了二叉树
//一般二叉树用顺序存储浪费空间，所以大都用链式存储
//特殊的二叉树有完美 或 满二叉树、完全树 可以用顺序存储
//严
#define MAXSIZE 100 //二叉树的最大结点数
typedef TElemType SqBiTree[MAXSIZE];
//用于顺序存储二叉树的结点。
//数组的每个元素都代表一个二叉树的结点，0 号单元存储根结点。
SqBiTree bt;
//变量 bt 被声明为 SqBiTree 类型，用于存储顺序存储的二叉树
/*二叉树顺序存储定义*/
typedef struct BiTNode{
TElemType data; //结点数据域
struct BiTNode *lchild,*rchild; //左右孩子指针
} BiTNode,*BiTree;
/*二叉树链式存储定义 */
二，p129 算法6-1 树的先序遍历（栈）
Status PreOrderTraverse (BinTree T, Status(*Vist)(TElemType e)){
//函数 PreOrderTraverse 接受一个二叉树的指针 T 和一个访问函数的指针 Vist。
Status PrintElement(TElemType e ){
print (e);
return OK;
}//这是一个自定义的函数，用于打印元素。它接受一个元素类型的参数 e，并打印该元素。
if(T){//如果二叉树不为空
if(Visit(T->data))
if(PreOrderTraverse(T->l.child.Visit))
if(PreOrderTraverse(T->r.child.Visit)) return OK;
return ERROR;
}else return Ok; //递归调用
}
三，p130 算法6-2 树的中序遍历（栈）
Status InOrderTraverse (BinTree T, Status(*Vist)(TElemType e)){
//函数 IneOrderTraverse 接受一个二叉树的指针 T 和一个访问函数的指针 Vist。
//中序遍历非递归
InitStack(s);
while( GetTop(S,p)&&p)
push(S,p->lchild);
//就将当前节点的左子节点压入栈中
Pop(S,p);/*删除栈顶元素，并用p返回其值*/
if(!StackEmpty(S)){
pop(S,p);
if(!Visit(p->data))
return ERROR;
push(S,p->rchild);
}
}
四， 树的后序遍历（栈）
//非递归
void PostOrderTraversal(BinTree BT){
BinTree T=BT;
//将二叉树的根节点赋值给变量 T。
Stack S=CreateStack();
//创建一个栈用于辅助遍历
while(T||!isEmpty(S)){
//只要树节点 T 不为空或者栈 S 不为空，就执行循环。
while(T){
//树节点 T 不为空时，将 T 入栈（PUSH(S, T)）
PUSH(S,T);
T=T->Left;
//移动到左子节点 T->Left
}
if(!isEmpty(S)){//如果栈不为空，从栈中弹出节点 T。
T=POP(S);
T=T->Right;//移动到右子节点 T->Right
printf("%d",T->Data);
//这里打印出当前节点的值，即访问根节点
}
}
}
五，树的层次遍历（队列）
//层序用的不是栈，而是队列
void LevelOrderTraversal(BinTree BT){
Queue Q; //队列做回溯
BinTree T; //临时用来操作树
if(!BT)return; //校验是否为空树
Q=CreateQueue(MaxSize); //创建并初始化队列
Add(BT,Q); //最初是根节点入队
while(!IsEmpty(Q)){
T=Delete(Q);
printf("%d",T->Data); //访问根节点，下面将左右孩子入队。
if(T->Left)Add(T->Left,Q);
if(T->Right)Add(T->Right,Q);
//提示一下：父弹出时，左右儿子入队；左儿子弹出时，左边两个孙子入队，然后右儿子弹出，右边两个孙子入队；这样总能一层层地访问
}
}
