1 递归算法
算法的递归定义是：
若2叉树为空，则遍历结束；否则
⑴ 中序遍历左子树(递归调用本算法)；
⑵ 访问根结点；
⑶ 中序遍历右子树(递归调用本算法)。
中序遍历的递归算法
void InorderTraverse(BTNode *T)
{ if (T==NULL)
return；
InorderTraverse(T->Lchild) ;
visit(T->data) ; /* 访问根结点 */
InorderTraverse(T->Rchild) ;
} 2 非递归算法（略）
设T是指向2叉树根结点的指针变量，非递归算法是：
若2叉树为空，则返回；否则，令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!
”) ;
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 递归算法
算法的递归定义是：
若2叉树为空，则遍历结束；否则
⑴ 后序遍历左子树(递归调用本算法)；
⑵ 后序遍历右子树(递归调用本算法) ；
⑶ 访问根结点 。
后序遍历的递归算法
void PostorderTraverse(BTNode *T)
{ if (T!=NULL)
{ PostorderTraverse(T->Lchild) ;
PostorderTraverse(T->Rchild) ;
visit(T->data) ; /* 访问根结点 */
}
}
遍历2叉树的算法中基本操作是访问结点，因此，不管是哪一种次序的遍历，对有n个结点的2叉树，其时间复杂度均为O(n) 。
2 非递归算法（略）
在后序遍历中，根结点是最后被访问的。因此，在遍历进程中，当搜索指针指向某1根结点时，不能立即访问，而要先遍历其左子树，此时根结点进栈。当其左子树遍历完后再搜索到该根结点时，还是不能访问，还需遍历其右子树。所以，此根结点还需再次进栈，当其右子树遍历完后再退栈到到该根结点时，才能被访问。
因此，设立1个状态标志变量tag ：
其次，设两个堆栈S1、S2 ，S1保存结点，S2保存结点的状态标志变量tag 。S1和S2共用1个栈顶指针。
设T是指向根结点的指针变量，非递归算法是：
若2叉树为空，则返回；否则，令p=T；
⑴ 第1次经过根结点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!
”) ;
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) ;
}}
层次遍历2叉树，是从根结点开始遍历，按层次次序“自上而下，从左至右”访问树中的各结点。
为保证是按层次遍历，必须设置1个队列。
设T是指向根结点的指针变量，层次遍历非递归算法是：
若2叉树为空，则返回；否则，令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; /* 左结点入队 */
}
}
}
“遍历”是2叉树最重要的基本操作，是各种其它操作的基础，2叉树的许多其它操作都可以通过遍历来实现。如建立2叉树的存储结构、求2叉树的结点数、求2叉树的深度等。
2叉树的扩充方法是：在2叉树中结点的每个空链域处增加1个扩充的结点(总是叶子结点，用方框“□”表示)。对2叉树的结点值：
◆ 是char类型：扩充结点值为“？”或“#”；
◆ 是int类型：扩充结点值为0或⑴；
下面的算法是2叉树的前序创建的递归算法，读入1棵2叉树对应的扩充2叉树的前序遍历的结点值序列。每读入1个结点值就进行分析：
◆ 若是扩充结点值：令根指针为NULL；
◆ 若是(正常)结点值：动态地为该指针分配1个结点，将该值赋给根结点，然后递归地创建根的左子树和右子树。
算法实现：
#define NULLKY ‘?’
#define MAX_NODE 50
typedef struct BTNode
{ char data ;
struct BTNode *Lchild , *Rchild ;
}BTNode ;
BTNode *Preorder_Create_BTree(BTNode *T)
/* 建立链式2叉树，返回指向根结点的指针变量 */
{ char ch ;
ch=getchar() ;
if (ch==NULLKY)
{ T=NULL; return(T) ; }
else
{
T=(BTNode *)malloc(sizeof(BTNode)) ;
T
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生，我编程，我富裕，记住wfuyu网，php教程，php学习，php手册，CMS模版制作
声明：本站大部分内容是作者原创，少部分收集于互联网供大家一起学习，原版权很多不明，如有侵权请联系本站，谢谢！
粤ICP备14040726号-1 2015-2020 程序员人生 版权所有
