树遍历_综合

//二叉树深度优先遍历
//先序中序后序
//根据访问时机：第一次到先序，第二次到中序，第三次到后序
//先序：根节点-左子树-右子树
//中序：中序左子树-根节点-中序右子树
//后序：后序左子树-后序右子树-根节点//树的深度优先遍历
//根据访问时机：首次访问先序，最后一次访问后序
//先序：根节点，先序所有子树
//后序：后序所有子树，根节点//树转换成二叉树，先序相同，二叉树中序等效于树的后序
//森林转换二叉树相同//二叉树遍历
//二叉树深度优先遍历
//递归实现，系统栈保护现场、恢复现场
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;//定义指针pStack[++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;//定义指针pStack1[++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;//定义指针pp = 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;}}}
}
树 遍历

树遍历
