二叉树的四种遍历方法和两种求深度的方法

3677次浏览 |630点赞 | 854评论 | 2020-08-01 06:06 更新

来源：互联网

最佳文档

本文由作者推荐

岷的读音-校书郎

二叉树的四种遍历方法和两种求深度的方法.txt等余震的心情，就像初恋的少女等情人，既怕他不来，又怕他乱来。听说女人如衣服，兄弟如手足，回想起来，我竟然七手八脚地裸奔了二十多年！今天心情不好，我只有四句话想说，包括这句和前面的两句，我的话说完了！二叉树的四种遍历方法和两种求深度的方法

用到了以前学的栈和队列的知识，也算是一种复习。不过用到栈来求深度的时候，改变了二叉树，不知道如何去避免？

// 二叉树.cpp : 定义控制台应用程序的入口点。

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"

typedef struct BiTNode{ //二叉树结构
int data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

#define STACK_INIT_SIZE 100
#define STACKINGMENT 10

int CreateBiTree( BiTNode **T ) //用先序顺序建立二叉树
{
char c;
if( (c = getchar()) == '#')
*T = NULL;
else
{
if(!(*T = (BiTree)malloc(sizeof(BiTNode))))
{
printf("ERROR!");
return 0;
}
(*T)->data = c;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
return 0;

}

int PrintfElement( int e )
{
printf("%c",e);
return 1;
}

int PreOrderTraverse(BiTree T,int (* PrintfElement)(int e)) //先序遍历二叉树的递归方法
{
if(T) //访问根结点
{
if(PrintfElement(T->data))
if(PreOrderTraverse(T->lchild,PrintfElement)) //先序遍历左子树
if(PreOrderTraverse(T->rchild,PrintfElement)) //先序遍历右子树
return 1;
return 0;
}
else
return 1;
}

int InOrderTraverse(BiTree T,int (*PrintfElement)(int)) //中序遍历二叉树的递归方法
{
if(T)
{
if(InOrderTraverse(T->lchild, PrintfElement))
if(PrintfElement(T->data))
if(InOrderTraverse(T->rchild, PrintfElement))
return 1;
return 0;
}
else
return 1;
}

int PostOrderTraverse(BiTree T, int (*PrintfElement)(int) ) //后序遍历二叉树的递归方法
{
if(T)
{
if(PostOrderTraverse(T->lchild, PrintfElement))
if(PostOrderTraverse(T->rchild, PrintfElement))
if(PrintfElement(T->data))
return 1;
return 0;
}
else
return 1;
}

/*typedef struct{ //栈
BiTree * base;
BiTree * top;
int stacksize;
}SqStack;

int InitStack(SqStack **s) //建立空栈
{
(*s)->base = (BiTree*)malloc(STACK_INIT_SIZE * sizeof(BiTNode*));
if(!((*s)->base))
return 0;
(*s)->top = (*s)->base;
(*s)->stacksize = (*s)->stacksize;
return 0;
}

int Push(SqStack *s, BiTree T) //压栈
{
if(s->top - s->base >= STACK_INIT_SIZE)
{
s->base = (BiTree*)realloc(s->base,(STACK_INIT_SIZE + STACKINGMENT) + sizeof(BiTNode*));
s->top = s->base + STACK_INIT_SIZE;
s->stacksize += STA
CK_INIT_SIZE;
}
*s->top++ = T;
return 0;
}

BiTree Pop(SqStack *s,BiTree T) //出栈, 后返回栈顶元素
{
if(s->base == s->top)
{
printf("已空！");
return 0;
}
T = * (-- s->top -1);
return T;
}

// 此方法过后二叉树就被改变了。
int DeepBiTree(BiTree T) //二叉树的深度
{
BiTree p = T;
SqStack *s, a;
int deep = 1,max = 0,k = 0,b = -2,i = 0,j = 0;
s = &a;
InitStack(&s);
Push(s, T);
if(T->rchild == NULL)
b++;
while(b)
{
if(p->lchild)
{
if(0 == k)
{
p = p->lchild;
j = 1; //表记走过左子树
}
else
{
p = p->rchild;
k = 0;
i = 1;
}
Push(s,p);
deep++;
if(deep > max)
max = deep;
}
else
{
if(p->rchild != NULL)
{
i = 1;
p = p->rchild;
Push(s,p);
deep++;
if(deep > max)
max = deep;
}
else
{
p = Pop(s,p);
deep--;
k = 1;
if(i) //把走过的子树置为空，以后不再走
p->rchild = NULL;
if(j)
p->lchild = NULL;
i = j = 0;
}
}
if(p == T)
b++;
}
free(s->base);
return max;
}*/
int DeepBiTree(BiTree T) //求二叉树的深度
{

int ldeep,rdeep;
if(!T)
return 0; //空二叉子树深度为0
else
{
ldeep = DeepBiTree(T->lchild); //先序遍历二叉树谨记：递归是把问题分解成一个最小的单元，例如这里求二叉树的深度就是
rdeep = DeepBiTree(T->rchild); //左二叉子树的深度和右二叉子树的深度作比较，取大的那个加一就是此二叉树的深度。
}
if(ldeep > rdeep) //ldeep就是每个“二叉树”的左子树深度。
return ldeep + 1; //rdeep就是每个“二叉树”的右子树深度。
else
return rdeep + 1;
}

typedef struct QNode{
BiTree data;
struct QNode *next;
}QNode, *QueuePtr;

typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;

int InitQueue(LinkQueue **Q) //建立空队列
{
(*Q)->rear = (*Q)->front = (QueuePtr)malloc(sizeof(QNode));//给对头分配空间
if(!(*Q)->front)
return 0;
(*Q)->front->next= NULL; //队尾指向空
return 0;
}

int DestoryQueue(LinkQueue *Q)
{
while(Q->front) //对头不为空则继续删除
{
Q->rear = Q->front->next; //保留对头后一个队员，留出对头以便删除
free(Q->front); //删除原对头结点
Q->front = Q->rear; //指向新对头
}
return 0;
}

int EnQueue(LinkQueue *Q, BiTree T) //插入新队员切记队列在队尾插
入。
{
QueuePtr p;
if(!(p = (QueuePtr)malloc(sizeof(QNode)))) //生成新结点(不要搞错结点的类型)
return 0;
p->data = T; //给新结点赋值
p->next = NULL; //新结点指向空
Q->rear->next = p; //队尾指向新结点
Q->rear = p; //新队尾既是刚插入的结点
return 0;
}

BiTree DeQueue(LinkQueue *Q, BiTree T) //在对头删除
{
QueuePtr p = Q->front->next; // 辅助指针标记要删除的队员
if(Q->front == Q->rear) //空队列不予删除
{
printf("队列已空，无法删除！
");
return 0;
}
T = p->data; //提取要删除的队员
Q->front->next = p->next; //删除对头结点
if(Q->rear == p) //若队列已空
Q->rear = Q->front; //则对头等于队尾
free(p); //删除结点
return T;
}

//队列使用注意：在对头删除，在队尾插入，对头没有指向数据，而队尾有，空队列对头等于队尾。

int LevelOrderTraverse(BiTree T, int (*PrintfElement)(int)) //层序遍历二叉树
{
LinkQueue *Q, a;
Q = &a;
BiTree p = T;
InitQueue(&Q);
if(!T) //空二叉树结束
return 0;
PrintfElement(p->data); //首先输出根结点
if(p->lchild) //若左孩子存在则把左孩子插入队列
EnQueue(Q, p->lchild);
if(p->rchild) //若右孩子存在则把右孩子插入队列
EnQueue(Q, p->rchild);
while(Q->front != Q->rear) //队列不为空
{
p = DeQueue(Q, p); //删除对头
PrintfElement(p->data); //输出结点
if(p->lchild) //同上
EnQueue(Q, p->lchild);
if(p->rchild)
EnQueue(Q, p->rchild);
}
DestoryQueue(Q); //销毁队列
return 0;
}

int main()
{
int (*p)(int) //函数类型指针
int deep;
BiTree T;
BiTNode s;
T = &s;
p = PrintfElement;
printf("输入字符建立二叉树：");
CreateBiTree( &T );
printf("先序遍历输出二叉树:");
PreOrderTraverse(T,p);
printf("
中序遍历输出二叉树:");
InOrderTraverse(T, p);
printf("
后序遍历输出二叉树:");
PostOrderTraverse(T,p);
deep = DeepBiTree(T);
printf("
二叉树的深度：%d
",deep);
printf("层序遍历输出二叉树;");
LevelOrderTraverse(T,p);
return 0;
}