二叉树——遍历按层次非递归遍历、先序非递归、先后序递归遍历二叉树的链表结构C语言，数据结构内含源代码

  前言：

因为本次实验二叉树考察的内容太多了，所以我把它拆分成了三个部分，分别是建立，处理，遍历三个板块，三篇文章可以在我的博客或专栏中找到。

以下是链接

二叉树递归总头文件：

http://t.csdn.cn/Vxst3

建立包含以下内容：

http://t.csdn.cn/YxBdf

二叉树结构，二叉树的三种建立。

遍历包含以下内容：

http://t.csdn.cn/RD8nQ

按层次非递归遍历、先序非递归、先中后序递归遍历二叉树的链表结构

处理包含以下内容：

http://t.csdn.cn/K3k4y

求二叉树的高度、叶节点数、单分支节点数、双分支节点数，交换左右子树

目录

前言：

遍历时用到的打印函数：

二叉树的递归遍历：

先序遍历：

中序遍历：

后序遍历：

二叉树的特殊遍历：

按层次非递归遍历：

先序非递归遍历二叉树：

栈头文件：

队列头文件：

遍历时用到的打印函数：

这个打印函数会作为一个函数指针出现在遍历函数中，作为遍历的输出手段

1.  
   Status print(TElemType e) {
2.  
   //打印方式
3.  
   printf("%c ", e);
4.  
   return OK;
5.  
   }

二叉树的递归遍历：

先序遍历：

1.  
   Status TraverseBiTree_Pre(BiTree T, Status(*print)(TElemType)) {
2.  
   //先序遍历二叉树
3.  
   if(T) {
4.  
   if(print(T->data)) {
5.  
   if(TraverseBiTree_Pre(T->lchild, print)) {
6.  
   if(TraverseBiTree_Pre(T->rchild, print)) {
7.  
   return OK;
8.  
   }
9.  
   }
10.  
    }
11.  
    return ERROR;
12.  
    }
13.  
    return OK;
14.  
    }

中序遍历：

1.  
   Status TraverseBiTree_In(BiTree T, Status(*print)(TElemType)) {
2.  
   //中序遍历二叉树
3.  
   if(T) {
4.  
   if(TraverseBiTree_In(T->lchild, print)) {
5.  
   if(print(T->data)) {
6.  
   if(TraverseBiTree_In(T->rchild, print)) {
7.  
   return OK;
8.  
   }
9.  
   }
10.  
    }
11.  
    return ERROR;
12.  
    }
13.  
    return OK;
14.  
    }

后序遍历：

1.  
   Status TraverseBiTree_Post(BiTree T, Status(*print)(TElemType)) {
2.  
   //后序遍历二叉树
3.  
   if(T) {
4.  
   if(TraverseBiTree_In(T->lchild, print)) {
5.  
   if(TraverseBiTree_In(T->rchild, print)) {
6.  
   if(print(T->data)) {
7.  
   return OK;
8.  
   }
9.  
   }
10.  
    }
11.  
    return ERROR;
12.  
    }
13.  
    return OK;
14.  
    }

二叉树的特殊遍历：

按层次非递归遍历：

这里需要用到队列，队列的头文件我会附在文章末

1.  
   typedef BiTree QElemType;
2.  
   #include "ArrayQueue.h"
3.  
    
4.  
   Status TraverseBiTree_Level(BiTree T, Status(*print)(TElemType)) {
5.  
   //层序遍历二叉树
6.  
   if(T) {
7.  
   ArrayQueue Q;
8.  
   InitQueue(&Q);
9.  
   EnQueue(&Q, T);
10.  
    while(!QueueEmpty(Q)) {
11.  
    DeQueue(&Q, &T);
12.  
    print(T->data);
13.  
    if(T->lchild) {
14.  
    EnQueue(&Q, T->lchild);
15.  
    }
16.  
    if(T->rchild) {
17.  
    EnQueue(&Q, T->rchild);
18.  
    }
19.  
    }
20.  
    }
21.  
    return OK;
22.  
    }

先序非递归遍历二叉树：

这里需要用到栈，栈的头文件我会附在文章末

1.  
   typedef BiTree SElemType;
2.  
   #include "Stack.h"
3.  
    
4.  
   Status TraverseBiTree_NRPre(BiTree T, Status(*print)(TElemType)) {
5.  
   //非递归先序遍历二叉树
6.  
   if(T) {
7.  
   SqStack S;
8.  
   InitStack(&S);
9.  
   while(T || !StackEmpty(S)) {
10.  
    if(T) {
11.  
    Push(&S, T);
12.  
    print(T->data);
13.  
    T = T->lchild;
14.  
    } else {
15.  
    Pop(&S, &T);
16.  
    T = T->rchild;
17.  
    }
18.  
    }
19.  
    }
20.  
    return OK;
21.  
    }

