304 lines
7.3 KiB
C++
304 lines
7.3 KiB
C++
#include <stdio.h>
|
||
#include <stdlib.h>
|
||
#define OK 1
|
||
typedef int Status;
|
||
typedef struct BiTNode
|
||
{
|
||
char data; // 结点数据域
|
||
struct BiTNode *lchild, *rchild; // 左右孩子指针
|
||
} BiTNode, *BiTree;
|
||
|
||
// 1、创建二叉链表：按先序次序输入二叉树中结点的值，创建二叉链表表示的二叉树T
|
||
// 例：建立课本P115图5.10(b)的二叉树——读入字符的顺序为：ABC##DE#G##F###(#表示空树)
|
||
BiTree Create(BiTree &T)
|
||
{
|
||
char ch;
|
||
printf("请输入一个字符:");
|
||
scanf("%c", &ch);
|
||
getchar(); // 清空缓冲区，把遗留的\n清除
|
||
|
||
// todo list //if: 如果输入的是’#’，则建立一棵空树
|
||
if (ch == '#')
|
||
{
|
||
T = NULL;
|
||
}
|
||
// else：否则，递归建立一个二叉树（注意：是按按先序次序创建的二叉树）
|
||
else
|
||
{
|
||
T = (BiTree)malloc(sizeof(BiTNode));
|
||
T->data = ch;
|
||
Create(T->lchild);
|
||
Create(T->rchild);
|
||
}
|
||
return T;
|
||
}
|
||
|
||
// 先序遍历二叉树
|
||
Status PreOrder(BiTree &T)
|
||
{
|
||
// todo list //if: 如果是空树，则返回
|
||
if (T == NULL)
|
||
{
|
||
return OK;
|
||
}
|
||
// else:否则，先访问根结点 (D)
|
||
else
|
||
{
|
||
printf("%c ", T->data);
|
||
// 前序遍历左子树 (L)
|
||
PreOrder(T->lchild);
|
||
// 前序遍历右子树 (R)
|
||
PreOrder(T->rchild);
|
||
}
|
||
return OK;
|
||
}
|
||
|
||
// 中序遍历二叉树
|
||
Status InOrder(BiTree &T)
|
||
{
|
||
// todo list //if: 如果是空树，则返回
|
||
if (T == NULL)
|
||
{
|
||
return OK;
|
||
}
|
||
// else:否则，先中序遍历左子树 (L)
|
||
else
|
||
{
|
||
InOrder(T->lchild);
|
||
// 访问根结点 (D)
|
||
printf("%c ", T->data);
|
||
// 中序遍历右子树 (R)
|
||
InOrder(T->rchild);
|
||
}
|
||
return OK;
|
||
}
|
||
|
||
// 后序遍历
|
||
Status PostOrder(BiTree &T)
|
||
{
|
||
// todo list //if: 如果是空树，则返回
|
||
if (T == NULL)
|
||
{
|
||
return OK;
|
||
}
|
||
// else:否则，先后序遍历左子树 (L)
|
||
else
|
||
{
|
||
PostOrder(T->lchild);
|
||
// 后序遍历右子树 (R)
|
||
PostOrder(T->rchild);
|
||
// 访问根结点 (D)
|
||
printf("%c ", T->data);
|
||
}
|
||
return OK;
|
||
}
|
||
|
||
// 层次遍历1
|
||
void LeverOrder(BiTree &T)
|
||
{
|
||
if (T == NULL)
|
||
{ // 处理空树，避免空指针访问
|
||
printf("二叉树为空！\n");
|
||
return;
|
||
}
|
||
// BT *Queue[100]; //队列
|
||
BiTree Queue[100]; // 队列
|
||
char ch;
|
||
int front = 0;
|
||
int rear = 0;
|
||
// 队列边界检查（新增：防止数组越界）
|
||
if (rear >= 100)
|
||
{
|
||
printf("队列已满，无法入队！\n");
|
||
return;
|
||
}
|
||
Queue[rear++] = T; // 根节点入队
|
||
while (front < rear) // 当队不空
|
||
{
|
||
ch = Queue[front]->data; // 出队队头元素
|
||
printf("%c ", ch);
|
||
if (Queue[front]->lchild)
|
||
{
|
||
if (rear >= 100)
|
||
{
|
||
printf("队列已满，左孩子无法入队！\n");
|
||
break;
|
||
}
|
||
Queue[rear++] = Queue[front]->lchild;
|
||
}
|
||
if (Queue[front]->rchild)
|
||
{
|
||
if (rear >= 100)
|
||
{
|
||
printf("队列已满，右孩子无法入队！\n");
|
||
break;
|
||
}
|
||
Queue[rear++] = Queue[front]->rchild;
|
||
}
|
||
front++; // 队头后移，完成出队
|
||
}
|
||
}
|
||
|
||
/*
|
||
|
||
// ------------- 循环队列结构体定义（层序遍历依赖队列） -------------
|
||
#define MAXQSIZE 100 // 队列最大容量
|
||
typedef struct {
|
||
BiTree base[MAXQSIZE]; // 队列存储二叉树结点指针
|
||
int front; // 队头指针
|
||
int rear; // 队尾指针
|
||
} SqQueue;
|
||
|
||
// 初始化队列
|
||
int InitQueue(SqQueue *qu) {
|
||
qu->front = qu->rear = 0; // 空队列：队头=队尾=0
|
||
return 1;
|
||
}
|
||
|
||
// 判断队列是否为空
|
||
int QueueEmpty(SqQueue *qu) {
|
||
return qu->front == qu->rear;
|
||
}
|
||
|
||
// 入队操作（将二叉树结点指针入队）
|
||
int enQueue(SqQueue *qu, BiTree p) {
|
||
// 判断队列是否满（循环队列判满条件）
|
||
if ((qu->rear + 1) % MAXQSIZE == qu->front) {
|
||
printf("队列满，入队失败！\n");
|
||
return 0;
|
||
}
|
||
qu->base[qu->rear] = p; // 结点指针入队
|
||
qu->rear = (qu->rear + 1) % MAXQSIZE; // 队尾指针后移
|
||
return 1;
|
||
}
|
||
|
||
// 出队操作（取出队头结点指针）
|
||
int deQueue(SqQueue *qu, BiTree *p) {
|
||
if (QueueEmpty(qu)) { // 队空则出队失败
|
||
printf("队列空，出队失败！\n");
|
||
return 0;
|
||
}
|
||
*p = qu->base[qu->front]; // 取出队头元素
|
||
qu->front = (qu->front + 1) % MAXQSIZE; // 队头指针后移
|
||
return 1;
|
||
}
|
||
|
||
// ------------- 层次遍历2 -------------
|
||
void LevelOrder(BiTree b) {
|
||
BiTree p;
|
||
SqQueue qu; // 定义队列（注意：原参考中qu是指针，此处改为直接定义结构体，更易理解）
|
||
|
||
if (b == NULL) return; // 空树直接返回
|
||
|
||
InitQueue(&qu); // 初始化队列
|
||
enQueue(&qu, b); // 根结点入队
|
||
|
||
while (!QueueEmpty(&qu)) { // 队列非空则循环
|
||
deQueue(&qu, &p); // 出队当前结点
|
||
printf("%c ", p->data); // 访问当前结点
|
||
|
||
// 左孩子非空则入队
|
||
if (p->lchild != NULL) {
|
||
enQueue(&qu, p->lchild);
|
||
}
|
||
// 右孩子非空则入队
|
||
if (p->rchild != NULL) {
|
||
enQueue(&qu, p->rchild);
|
||
}
|
||
}
|
||
}
|
||
*/
|
||
|
||
// 节点总数
|
||
int Count(BiTree &T)
|
||
{
|
||
// todo list //if：如果是空树，则结点个数为0；
|
||
if (T == NULL)
|
||
{
|
||
return 0;
|
||
}
|
||
// else：否则，结点个数为左子树的结点个数+右子树的结点个数再+1。
|
||
else
|
||
{
|
||
return Count(T->lchild) + Count(T->rchild) + 1;
|
||
}
|
||
}
|
||
// 叶子节点
|
||
int CountLeaf(BiTree &T)
|
||
{
|
||
// todo list //if：如果是空树，则叶子结点个数为0；
|
||
if (T == NULL)
|
||
{
|
||
return 0;
|
||
}
|
||
// else if：如果是叶子结点，则返回1；
|
||
else if (T->lchild == NULL && T->rchild == NULL)
|
||
{
|
||
return 1;
|
||
}
|
||
// else否则，为左子树的叶子结点个数+右子树的叶子结点个数。
|
||
else
|
||
{
|
||
return CountLeaf(T->lchild) + CountLeaf(T->rchild);
|
||
}
|
||
}
|
||
int main()
|
||
{
|
||
BiTree T = NULL; // 创建一颗空树
|
||
int choose = -1;
|
||
printf("*********************************************\n");
|
||
printf("********** 实验六 *******\n");
|
||
printf("*********************************************\n");
|
||
printf("********** 1.创建一棵二叉树 *******\n");
|
||
printf("********** 2.先序遍历二叉树 *******\n");
|
||
printf("********** 3.中序遍历二叉树 *******\n");
|
||
printf("********** 4.后序遍历二叉树 *******\n");
|
||
printf("********** 5.层序遍历二叉树 *******\n");
|
||
printf("********** 6.求二叉树节点个数 *******\n");
|
||
printf("********** 7.求二叉数叶子节点个数 *******\n");
|
||
printf("********** 0.退出 *******\n");
|
||
printf("*********************************************\n");
|
||
while (choose)
|
||
{
|
||
printf("\n");
|
||
printf("请输入你的选择项：");
|
||
scanf("%d", &choose);
|
||
getchar(); // 清空缓冲区，把遗留的\n清除
|
||
switch (choose)
|
||
{
|
||
case 1:
|
||
T = Create(T);
|
||
break; // 创建
|
||
printf("\n");
|
||
case 2:
|
||
printf("先序序列为：");
|
||
PreOrder(T);
|
||
break; // 先序遍历二叉树
|
||
printf("\n");
|
||
case 3:
|
||
printf("中序序列为：");
|
||
InOrder(T);
|
||
break; // 中序遍历二叉树
|
||
printf("\n");
|
||
case 4:
|
||
printf("后序序列为：");
|
||
PostOrder(T);
|
||
break; // 后序遍历二叉树
|
||
printf("\n");
|
||
case 5:
|
||
printf("层次序列为：");
|
||
LeverOrder(T);
|
||
break; // 层序遍历二叉树
|
||
printf("\n");
|
||
case 6:
|
||
printf("节点总数为：%d\n", Count(T));
|
||
break; // 结点总数
|
||
case 7:
|
||
printf("叶子节点总数为：%d\n", CountLeaf(T));
|
||
break; // 叶子结点总数
|
||
case 0:
|
||
exit(0);
|
||
break;
|
||
}
|
||
}
|
||
} |