#include "stdafx.h"
#include <iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define UNDERFLOW -2
using namespace std;
typedef char TElemType;
typedef int Status;
typedef struct BiTNode { // 结点结构
TElemType data;
int level; //用于层序遍历求深度
struct BiTNode *lchild, *rchild; //左右孩子指针
}BiTNode, *BiTree;
BiTree T;
typedef BiTNode *ElemType;
typedef struct QNode {// 结点类型
ElemType data; //数据域
struct QNode *next; //指针域
}QNode, *QueuePtr;
typedef struct { // 链队列类型
QueuePtr front; // 队头指针
QueuePtr rear; // 队尾指针
}LinkQueue;
LinkQueue Q;
#define STACK_INIT_SIZE 80 //初始分配量
#define STACKINCREMENT 10 //分配增量
typedef struct {//注意与顺序表定义的区别
ElemType *base;//栈底指针
ElemType *top;//栈顶指针，指向栈顶的下一个位置
int stacksize; //当前已分配的存储容量
}SqStack;
SqStack S;
int flag = 2;//用于求某结点的子结点
Status InitQueue(LinkQueue &Q) {
// 构造一个空队列Q
Q.front = Q.rear = new QNode;
Q.front->next = NULL;//或Q.rear->next=NULL
return OK;
}
Status InitStack(SqStack &S) {//构造一个空栈S
S.base = (ElemType*)malloc(
STACK_INIT_SIZE * sizeof(ElemType));
//S.base = new ElemType[STACK_INIT_SIZE];
if (!S.base) exit(OVERFLOW); //存储分配失败
S.top = S.base; //空栈
S.stacksize = STACK_INIT_SIZE;
return OK;
}
Status EnQueue(LinkQueue &Q, ElemType e) {
// 插入元素e为Q的新的队尾元素
QueuePtr s = new QNode;
s->data = e; s->next = NULL;
Q.rear->next = s; Q.rear = s;
return OK;
}
//链栈的进栈
Status Push(SqStack &S, ElemType e) {//入栈
if (S.top-S.base == S.stacksize) {//栈满，追加存储空间
S.base = (ElemType *)realloc(S.base,
(S.stacksize + STACKINCREMENT) *
sizeof(ElemType));
if (!S.base) exit(OVERFLOW); //存储分配失败
S.top = S.base + S.stacksize; //新栈顶
S.stacksize += STACKINCREMENT;
}
*S.top++ = e; //e先入栈，再移动指针
return OK;
}
Status DeQueue(LinkQueue &Q, ElemType &e) {
//若队列不空，则删除Q的队头元素，
//用 e 返回其值，并返回OK；否则返回ERROR
if (Q.front == Q.rear) return ERROR;//空队列
QueuePtr p = new QNode;
p = Q.front->next; e = p->data; //非空队列
Q.front->next = p->next;
if (p->next == NULL) Q.rear = Q.front;
//若删除前只有一个结点，则删除后成为空队列
delete p; return OK;
}
//链栈的出栈
Status Pop(SqStack &S, ElemType &e) {//出栈
// 若栈不空，则删除S的栈顶元素，
// 用e返回其值，并返回OK；
// 否则返回ERROR
if (S.top == S.base) exit(UNDERFLOW);
e = *(S.top=S.top-1); //先移动指针，再取数据元素
return OK;
}
Status StackEmpty(SqStack S) {//是否为空栈
return S.base == S.top;
}
Status QueueEmpty(LinkQueue Q) {//是否为空队
return Q.rear == Q.front;
}
void CreateBiTree(BiTree &T) {
char c;
cin >> c;
if (c == '#')
T = NULL;
else
{
T = new BiTNode;
T->data = c;
cout << "请输入" << c << "的左孩子：";
CreateBiTree(T->lchild);
cout << "请输入" << c << "的右孩子：";
CreateBiTree(T->rchild);
}
}
// 先序遍历二叉树的递归算法
void Preorder(BiTree T) {
if (T) {//非空二叉树
cout << T->data;
Preorder(T->lchild); // 递归遍历左子树
Preorder(T->rchild);// 递归遍历右子树
}
}
//先序遍历非递归
void preorder(BiTree T) {
InitStack(S);
BiTree P = T;
do {
while (P) {
cout << P->data;
Push(S, P);
P = P->lchild;
}
if (!StackEmpty(S)) {
Pop(S, P);
P = P->rchild;
}
} while (!StackEmpty(S) || P);
}
// 中序遍历二叉树的递归算法
void Inorder(BiTree T) {
if (T) {//非空二叉树
Inorder(T->lchild); // 递归遍历左子树
cout << T->data;
Inorder(T->rchild);// 递归遍历右子树
}
}
//中序遍历非递归
void inorder(BiTree T) {
InitStack(S);//初始化栈
BiTree p = T;//p指向根结点
do {
while (p)//p不是空二叉树
{
Push(S, p);//指针p入栈
p = p->lchild;//沿左分支向下走
}
if (!StackEmpty(S)) {//栈不空才能出栈访问结点
Pop(S, p);//指针出栈
cout << p->data;//访问p所指向结点
p = p->rchild; //访问右子树
}
} while (!StackEmpty(S) || p);//栈空且p为空时结束
}
// 后序遍历二叉树的递归算法
void Postorder(BiTree T) {
if (T) {//非空二叉树
Postorder(T->lchild); // 递归遍历左子树
Postorder(T->rchild);// 递归遍历右子树
cout << T->data;
}
}
//层序遍历
void LevelTraverse(BiTree T) {
if (T) {
LinkQueue Q;
ElemType p;
InitQueue(Q);//初始化队列
EnQueue(Q, T);//根指针入队
while (!QueueEmpty(Q)) {
DeQueue(Q, p);
cout << p->data;
if (p->lchild)
EnQueue(Q, p->lchild);
if (p->rchild)
EnQueue(Q, p->rchild);
}
}
}
//二叉树中叶子结点的个数
void CountLeaf(BiTree T, int & count) {
if (T) {
if ((!T->lchild) && (!T->rchild))
count++;
CountLeaf(T->lchild, count);
CountLeaf(T->rchild, count);
}
}
//统计结点个数
void CountNode(BiTree T, int &count) {
if (T) {
count++;
CountNode(T->lchild, count);
CountNode(T->rchild, count);
}
}
// 后序遍历求二叉树的深度
int PostorderDepth(BiTree T) {
if (!T) return 0;
int a, b;
a = PostorderDepth(T->lchild);
b = PostorderDepth(T->rchild);
return ((a > b) ? a : b) + 1;
}
//层序遍历求二叉树深度
int LevelDepth(BiTree T) {
int h;//暂存当前访问到的层次
if (!T)
h = 0;//空树
else {
LinkQueue Q;
ElemType p;
InitQueue(Q);//初始化队列
T->level = 1;//根的层序1
EnQueue(Q, T);//根指针入队
while (!QueueEmpty(Q)) {
DeQueue(Q, p);
h = p->level;
if (p->lchild) {
p->lchild->level = h + 1;//左孩子层次加1
EnQueue(Q, p->lchild);
}
if (p->rchild) {
p->rchild->level = h + 1;//右孩子层次加1
EnQueue(Q, p->rchild);
}
}
}
return h;
}
//输出二叉树中某结点（先序遍历+后序遍历）
void Descendents(BiTree T, TElemType e) {
if (flag == 0) return;
if (T) {
if (e == T->data) flag = 1;
if (flag == 1)
cout << T->data;//先序
Descendents(T->lchild, e);
Descendents(T->rchild, e);
if (e == T->data)
flag = 0;//后序
}
}
// 输出度为2的节点
void CoundNode2(BiTree T, int &count) {
if (T) {
if (T->lchild&&T->rchild)count++;
CoundNode2(T->lchild, count);
CoundNode2(T->rchild, count);
}
}
int main() {
int leafNum = 0, nodeNum = 0, count = 0;
TElemType e;
cout << "\t\t\t\t*\t\t\t\t\t*";
cout << endl << "\t\t\t\t*\t计科1512-02210151232-杨少通\t*" << endl;
cout << "\t\t\t\t*****************************************" << endl << endl;
cout << "首先创建二叉树（若结点不存在请输入“#”）。" << endl << endl;
//创建二叉树
cout << "请输入根结点：";
CreateBiTree(T);
cout << endl << "先序遍历为（递归法）：";
Preorder(T);
cout << endl << "先序遍历为（非递归法）：";
preorder(T);
cout << endl << endl << "中序遍历为（递归法）：";
Inorder(T);
cout << endl << "中序遍历为（非递归法）：";
inorder(T);
cout << endl << endl << "后序遍历为（递归法）：";
Postorder(T);
cout << endl << endl << "层序遍历为（递归法）：";
LevelTraverse(T);
cout << endl << endl << "二叉树中叶子结点的个数：";
CountLeaf(T, leafNum);
cout << leafNum << "个";
cout << endl << endl << "二叉树中结点的个数：";
CountNode(T, nodeNum);
cout << nodeNum << "个";
cout << endl << endl << "请输入要求度为2的结点的个数：";
CoundNode2(T, count);
cout << count << "个";
cout << endl << endl << "二叉树的深度（后序遍历法）：";
cout << PostorderDepth(T);
cout << endl << "二叉树的深度（层序遍历法）：";
cout << LevelDepth(T);
cout << endl << endl << "请输入要求子结点的结点：";
cin >> e;
cout << e << "的子结点为（包括自身）：";
Descendents(T, e);
cout << endl << endl;
return 0;
}
已有 2736 位网友参与，快来吐槽：
发表评论