------------------------------
- 涉及内容：
- 二叉树的先中后序遍历，层次遍历
- 递归与非递归方式 ， 伪代码实现
- 2020/10/29
- 应了解的内容：
- 先中后序遍历以根节点作为参照点，遍历顺序如下：
- 先序：根左右
- 中序：左根右
- 后序：左右根
- 画图最好理解
先序遍历
-------------------------------------------------------------
- 参数说明：
- T：根节点
- lchild：左子树
- rchild：右子树
-------------------------------------------------------------
递归：
void PreOrder(BiTree T) {
if(T) {
visit(T);
PreOrder( T->lchild ) ;
PreOrder( T->rchild ) ;
}
}
非递归：需要借助栈来实现
void PreOrder(BiTree T) {
/*
初始化一个栈
p指针指向头节点
*/
InitStack(s);
BiTree p = T;
// 如果当前节点不空，或者栈不空，
while( p || !IsEmpty(s) ) {
while( p ) {
visit(p); // 访问节点，访问次序，根左右
push(s,p);
p = p->lchild;
}
if( ！IsEmpty(s) ) {
pop(s,p);
p = p->rchild;
}
}
}
中序遍历
-------------------------------------------------------------
- 参数说明：
- T：根节点
- lchild：左子树
- rchild：右子树
-------------------------------------------------------------
递归：
void InOrder(BiTree T) {
if(T) {
InOrder( T->lchild ) ;
visit(T);
InOrder( T->rchild ) ;
}
}
非递归：需要借助栈来实现
void InOrder(BiTree T) {
/*
初始化一个栈
p指针指向头节点
*/
InitStack(s);
BiTree p = T;
// 如果当前节点不空，或者栈不空，
while( p || !IsEmpty(s) ) {
if( p ) {
push(s,p);
p = p->lchild;
}
else {
pop(s,p);
visit(T); // 访问节点，访问次序：左根右
p = p->rchild;
}
}
}
后序遍历
-------------------------------------------------------------
- 参数说明：
- T：根节点
- lchild：左子树
- rchild：右子树
-------------------------------------------------------------
递归：
void PostOrder(BiTree T) {
if(T) {
PostOrder( T->lchild ) ;
PostOrder( T->rchild ) ;
visit(T);
}
}
非递归：非递归后序遍历的节点要两次入栈，两次出栈
struct element{
BiTree *ptr;
int flag; // flag表示入栈的次数
}elem;
void PostOrder(BiTree T) {
/*
初始化一个栈
p指针指向头节点
*/
InitStack(s);
BiTree p = T;
// 如果当前节点不空，或者栈不空，
while( p || !IsEmpty(s) ) {
if( p ) { // L1
elem.ptr = p;
elem.flag = 1;
push(s,elem); // 将指针地址以及入栈次数保存到栈中
p = p->lchild;
}
else {
elem = push(s,elem);
p = elem.ptr;
if(elem.flag == 1) {
elem.flag = 2;
push(s,elem);
p = p->rchild;
}
else {
visit(p);
p = NULL; // 访问节点之后，p置为空指针，确保下次循环时可以直接跳过L1语句，也就是第一个if语句
}
}
}
}
层次遍历
-------------------------------------------------------------
- 参数说明：
- T：根节点
- lchild：左子树
- rchild：右子树
-------------------------------------------------------------
层次遍历需要借助队列实现
void LevelOrder(BiTree T) {
/*
初始化一个队列
p指针指向头节点
根节点入队
*/
InitStack(s);
BiTree p = T;
EnQueue(Q,T);
while( !IsEmpty(Q) ) { // 队列不空
DeQueue(Q,p); // 出队
visit(p); // 访问节点
if( p->lchild ) {
EnQueue(Q,p->lchild);
}
if( p->rchild ) {
EnQueue(Q,p->rchild);
}
}
}