dhu 5.2 二叉树：建立存储结构（层次次序）

2024-07-16 05:29| 来源: 网络整理| 查看: 265

二叉树：建立存储结构（层次次序）时间限制: 1S类别: DS：树->中等

晚于: 2022-05-22 23:55:00后提交分数乘系数50%

截止日期: 2022-05-29 23:55:00

问题描述 :

目的：使用C++模板设计并逐步完善二叉树的抽象数据类型（ADT）。

内容：（1）请参照链表的ADT模板，设计二叉树并逐步完善的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考教材、课件，以及网盘中的链表ADT原型文件，自行设计二叉树的ADT。）

注意：二叉树ADT的基本操作的算法设计很多要用到递归的程序设计方法。

（2）基本操作：二叉树的二叉链表存储形式的建立，完成后将其加入到二叉树的ADT基本操作集中。

输入数据为层次次序，要求设计一个算法，将二叉树转化为二叉链表的存储形式。

初始条件：definition给出二叉树T的定义（自然输入顺序序列。无孩子或指针为空的情形，算法通过特殊分隔符识别（输入）），至少有1个根结点。

输出：按definition构造二叉树的二叉链表。

注意：由于测试数据的显示需建立在二叉树的遍历基础上。因此，请在设计好二叉树的三种遍历算法之后（基本操作2），再进行测试。

参考函数原型：

//建立二叉树的存储结构（用户函数）

template

void CreateTree_Layer(BinaryTree &T, ElemType &str, ElemType &empty)；

输入说明 :

第一行：表示无孩子或指针为空的特殊分隔符

第二行：二叉树的层次次序序列（结点元素之间以空格分隔）

输出说明 :

第一行：二叉树先序遍历结果

第二行：二叉树中序遍历结果

第三行：二叉树后序遍历结果

输入范例 :

62 * / # # + 3 400 + 12 14 # # # # 30 * # # # # # # 10 5 输出范例 :

+,-,,+,12,14,3,/,400,+,30,,10,5,62 12,+,14,,3,-,400,/,30,+,10,,5,+,62 12,14,+,3,,400,30,10,5,,+,/,-,62,+

