王道计算机考研 数据结构
二叉树的 先序，中序，后序，层次遍历（层次遍历找bug找了一下午，结果传队列进去只传的是数据域，应该传结点进去）希望对大家有用
#include <stdio.h>
#include <stdlib.h>
#define Elemtype char
typedef struct BiTNode
{
Elemtype data;
struct BiTNode *lchild;
struct BiTNode *rchild;
} BiTNode, *BiTree;
// 链式队列结点
typedef struct LinkNode
{
BiTNode *data;
struct LinkNode *next;
} LinkNode;
// 链式队列
typedef struct
{
LinkNode *head;
LinkNode *rear;
} LinkQueue;
// 初始化队列
void InitQueue(LinkQueue &Q)
{
Q.head = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
Q.head->next = NULL;
}
// 入队
void EnQueue(LinkQueue &Q, BiTNode *x) //让结点入队所以传结点BiTNode *x
{
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = (BiTNode *)malloc(sizeof(BiTNode));
s->data = x;
s->next = NULL;
Q.rear->next = s; // 新结点插入到rear之后
Q.rear = s; // 修改表尾指针
}
// 出队
bool DeQueue(LinkQueue &Q, BiTNode *&x) //让结点出队所以传出（用&引用出来）的应该是结点（而不是单纯的数据域！！！）
{
if (Q.head == Q.rear) // 空队
return false;
LinkNode *p = Q.head->next; // p指向队首
// p->data = (BiTNode *)malloc(sizeof(BiTNode));
x = p->data; // 用x返回队首元素
Q.head->next = p->next; // 修改头结点的头指针
if (Q.rear == p) // 此次是最后一个结点出队
Q.rear = Q.head; // 修改rear指针
free(p);
return true;
}
// 判断队列是否为空
bool isEmpty(LinkQueue Q)
{
if (Q.head == Q.rear)
return true;
else
return false;
}
// 创建二叉树
BiTree
CreateTree()
{
BiTNode *root;
Elemtype ch;
scanf("%c", &ch); // 通过输入的ch是否为特殊符号来判断该节点是否有孩子节点
if (ch == '#') // 不存在孩子节点
return NULL;
else
{
root = (BiTNode *)malloc(sizeof(BiTNode));
if (root == NULL)
{
printf("Created false\n");
return NULL;
}
root->data = ch;
root->lchild = CreateTree(); // 存放左孩子结点，递归调用本函数，使得左孩子结点先被赋值
root->rchild = CreateTree();
return root;
}
}
// 访问根节点
Elemtype Vist(BiTree T)
{
printf("%c", T->data);
return T->data;
}
// 先序遍历
void PreOrder(BiTree T)
{
if (T != NULL)
{
Vist(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
// 中序遍历
void InOrder(BiTree T)
{
if (T != NULL)
{
InOrder(T->lchild);
Vist(T);
InOrder(T->rchild);
}
}
// 后序遍历
void PostOrder(BiTree T)
{
if (T != NULL)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
Vist(T);
}
}
// 层次遍历
void LevelOrder(BiTree T)
{
LinkQueue Q;
InitQueue(Q); // 初始化辅助队列
BiTree p;
p = T;
EnQueue(Q, T); // 将根结点入队
while (!isEmpty(Q)) // 队列不空则循环
{
DeQueue(Q, p); // 队头结点出队
Vist(p); // 访问出队结点
if (p->lchild != NULL)
EnQueue(Q, p->lchild); // 左孩子入队
if (p->rchild != NULL)
EnQueue(Q, p->rchild); // 右孩子入队
}
}
// 后序遍历的应用
// 求树的深度
int TreeDepth(BiTree T)
{
if (T == NULL)
{
return 0;
}
else
{
int l = TreeDepth(T->lchild);
int r = TreeDepth(T->rchild);
// 树的深度=max(左子树的深度，右子树的深度)+1（根节点独占一个深度）
return l > r ? l + 1 : r + 1;
}
}
void test()
{
BiTree T;
printf("Please enter a binarytree ('#' is NULL):");
T = CreateTree(); // 用Createtree建立出来树（结构体），赋值给T，下面才能用T进行遍历操作
if (T != NULL)
{
// printf("The PreOrder is :\n");
// PreOrder(T);
// printf("\n");
// printf("The InOrder is:\n");
// InOrder(T);
// printf("\n");
// printf("The PostOrder is:\n");
// PostOrder(T);
// printf("\n");
printf("The LevelOrder is :\n");
LevelOrder(T);
printf("\n");
// printf("The binarytree's depth is %d\n", TreeDepth(T));
}
else
printf("Created false\n");
}
int main()
{
test();
return 0;
}
