第四章_树（遍历二叉树）
遍历二叉树，最常用的递归实现遍历二叉树，但我们还可以用非递归和层次遍历树的方法，这里就要用到栈和队列的一些知识，现在就让我们把这两个结合起来一起用。
这个是非递归中序遍历二叉树，非递归我们可以用栈的思想，中序遍历的时候，我们可以先一直把左子树全装栈里面，然后当装完左子树的结点后，我们就出栈并输出，然后跳到右子树，依次循环，对应的代码如下：
#include <stdio.h>
#include <stdlib.h>
typedef struct TNode {
int data;
struct TNode *lchild;//left child
struct TNode *rchild;//right child
}TNode,*Tree;
typedef struct SNode {
Tree data;
int top;
int maxsize;
}SNode,*Stack;
void InitStack (Stack *S);//初始化栈
void CreateTree (Tree *T);//创建一个二叉树。
void Pre (Tree T);//先序遍历二叉树。
void Pre1 (Tree T);//非递归中序遍历二插树。
void Push (Stack S, Tree T);//进栈。
Tree Pop (Stack S);//出栈。
int IsFull (Stack S);//判断是否为满。
int IsEmpty (Stack S);//判断是否为空。
int main ()
{
Tree T;
CreateTree(&T);//传入T的地址。
Pre(T);
Pre1 (T);
return 0;
}
void Pre1 (Tree T)
{
Stack S;
InitStack(&S);
while(T || !IsEmpty (S)) {
while (T) {
Push(S,T);
T = T->lchild;//先装完左子树的全部结点。
}
if(!IsEmpty(S)) {//装完后，我们就可以出栈了。
T = Pop (S);
printf(“%d “,T->data);//输出对应的结点数据。
T = T->rchild;//跳到右子树。
}
}
}
void InitStack (Stack *S)
{
*S = (SNode*) malloc(sizeof(SNode));
(*S)->top = 0;
(*S)->maxsize = 10;
(*S)->data = (TNode*)malloc(sizeof(TNode)*(*S)->maxsize);
}
int IsFull( Stack S)
{
return (S->top == S->maxsize – 1);
}
int IsEmpty (Stack S)
{
return (S->top == 0);
}
void Push (Stack S, Tree T)
{
if(IsFull(S)) {
printf(“The stack is Full\n”);
}else {
TNode *temp;
temp = T;
S->data[S->top] = *temp;
S->top++;
}
}
Tree Pop (Stack S)
{
if(IsEmpty (S)) {
printf(“The stack is empty\n”);
}else {
Tree T;
S->top–;
T = &(S->data[S->top]);
return T;
}
}
void Pre (Tree T)
{
if (T) {
printf(“%d “,T->data);
Pre(T->lchild);
Pre(T->rchild);
}
}
void CreateTree (Tree *T)
{
*T = (TNode*) malloc(sizeof(TNode));
int data;
scanf(“%d”,&data);
if( data == -1) {
*T = NULL;
}else {
(*T)->data = data;
CreateTree(&(*T)->lchild);
CreateTree(&(*T)->rchild);
}
}
下面就是层次遍历，层次遍历就是利用队列的思想，先进先出，以树的第一个为起点，开始输出，输出后，若有左右子树，则进队，若没有，则依次出队，再入队，依次循环。直到队列为空。
#include <stdio.h>
#include <stdlib.h>
typedef struct TNode {
int data;
struct TNode *lchild;
struct TNode *rchild;
}TNode,*Tree;
typedef struct QNode {
Tree data;
int top;
int base;
int maxsize;
}QNode,*Queue;
void InitQueue (Queue *q);//初始化队列。
void En (Queue q, Tree T);//进队。
Tree De (Queue q);//出队。
int IsFull (Queue q);//判断是否为满。
int IsEmpty (Queue q);//判断是否为空。
void CreateTree (Tree *T);//创建一颗二插树。
void Level (Tree T);//层次遍历二叉树。
int main ()
{
Tree T;
CreateTree(&T);
Level(T);
return 0;
}
void CreateTree (Tree *T)
{
*T = (Tree) malloc (sizeof(TNode));
int data;
scanf(“%d”,&data);
if (data == -1 ) {
*T = NULL;
}else {
(*T)->data = data;
CreateTree(&(*T)->lchild);
CreateTree(&(*T)->rchild);
}
}
void Level (Tree T)
{
Queue q;
InitQueue (&q);
En(q,T);
Tree temp;
while(!IsEmpty(q)) {//队列为空则停止。
temp = De(q);//出队。
printf(“%d “,temp->data);
if(temp->lchild) En(q,temp->lchild);//依次装入左右子树。
if(temp->rchild) En(q,temp->rchild);
}
}
void InitQueue (Queue *q)
{
(*q) = (QNode*) malloc(sizeof(QNode));
(*q)->top = (*q)->base = 0;
(*q)->maxsize = 10;
(*q)->data = (Tree) malloc(sizeof(TNode) * (*q)->maxsize);
}
int IsFull(Queue q)
{
return ((q->top + 1) % (q->maxsize – 1) == q->base);
}
int IsEmpty (Queue q)
{
return (q->base == q->top);
}
void En (Queue q, Tree T)
{
if (IsFull(q)) {
printf(“The queue is full!\n”);
}else {
TNode *temp;
temp = T;
q->data[q->top] = *temp;
q->top = (q->top + 1) % (q->maxsize -1 );
}
}
Tree De (Queue q)
{
if(IsEmpty(q)) {
printf(“The queue is empty!\n”);
}else {
Tree T;
T = &(q->data[q->base]);
q->base = (q->base + 1) % (q->maxsize – 1);
return T;
}
}
这就是树的一些遍历技巧，我们要能掌握并灵活的运用，若读者有不懂的，可以留言，期待下一次！