#include #include #include using namespace std; #define Status int #define MAXSIZE 100 //二叉树的链表存储形式 typedef string TElemType; typedef string SElemType; //链栈结点定义 typedef struct StackNode { SElemType data; struct StackNode* next; }StackNode, * LinkStack; //链栈的初始化 Status InitStack(LinkStack& S) {//构造一个空栈S S = NULL; //栈顶指针即S return 1; } //链栈的出栈 Status Pop(LinkStack& S, SElemType& e) {//删除S的栈顶元素，用e返回 if (S == NULL) return 0; //判断空栈 StackNode* p = S; //将栈顶临时赋给p S = S->next; //删除 delete p; //释放空间 return 1; } SElemType GetTop(LinkStack& S) { if (S == NULL) return 0; //判断空栈 return S->data; //返回栈顶元素值 } Status Push(LinkStack& S, SElemType e) { StackNode* p = new StackNode; //生成新结点 p->data = e; //将新结点数据域置为e p->next = S; //将新结点插入栈顶 S = p; //修改栈顶指针为p return 1; } //顺序栈的存储结构 typedef struct { SElemType* base; SElemType* top; int stacksize; //可用最大容量 }SqStack; //遍历输出栈 void printStack(LinkStack S) { StackNode* p = S; while (p != NULL) { cout next != NULL) cout Push(S2, p->data); p = p->next; Pop(S1, e); } } typedef struct BiNode { TElemType data; //结点数据域 struct BiNode* lchild, * rchild; //左右孩子指针 } BiTNode, * BiTree; Status InitBiTree(BiTree& T,string str)//构造空二叉树T( 先序序列） { //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T string ch; cin >> ch; if (ch == str) T = NULL; //递归结束，建空树 else { T = new BiTNode; T->data = ch; //生成根结点 InitBiTree(T->lchild,str); //递归创建左子树 InitBiTree(T->rchild,str); //递归创建右子树 } return 1; } Status InitBiTree1(BiTree& T, string str)//构造空二叉树T( 层次序列） { string ch; getline(cin, ch); char s[1000] = { 0 }; strcpy(s,ch.c_str()); BiTNode* m[1000]={0}; int n = 0; int i = 0, k = 0; for (i = 0; s[i] != 0&&s[i]!=-2; i++) { string ch2=""; for (k = i; s[k] != ' '&&s[k]!=0; k++) { ch2 += s[k]; } BiTree T = new BiTNode; if (ch2 == str) T = NULL; else { T->data = ch2; //生成根结点 T->lchild = NULL; T->rchild = NULL; } m[n] = T; n++; i = k; } int num = n; n = 1, i = 0; BiTNode* father = m[i]; BiTNode* child = m[n]; while (n != num) { if (n % 2 != 0) father->lchild = child; else { father->rchild = child; if (num != n + 1) { i++; while (m[i] == NULL) i++; } } n++; father = m[i]; child = m[n]; } T = m[0]; return 1; } Status ClearNode(BiTNode *T)//清除叶子 { delete T; return 1; } Status ClearBiTree(BiTree &T)//将二叉树清为空树(差根结点 { if (T->lchild != NULL&& T->rchild != NULL) { if (T->lchild != NULL) ClearBiTree(T->lchild); if (T->rchild != NULL) ClearBiTree(T->rchild); } else ClearNode(T); return 1; } Status DestroyBiTree(BiTree &T)//销毁二叉树(需上面那个递归函数 { ClearBiTree(T); ClearNode(T); T = NULL; return 1; } bool BiTreeEmpty(BiTree T)//若T为空二叉树，返回1 { if (T!=NULL) return 0; else return 1; } int BiTreeDepth(BiTree T)//返回二叉树深度 { int m, n; if (T == NULL) return 0; //如果是空树，深度为0，递归结束 else { m = BiTreeDepth(T->lchild); //递归计算左子树的深度记为m n = BiTreeDepth(T->rchild); //递归计算右子树的深度记为n if (m > n) return (m + 1); //二叉树的深度为m 与n的较大者加1 else return (n + 1); } } BiTNode *ROOT(BiTree& T)//返回根结点 { BiTNode *p = T; return p; } BiTNode *Value(BiTree T, TElemType e)//返回值为e的结点 { BiTree Q[MAXSIZE]; int front = 0, rear = 0; BiTree p; if (T) { Q[rear] = T; rear++; while (front != rear)/*队列不空*/ { p = Q[front];/*出队*/ front = (front + 1) % MAXSIZE; if (p->data == e)/*如果找到*/ return p; if (p->lchild)/*左树入队*/ { Q[rear] = p->lchild; rear = (rear + 1) % MAXSIZE; } if (p->rchild)/*右树入队*/ { Q[rear] = p->rchild; rear = (rear + 1) % MAXSIZE; } } } return NULL; } void Assign(BiTree T, TElemType e, TElemType value)//结点e赋值为value { BiTNode *p= Value(T, e); p->data = value; return; } BiTNode *arent(BiTree T, TElemType e)//返回双亲，否则返回空 { BiTNode* p; if (T->lchild != NULL) if (T->lchild->data == e) return T; if (T->rchild != NULL) if (T->rchild->data == e) return T; if (T->lchild != NULL) { p = arent(T->lchild, e); if(p!=NULL) return arent(T->lchild, e); } if (T->rchild != NULL) { p = arent(T->rchild, e); if (p!=NULL) return arent(T->rchild, e); } return NULL; } BiTNode *LeftChild(BiTree T, TElemType e)//返回左孩子，否则返回空 { BiTNode* p = Value(T, e); return p->lchild; } BiTNode *RightChild(BiTree T, TElemType e)//返回右孩子，否则返回空 { BiTNode* p = Value(T, e); return p->rchild; } void PreOrderTraverse(BiTree T,LinkStack &S)//先序遍历 { if (T == NULL) { return; } Push(S, T->data); PreOrderTraverse(T->lchild,S); PreOrderTraverse(T->rchild,S); } void InOrderTraverse(BiTree T, LinkStack& S)//中序遍历 { if (T == NULL) { return; } InOrderTraverse(T->lchild,S); Push(S, T->data); InOrderTraverse(T->rchild,S); } void PostOrderTraverse(BiTree T, LinkStack& S)//后序遍历 { if (T == NULL) {return;} PostOrderTraverse(T->lchild,S); PostOrderTraverse(T->rchild,S); Push(S, T->data); } void _BTreeLevelOrder(BiTNode* root, int i,LinkStack &S) { if (root == NULL || i == 0) { return; } if (i == 1) { Push(S,root->data); return; } _BTreeLevelOrder(root->lchild, i - 1,S); _BTreeLevelOrder(root->rchild, i - 1,S); } void BTreeLevelOrder(BiTNode* root,LinkStack &S) { if (root == NULL) return; int dep = BiTreeDepth(root); for (int i = 1; i StackNode* p = S; SElemType e=" "; while (p != NULL) { p = p->next; Pop(S,e); } } void change(BiTNode* T)//交换左右结点 { BiTNode* p = T->lchild; T->lchild = T->rchild; T->rchild = p; return ; } void solution(BiTree T)//后序遍历 { if (T == NULL) { return; } solution(T->lchild); solution(T->rchild); change(T); } void Preprinttree(BiTree T, LinkStack& S1, LinkStack& S2)//先序输出 { PreOrderTraverse(T, S1); change(S1, S2); printStack(S2); clear(S2); cout PostOrderTraverse(T, S1); change(S1, S2); printStack(S2); clear(S2); cout

【本文地址】

公司简介

联系我们