因为非递归版需要用到 栈stack 的操作
#define SElemType BiTree
// -----栈的链式存储结构----------------------------------
typedef struct SNode {
SElemType data; // 数据域
struct SNode *next; // 指针域
} SNode, *LinkStack;
Status InitStack(LinkStack& S)
{
S = (LinkStack)malloc(sizeof(SNode));
if (!S)
return 0;
S->next = NULL;
}
Status DestroyStack(LinkStack& S)
{
LinkStack p = S->next, ptmp;
while (p) {
ptmp = p->next;
free(p);
p = ptmp;
}
free(S);
return 1;
}
Status ClearStack(LinkStack& S)
{
LinkStack p = S->next, ptmp;
while (p) {
ptmp = p->next;
free(p);
p = ptmp;
}
S->next = NULL;
return 1;
}
Status StackEmpty(LinkStack& S)
{
return S->next == NULL;
}
int StackLength(LinkStack S)
{
int ans = 0;
LinkStack p = S->next;
while (p) {
ans++;
p = p->next;
}
return ans;
}
Status GetTop(LinkStack S, SElemType& e)
{
if (S->next == NULL)
return 0;
e = S->next->data;
return 1;
}
Status Push(LinkStack& S, SElemType e)
{
SNode* p = (SNode*)malloc(sizeof(SNode));
p->data = e;
p->next = S->next;
S->next = p;
return 1;
}
Status Pop(LinkStack& S, SElemType& e)
{
if (S->next == NULL)
return 0;
e = S->next->data;
SNode* p = S->next;
S->next = p->next;
free(p);
return 1;
}
Status Visit(TElemType e){
cout << e << " ";
return 1;
}
具体实现请看：
2021-9-22【数据结构/严蔚敏】【顺序栈&链式栈&迷宫求解&表达式求值】【代码实现算法3.1-3.5】
二叉树的前序遍历
递归版
Status Visit(TElemType e){
cout << e;
return 1;
}
//先序遍历
//算法6.1
Status PreOrderTraverse(BiTree T,Status Visit(TElemType e)){
if(T){
Visit(T->data);
PreOrderTraverse(T->lchild, Visit);
PreOrderTraverse(T->rchild, Visit);
}
}
非递归版
//先序遍历
Status PreOrderTraverse1(BiTree T,Status Visit(TElemType e))
{
if (T == NULL)
return 0;
BiTree p;
LinkStack s;
InitStack(s);
Push(s, T);//根进栈
while (!StackEmpty(s))
{
while(GetTop(s,p) && p){
if(!Visit(p->data))
return 0;
Push(s, p->lchild); //左走到尽头
}
Pop(s, p); //空指针退栈
if(!StackEmpty(s)){
//访问结点
Pop(s, p);
Push(s, p->rchild);
}
}
return 1;
}
Status PreOrderTraverse2(BiTree T,Status Visit(TElemType e))
{
if (T == NULL)
return 0;
BiTree p = T, e;
LinkStack s;
InitStack(s);
while (p || !StackEmpty(s))
{
if(p){
//根指针进栈，遍历左子树
if(!Visit(p->data))
return 0;
Push(s, p);
p = p->lchild;
}else{
//根指针退栈，访问根结点，遍历右子树
Pop(s, p);
p = p->rchild;
}
}
return 1;
}
中序遍历
递归版
//中序遍历
Status InOrderTraverse(BiTree T,Status Visit(TElemType e)){
if(T!=NULL){
InOrderTraverse(T->lchild, Visit);
Visit(T->data);
InOrderTraverse(T->rchild, Visit);
}
}
非递归版
//中序非递归实现
//算法6.2
Status InOrderTraverse1(BiTree T,Status Visit(TElemType e))
{
if (T == NULL)
return 0;
BiTree p;
LinkStack s;
InitStack(s);
Push(s, T);//根进栈
while (!StackEmpty(s))
{
while(GetTop(s,p) && p){
Push(s, p->lchild); //左走到尽头
}
Pop(s, p); //空指针退栈
if(!StackEmpty(s)){
//访问结点
Pop(s, p);
if(!Visit(p->data))
return 0;
Push(s, p->rchild);
}
}
return 1;
}
//算法6.3
Status InOrderTraverse2(BiTree T,Status Visit(TElemType e))
{
if (T == NULL)
return 0;
BiTree p = T, e;
LinkStack s;
InitStack(s);
while (p || !StackEmpty(s))
{
if(p){
//根指针进栈，遍历左子树
Push(s, p);
p = p->lchild;
}else{
//根指针退栈，访问根结点，遍历右子树
Pop(s, p);
if(!Visit(p->data))
return 0;
p = p->rchild;
}
}
return 1;
}
后序遍历
递归版
//后序遍历
Status PostOrderTraverse(BiTree T,Status Visit(TElemType e)){
if(T!=NULL){
PostOrderTraverse(T->lchild, Visit);
PostOrderTraverse(T->rchild, Visit);
Visit(T->data);
}
}
非递归版
//后序非递归
Status PostOrderrTraverse2(BiTree T, Status(*Visit)(TElemType e))
{
if (T == NULL)
return 0;
BiTree p = T, r = NULL;
LinkStack s;
InitStack(s);
while ( p != NULL || !StackEmpty(s))
{
if (p) {
Push(s, p);
p = p->lchild;
}
else
{
GetTop(s, p);
if (p->rchild && p->rchild != r) {
p = p->rchild;
Push(s, p);
p = p->lchild;
}
else
{
Pop(s, p);
Visit(p->data);
r = p;
p = NULL;
}
}
}
return 1;
}
层序遍历
层序遍历需要使用队列queue
//层次遍历
#define QElemType BiTree
#define Status int
//---------链队列实现--------------
typedef struct QNode{
QElemType data;
struct QNode *next;
} QNode, *QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
} LinkQueue;
Status QueueEmpty(LinkQueue Q){
if (Q.front == Q.rear)
return 1;
else
return 0;
}
Status InitQueue(LinkQueue &Q){
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if (!Q.front)
exit(_OVERFLOW);
Q.front->next = NULL;
return 1;
}
Status EnQueue(LinkQueue &Q, QElemType e){
QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
if (!p)
exit(_OVERFLOW);
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return 1;
}
Status DeQueue(LinkQueue &Q, QElemType &e){
QueuePtr p;
if (Q.front == Q.rear)
return 0;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p)
Q.rear = Q.front;
free(p);
return 1;
}
具体实现请看：
2021-9-27【数据结构/严蔚敏】【链队列】
代码实现
Status LevelOrderTraverse(BiTree &T){
LinkQueue lq;
InitQueue(lq);
QElemType q;
EnQueue(lq, T);
while (QueueEmpty(lq) != 1){
//队列不空，则出队
DeQueue(lq, q);
printf("%c ", q->data);
if(q->lchild)
EnQueue(lq, q->lchild); //若有左孩子，则入队
if(q->rchild)
EnQueue(lq, q->rchild); //若有右孩子，则入队
}
return 1;
}
int main(){
printf("测试代码\n");
BiTree T;
T = (BiTree)malloc(sizeof(BiTNode));
printf("请给二叉树按照先序方式依次输入结点的值(空结点为#):\n");
CreateBiTree(T);
printf("层序方式遍历结果：\n");
LevelOrderTraverse(T);
printf("\n");
return 0;
}
京公网安备 11010502036488号