数据结构-二叉树的遍历
中序遍历二叉树
1 递归算法
算法的递归定义是：
若二叉树为空，则遍历结束；否则
⑴ 中序遍历左子树(递归调用本算法)；
⑵ 访问根结点；
⑶ 中序遍历右子树(递归调用本算法)。
中序遍历的递归算法
void InorderTraverse(BTNode *T)
{ if (T==NULL)
return；
InorderTraverse(T->Lchild) ;
visit(T->data) ; /* 访问根结点 */
InorderTraverse(T->Rchild) ;
} 2 非递归算法（略）
设T是指向二叉树根结点的指针变量，非递归算法是：
若二叉树为空，则返回；否则，令p=T
⑴ 当p不为空，p进栈， p=p->Lchild ；
⑵ 否则(即p为空)，退栈到p，访问p所指向的结点；
⑶ p=p->Rchild ，转(1)；
直到栈空为止。
算法实现：
#define MAX_STACK_SIZE 50
void InorderTraverse( BTNode *T)
{ BTNode *Stack[MAX_STACK_SIZE ] ,*p=T ;
int top=0 , bool=1 ;
if (T==NULL) printf(“ Binary Tree is Empty!\n”) ;
else { do
{ while (p!=NULL)
{ stack[++top]=p ; p=p->Lchild ; }
if (top==0) bool=0 ;
else { p=stack[top] ; top-- ;
visit( p->data ) ; p=p->Rchild ; }
} while (bool!=0) ;
}
}
后序遍历二叉树
1 递归算法
算法的递归定义是：
若二叉树为空，则遍历结束；否则
⑴ 后序遍历左子树(递归调用本算法)；
⑵ 后序遍历右子树(递归调用本算法) ；
⑶ 访问根结点 。
后序遍历的递归算法
void PostorderTraverse(BTNode *T)
{ if (T!=NULL)
{ PostorderTraverse(T->Lchild) ;
PostorderTraverse(T->Rchild) ;
visit(T->data) ; /* 访问根结点 */
}
}
遍历二叉树的算法中基本操作是访问结点，因此，无论是哪种次序的遍历，对有n个结点的二叉树，其时间复杂度均为O(n) 。
2 非递归算法（略）
在后序遍历中，根结点是最后被访问的。因此，在遍历过程中，当搜索指针指向某一根结点时，不能立即访问，而要先遍历其左子树，此时根结点进栈。当其左子树遍历完后再搜索到该根结点时，还是不能访问，还需遍历其右子树。所以，此根结点还需再次进栈，当其右子树遍历完后再退栈到到该根结点时，才能被访问。
因此，设立一个状态标志变量tag ：
其次，设两个堆栈S1、S2 ，S1保存结点，S2保存结点的状态标志变量tag 。S1和S2共用一个栈顶指针。
设T是指向根结点的指针变量，非递归算法是：
若二叉树为空，则返回；否则，令p=T；
⑴ 第一次经过根结点p，不访问：
p进栈S1 ， tag 赋值0，进栈S2，p=p->Lchild 。
⑵ 若p不为空，转(1)，否则，取状态标志值tag ：
⑶ 若tag=0：对栈S1，不访问，不出栈；修改S2栈顶元素值(tag赋值1) ，取S1栈顶元素的右子树，即p=S1[top]->Rchild ，转(1)；
⑷ 若tag=1：S1退栈，访问该结点；
直到栈空为止。
算法实现：
#define MAX_STACK_SIZE 50
void PostorderTraverse( BTNode *T)
{ BTNode *S1[MAX_STACK_SIZE ] ,*p=T ;
int S2[MAX_STACK_SIZE ] , top=0 , bool=1 ;
if (T==NULL) printf(“Binary Tree is Empty!\n”) ;
else { do
{ while (p!=NULL)
{ S1[++top]=p ; S2[top]=0 ;
p=p->Lchild ;
}
if (top==0) bool=0 ;
else if (S2[top]==0)
{ p=S1[top]->Rchild ; S2[top]=1 ; }
else
{ p=S1[top] ; top-- ;
visit( p->data ) ; p=NULL ;
/* 使循环继续进行而不至于死循环 */ }
} while (bool!=0) ;
}}
层次遍历二叉树
层次遍历二叉树，是从根结点开始遍历，按层次次序“自上而下，从左至右”访问树中的各结点。 为保证是按层次遍历，必须设置一个队列。 设T是指向根结点的指针变量，层次遍历非递归算法是：
若二叉树为空，则返回；否则，令p=T，p入队；
⑴ 队首元素出队到p；
⑵访问p所指向的结点；
⑶将p所指向的结点的左、右子结点依次入队。直到队空为止。
#define MAX_NODE 50
void LevelorderTraverse( BTNode *T)
{ BTNode *Queue[MAX_NODE] , *p=T ;
int front=0 , rear=0 ;
if (p!=NULL)
{ Queue[++rear]=p; /* 根结点入队 */
while (front<rear)
{ p=Queue[++front]; visit( p->data );
if (p->Lchild!=NULL)
Queue[++rear]=p; /* 左结点入队 */
if (p->Rchild!=NULL)
Queue[++rear]=p; /* 左结点入队 */
}
}
}
二叉树遍历算法的应用
“遍历”是二叉树最重要的基本操作，是各种其它操作的基础，二叉树的许多其它操作都可以通过遍历来实现。如建立二叉树的存储结构、求二叉树的结点数、求二叉树的深度等。
二叉树的扩充方法是：在二叉树中结点的每一个空链域处增加一个扩充的结点(总是叶子结点，用方框“□”表示)。对于二叉树的结点值：
◆ 是char类型：扩充结点值为“？”或“#”；
◆ 是int类型：扩充结点值为0或-1；
下面的算法是二叉树的前序创建的递归算法，读入一棵二叉树对应的扩充二叉树的前序遍历的结点值序列。每读入一个结点值就进行分析：
◆ 若是扩充结点值：令根指针为NULL；
◆ 若是(正常)结点值：动态地为该指针分配一个结点，将该值赋给根结点，然后递归地创建根的左子树和右子树。
算法实现：
#define NULLKY ‘?’
#define MAX_NODE 50
typedef struct BTNode
{ char data ;
struct BTNode *Lchild , *Rchild ;
}BTNode ;
BTNode *Preorder_Create_BTree(BTNode *T)
/* 建立链式二叉树，返回指向根结点的指针变量 */
{ char ch ;
ch=getchar() ;
if (ch==NULLKY)
{ T=NULL; return(T) ; }
else
{
T=(BTNode *)malloc(sizeof(BTNode)) ;
T–>data=ch ;
Preorder_Create_BTree(T->Lchild) ;
Preorder_Create_BTree(T->Rchild) ;
}
}
求二叉树的叶子结点数
2 求二叉树的叶子结点数
可以直接利用先序遍历二叉树算法求二叉树的叶子结点数。只要将先序遍历二叉树算法中vist()函数简单地进行修改就可以。
算法实现：
＃define MAX_STACK_SIZE 50
int BiTreeleaves( BTNode *T)
{ BTNode *stack[MAX_STACK_SIZE] ,*p=T;
int top=0, num=0;
if (T!=NULL)
{ stack[++top]=p ;
while (top>0)
{ p=stack[top--] ;
if (p->Lchild==NULL&&p->Rchild==NULL) num++ ;
if (p->Rchild!=NULL )
stack[++top]=p->Rchild;
if (p->Lchild!=NULL )
stack[++top]=p->Lchild;
}
}
return(num) ;
}
求二叉树的深度
3 求二叉树的深度
利用层次遍历算法可以直接求得二叉树的深度。
算法实现：
＃define MAX_NODE 50
int BiTreedepth( BTNode *T)
{ BTNode * Queue[MAX_NODE] ,*p=T;
int front=0 , rear=0, depth=0, level ;
/* level总是指向访问层的最后一个结点在队列的位置 */
if (T!=NULL)
{ Queue[++rear]=p; /* 根结点入队 */
level=rear ; /* 根是第1层的最后一个节点 */
while (front<rear)
{ p=Queue[++front];
if (p->Lchild!=NULL)
Queue[++rear]=p; /* 左结点入队 */
if (p->Rchild!=NULL)
Queue[++rear]=p; /* 左结点入队 */
if (front==level)
/* 正访问的是当前层的最后一个结点 */
{ depth++ ; level=rear ; }
}
}
}
求深度的递归算法
/* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
int BiTreeDepth(BiTree T)
{
int i,j;
if(!T) return 0;
if(T->lchild)
i=BiTreeDepth(T->lchild);
else i=0;
if(T->rchild)
j=BiTreeDepth(T->rchild);
else j=0;
return i>j?i+1:j+1;
}