本文共 6253 字，大约阅读时间需要 20 分钟。
注：本程序由Visual Studio 2015编写，与VC++6.0稍有区别，复制到VC++6.0注释掉“#include “stdafx.h””即可运行，复制到VS可直接运行。
#include “stdafx.h”#include
#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) {
// 构造一个空队列QQ.front = Q.rear = new QNode;Q.front->next = NULL;//或Q.rear->next=NULLreturn 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；否则返回ERRORif (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； // 否则返回ERRORif (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;
}
如有转载请注明来源： www.dreamload.cn/blog/?p=258&preview=true （洋葱先生）
转载地址：https://blog.csdn.net/Kindergarten_Sir/article/details/108587494 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
