//二叉树深度优先遍历
//先序中序后序
//根据访问时机：第一次到先序，第二次到中序，第三次到后序
//先序：根节点-左子树-右子树
//中序：中序左子树-根节点-中序右子树
//后序：后序左子树-后序右子树-根节点
//树的深度优先遍历
//根据访问时机：首次访问先序，最后一次访问后序
//先序：根节点，先序所有子树
//后序：后序所有子树，根节点
//树转换成二叉树，先序相同，二叉树中序等效于树的后序
//森林转换二叉树相同
//二叉树遍历
//二叉树深度优先遍历
//递归实现，系统栈保护现场、恢复现场
void traversal(BTNode* p)
{
if(p != NULL)
{
visit(p);//先序
r(p->lChild);
//中序
r(p->rChild);
//后序
}
}
//二叉树深度优先遍历，非递归实现，自定义栈
//先序非递归遍历
void preorderNonrecursion(BTNode *bt)
{
if (bt != NULL)
{
BTNode *Stack[Maxsize];
int top = -1;//自定义栈
BTNode *p = NULL;//定义指针p
Stack[++top] = bt;//根节点入栈
while(top != -1)
{
p = Stack[top--];
visit(p);
if(p->rChild != NULL)
Stack[++top] = p->rChild;//右孩子先入栈
if(p->rChild != NULL)
Stack[++top] = p->lChild;
}
}
}
//先序序列：根-左子树-右子树
//逆后序：根-右子树-左子树
//后序非递归遍历代码
void postorderNonrecursion(BTNode *bt)
{
if (bt != NULL)
{
BTNode *Stack1[Maxsize];int top1 = -1;//辅助遍历的栈
BTNode *Stack2[Maxsize];int top2 = -1;//辅助逆后序求逆的栈
BTNode *p = NULL;//定义指针p
Stack1[++top] = bt;//根节点入栈
while(top != -1)
{
p = Stack[top--];
visit(p);
if(p->rChild != NULL)
Stack[++top] = p->lChild;//左孩子先入栈
if(p->rChild != NULL)
Stack[++top] = p->rChild;
}
while(top2 != -1)
{
p = Stack2[top2--];
visit(p);
}
}
}
//中序非递归遍历
//算法描述：
//1、根节点入栈
//2、一直入栈左孩子，直到左孩子为空，出栈一个结点，并访问
//3、该结点右孩子存在，重复步骤2，右孩子为空，继续出栈一个结点，并访问，重复步骤2
void inorderNonrecursion(BTNode *bt)
{
if (bt != NULL)
{
BTNode *Stack[Maxsize]; int top =-1;//定义辅助栈
BTNode *p = NULL;//定义指针p
p = bt;
while(top != -1 || p != NULL)//栈不为空，或者指向树的指针p不为空
{
while(p != NULL)
{
Stack[++top] = p;
p = p->lChild;
}//一直入栈左孩子
if(top != -1)
{
p = Stack[top--];
visit(p);
p = p->rChild;
}
}
}
}
//二叉树广度优先，层次遍历
//算法描述：
//1、根节点入队
//2、出队一个结点，检测出队结点的左右孩子，按左右顺序入队
//3、重复步骤2
void level(BTNode *bt)
{
if (bt != NULL)
{
int front = rear = 0;
BTNode *que[Maxsize];//顺序队列
BTNode *p;
rear = (rear + 1) % Maxsize;
que[rear] = bt;//入队
while(front != rear)//判断队列不为空
{
front = (front + 1) % Maxsize;
p = que[front];//出队
visit(p);
//检测左右孩子不为空，入队
if (p->lChild != NULL)
{
rear = (rear + 1) % Maxsize;
que[rear] = p->lChild;
}
if (p->rChild != NULL)
{
rear = (rear + 1) % Maxsize;
que[rear] = p->rChild;
}
}
}
}
//树的遍历(考的不多)
//先序遍历
void r(BTNode *p)//伪代码用于理解
{
if (p != NULL)
{
visit(p);
//树的所有孩子
r(p->child1);
r(p->child2);
r(p->child3);
r(p->child4);
......
r(p->childn);
}
}
//树的孩子存储结构，链式存储，邻接表
typedef struct Branch
{
int cIdx;
Branch* next;
}Branch;
typedef struct
{
int data;
Branch* first;
}TNode;
//取值
TNode tree[6];//数组长度为6
Branch* q = tree[0]->first;//指向第一个分支
tree[q->cIdx];//找到索引是cIdx的结点
//正确代码
//先序遍历
void preOrder(TNode *p, TNode tree[])
{
if (p != NULL)
{
Branch *q = p->first;
visit(p);
while (q != NULL)
{
preOrder(&tree[q->cIdx], tree);
q = q->next;
}
}
}
//后序遍历
void postOrder(TNode *p, TNode tree[])
{
if (p != NULL)
{
Branch *q = p->first;
while (q != NULL)
{
postOrder(&tree[q->cIdx], tree);
q = q->next;
}
visit(p);
}
}
//层次遍历
void level(TNode *tn, TNode tree[])
{
int front = rear = 0;
TNode *que[Maxsize];//辅助队列
TNode *p;
if (tn != NULL)
{
rear = (rear + 1) % Maxsize;
que[rear] = tn;//入队根结点
while(front != rear)
{
front = (front + 1) % Maxsize;
p = que[front];//出队
visit(p);
Branch *q = p->first;//找到指向孩子链表的分支
while(q != NULL)
{
rear = (rear + 1) % Maxsize;
que[rear] = &tree[q->cIdx];//入队孩子
q = q->next;
}
}
}
}