栈头文件：

1.  
   #include <stdio.h> //头文件
2.  
   #include <stdlib.h>
3.  
   #include <malloc.h>
4.  
   #include <conio.h>
5.  
   #include <string.h>
6.  
    
7.  
   #define TRUE 1 //函数结果状态码
8.  
   #define FALSE 0
9.  
   #define ERROR 0
10.  
    #define OK 1
11.  
    #define EQUAL 1
12.  
    #define OVERFLOW -1
13.  
    #define INFEASIBLE -2
14.  
    #define STACK_INIT_SIZE 100 //存储空间初始分配量
15.  
    #define STACKINCREMENT 10 //存储空间分配增量
16.  
    #define LIST_INIT_SIZE 100 //顺序表存储空间的初始分配量
17.  
    #define LISTINCREMENT 10 //顺序表存储空间的分配增量
18.  
     
19.  
    typedef int Status; //Status 为函数返回值类型，其值为函数结果状态代码
20.  
     
21.  
     
22.  
     
23.  
    typedef struct { //栈的顺序存储表示
24.  
    SElemType *base; //栈构造之前和销毁之后，其值为NULL
25.  
    SElemType *top; //栈顶指针
26.  
    int stacksize; //当前已分配的存储空间
27.  
    } SqStack;
28.  
     
29.  
    Status InitStack(SqStack *); //栈初始化
30.  
    Status DestroyStack(SqStack *); //销毁栈
31.  
    Status StackEmpty(SqStack); //栈判空
32.  
    Status GetTop(SqStack, SElemType *); //取栈顶元素
33.  
    Status Push(SqStack *, SElemType); //入栈
34.  
    Status Pop(SqStack *, SElemType *); //出栈
35.  
    Status StackTraverse(SqStack); //遍历栈，输出每个数据元素
36.  
     
37.  
    Status InitStack(SqStack *S) {
38.  
    //构造一个空栈Ss
39.  
    S->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
40.  
    if(!S->base) {
41.  
    //存储分配失败
42.  
    exit(OVERFLOW);
43.  
    }
44.  
    S->top = S->base;
45.  
    S->stacksize = STACK_INIT_SIZE;
46.  
    return OK;
47.  
    }//InitStack
48.  
     
49.  
    Status GetTop(SqStack S, SElemType *e) {
50.  
    //若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
51.  
    if(S.top == S.base) {
52.  
    return ERROR;
53.  
    }
54.  
    *e = *(S.top - 1);
55.  
    return OK;
56.  
    }//GetTop
57.  
     
58.  
    Status Push(SqStack *S, SElemType e) {
59.  
    //插入元素e为新的栈顶元素
60.  
    if(S->top - S->base >= S->stacksize) {
61.  
    //栈满，追加存储空间
62.  
    S->base = (SElemType *)realloc(S->base, (S->stacksize STACKINCREMENT) * sizeof(SElemType));
63.  
    if(!S->base) {
64.  
    //存储分配失败
65.  
    exit(OVERFLOW);
66.  
    }
67.  
    S->top = S->base S->stacksize;
68.  
    S->stacksize = STACKINCREMENT;
69.  
    }
70.  
    *S->top = e;
71.  
    return OK;
72.  
    }//Push
73.  
     
74.  
    Status Pop(SqStack *S, SElemType *e) {
75.  
    //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROE
76.  
    if(S->top == S->base) {
77.  
    return ERROR;
78.  
    }
79.  
    *e = *(--S->top);
80.  
    return OK;
81.  
    }//Pop
82.  
     
83.  
    Status DestoryStack(SqStack *S) {
84.  
    //销毁栈S
85.  
    if(S->base) {
86.  
    free(S->base);
87.  
    }
88.  
    S->top = S->base = NULL;
89.  
    return OK;
90.  
    }//DestroyStack
91.  
     
92.  
    //Status StackTraverse(SqStack S) {
93.  
    // //遍历栈，输出每一个数据元素
94.  
    // SElemType *p = S.base;
95.  
    // int i = 0;
96.  
    // if(S.base == S.top) {
97.  
    // printf("Stack is Empty.\n");
98.  
    // return OK;
99.  
    // }
100.  
     // while(p < S.top) {
101.  
     // printf("[%d:%d,%d]", i, p->i, p->j);
102.  
     // p ;
103.  
     // }
104.  
     // printf("\n");
105.  
     // return OK;
106.  
     //}//StackTraverse
107.  
      
108.  
     Status StackEmpty(SqStack S) {
109.  
     //栈判空
110.  
     if(S.base == S.top) {
111.  
     return OK;
112.  
     }
113.  
     return ERROR;
114.  
     }

队列头文件：

1.  
   //#inclue <conio.h>
2.  
   //#include <stdio.h>
3.  
   #include <stdlib.h>
4.  
   #define TRUE 1 //函数结果状态码
5.  
   #define FALSE 0
6.  
   #define OK 1
7.  
   #define ERROR 0
8.  
   #define OVERFLOW -1
9.  
   #define INFEASIBLE -2
10.  
     
11.  
    typedef int Status; //Status 为函数返回值类型，其值为函数结果状态代码
12.  
     
13.  
    typedef struct {
14.  
    QElemType *base; //初始化的动态分配存储空间
15.  
    int front; //队头指针
16.  
    int rear; //队尾指针
17.  
    int length; //队列总长度
18.  
    } ArrayQueue;
19.  
     
20.  
    Status InitQueue(ArrayQueue *); //构造一个空队列Q
21.  
    Status DestroyQueue(ArrayQueue *); //销毁队列Q，Q不再存在
22.  
    Status ClearQueue(ArrayQueue *); //将Q清为空队列
23.  
    Status QueueEmpty(ArrayQueue ); //若队列Q为空，则返回TRUE，否则返回FALSE
24.  
    int QueueLength(ArrayQueue ); //返回Q的元素个数，即为队列的长度
25.  
    Status GetHead(ArrayQueue, QElemType *); //若队列不为空，则用e返回Q的队头元素，并返回OK；头则返回ERROR
26.  
    Status EnQueue(ArrayQueue *, QElemType); //插入元素e为Q的新的队尾元素
27.  
    Status DeQueue(ArrayQueue *, QElemType *); //若队列不为空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR；
28.  
    //Status QueueTraverse(ArrayQueue, visit()); //从队头到队尾依次对队列Q中的每一个元素调用visit()。一旦visit失败，则操作失败；
29.  
     
30.  
    Status InitQueue(ArrayQueue *Q) {
31.  
    //构造一个空队列Q
32.  
    Q->length = 100;
33.  
    Q->base = (QElemType *)malloc(Q->length * sizeof(QElemType));
34.  
    if(!Q->base) {
35.  
    exit(OVERFLOW);
36.  
    }
37.  
    Q->front = Q->rear = 0;
38.  
    return OK;
39.  
    }
40.  
     
41.  
    Status DestroyQueue(ArrayQueue *Q) {
42.  
    //销毁队列Q，Q不再存在
43.  
    free(Q->base);
44.  
    return OK;
45.  
    }
46.  
     
47.  
    Status QueueEmpty(ArrayQueue Q) {
48.  
    //若队列Q为空，则返回TRUE，否则返回FALSE
49.  
    if(Q.front == Q.rear) {
50.  
    return TRUE;
51.  
    }
52.  
    return FALSE;
53.  
    }
54.  
     
55.  
    int QueueLength(ArrayQueue Q) {
56.  
    //返回Q的元素个数，即为队列的长度
57.  
    return Q.rear - Q.front;
58.  
    }
59.  
    Status GetHead(ArrayQueue Q, QElemType *e) {
60.  
    //若队列不为空，则用e返回Q的队头元素，并返回OK；头则返回ERROR
61.  
    if(Q.front == Q.rear) {
62.  
    return ERROR;
63.  
    }
64.  
    *e = Q.base[Q.front];
65.  
    return OK;
66.  
    }
67.  
    Status EnQueue(ArrayQueue *Q, QElemType e) {
68.  
    //插入元素e为Q的新的队尾元素
69.  
    if(Q->rear == Q->length - 1) {
70.  
    //队列满
71.  
    Q->length = 100;
72.  
    Q->base = (QElemType *)realloc(Q->base, Q->length * sizeof(QElemType));
73.  
    }
74.  
    Q->base[Q->rear] = e;
75.  
    Q->rear ;
76.  
    return OK;
77.  
    }
78.  
    Status DeQueue(ArrayQueue *Q, QElemType *e) {
79.  
    //若队列不为空，则删除Q的队头元素，用e返回其值，并返回OK；
80.  
    //否则返回ERROR；
81.  
    if(Q->front == Q->rear) {
82.  
    return ERROR;
83.  
    }
84.  
    *e = Q->base[Q->front];
85.  
    Q->front ;
86.  
    return OK;
87.  
    }

这篇好文章是转载于：学新通技术网