购物网站php源代码,北京网站关键词排名公司,英国设计网站,国外10条新闻简短二叉树和其他树
可编译运行程序见#xff1a;Github::Jasmine-up/Data-Structures-Algorithms-and-Applications/_23BinaryTree
定义
树
定义 11-1 一棵树 t是一个非空的有限元素的集合#xff0c;其中一个元素为根#xff08;root#xff09;#xff0c;其余的元素Github::Jasmine-up/Data-Structures-Algorithms-and-Applications/_23BinaryTree
定义
树
定义 11-1 一棵树 t是一个非空的有限元素的集合其中一个元素为根root其余的元素如果有的话组成t的子树subtree。
在画一棵树时每个元素都代表一个节点。树根画在上面其子树画在下面。在根与子树的根如果有子树之间有一条边。同样的每一棵子树也是根在上其子树在下。在一棵树中一个元素节点及其孩子节点之间用边连接。树不能为空。
树的另一常用术语为级level。树根是 1级其孩子如果有是 2 级孩子的孩子是3 级等等。
一棵树的高度height或深度depth是树中级的个数。
一个元素的度degree of an element是指其孩子的个数。叶节点的度为0。
一棵树的度degree of a tree是其元素的度的最大值。
二叉树
定义
定义 11-2 一棵二叉树binary treet 是有限个元素的集合可以为空。当二叉树非空时其中有一个元素称为根余下的元素如果有的话被划分成两棵二叉树分别称为t的左子树和右子树。 二叉树和树的根本区别是
二叉树的每个元素都恰好有两棵子树其中一个或两个可能为空。而树的每个元素可有任意数量的子树。在二叉树中每个元素的子树都是有序的也就是说有左子树和右子树之分。而树的子树是无序的。
树和二叉树的另一个区别大概与定义有关二叉树可以为空但树不能为空。有的作者放宽了对树的定义允许树为空。 和树一样二叉树也是根节点在顶部。二叉树左右子树中的元素画在根的左右下方。每个元素节点和其子节点之间用一条边相连。 二叉树特性
二叉树的特性
特性 11-1 一棵二叉树有 n 个元素n0它有 n-1 条边。
证明 二叉树的每个元素除了根节点有且只有一个父节点。在子节点与父节点间有且只有一条边因此边数为n-1。
特性 11-2 一棵二叉树的高度为hh0它最少有h个元素最多有 2 h 2^h 2h-1 个元素。
证明 因为每一级最少有1个元素因此元素的个数最少为h。每个元素最多有2个子节点则第i层节点元素最多为 2 h − 1 2^h-1 2h−1 个i0。当 h0 时元素的总数为 0也就是 2 0 − 1 2^0-1 20−1。当h0 时元素的总数不会超过 ∑ i 1 h 2 h − 1 2 h − 1 \sum_{i1}^h2^{h-1}2^h-1 ∑i1h2h−12h−1。
特性 11-3 一棵二叉树有 n 个元素n0它的高度最大为 n最小高度为 ⌈ l o g 2 ( n − 1 ) ⌉ \lceil log_2(n-1)\rceil ⌈log2(n−1)⌉。
证明 因为每层至少有一个元素因此高度不会超过n。由特性 11-2可以得知高度为h 的二叉树最多有 2 h − 1 2^h-1 2h−1个元素。因为 n 2 h − 1 2^h-1 2h−1所以 h l o g 2 ( n 1 ) hlog_2(n1) hlog2(n1)。由于h是整数所以 h ≥ ⌈ l o g 2 ( n − 1 ) ⌉ h \geq \lceil log_2(n-1)\rceil h≥⌈log2(n−1)⌉。
满二叉树
当高度为h的二叉树恰好有 2 h − 1 2^h-1 2h−1个元素时称其为满二叉树full binary tree。如图11-6所示。 完全二叉树
对高度为h的满二叉树的元素从第一层到最后一层在每一次中从左至右顺序编号从1到 2 h − 1 2^h-1 2h−1如图11-6所示。假设从满二叉树中删除k个其编号为 2 h − i 2^h-i 2h−i元素 1 ≤ i ≤ k 2 h 1≤i≤k2^h 1≤i≤k2h所得到的二叉树被称为完全二叉树complete binary tree。满二叉树是完全二叉树的特例。 在完全二叉树中一个元素与其孩子的编号有非常好的对应关系。
特性 11-4 设完全二叉树的一元素其编号为i 1 i n 1in 1in。有以下关系成立 1如果 i 1 i1 i1则该元素为二叉树的根。若 i 1 i1 i1则其父节点的编号为 ⌊ i / 2 ⌋ \lfloor i/2\rfloor ⌊i/2⌋。 2如果 2 i n 2in 2in则该元素无左孩子。否则其左孩子的编号为 2 i 2i 2i。左孩子一定是偶数。 3如果 2 i 1 n 2i1n 2i1n则该元素无右孩子。否则其右孩子的编号为 2 i 1 2i1 2i1。右孩子一定是奇数。
树的二叉树描述
当分布树t有节点超过两个孩子时依然用二叉树来表示。此时对每个节点x可用其孩子节点的rightChild指针把x的所有孩子链成一条链表。x节点的leftChild指针指向该链表的第一个节点。x节点的rightChild指针来指向 x 的兄弟。图 11-15 是一棵树和其二叉树其中实线表示指向左孩子的指针虚线表示指向右孩子的指针。 二叉树的描述
数组描述
当缺少的元素数目多时很浪费空间因此不常用。
链表描述
二叉树最常用的表示方法是用指针。每个元素用一个节点表示节点有两个指针域分别称为leftChild和rightChild。除两个指针域之外每个节点还有一个element域。
父节点的每一个指向孩子的指针表示一条边。因为 n个元素的二叉树仅有 n-1 条边所以有2n-n-1n1个指针域没有值它们被置为NULL。图 11-10 是二叉树的链表表示。 二叉树遍历 前序遍历根左孩子右孩子。对应于前缀表达式在前缀prefix表达式中操作符位于操作数之前操作数从左到右顺序出现。不会存在歧义无需括号和优先级。 中序遍历左孩子根右孩子。对应于中缀表达式每个二元操作符即有两个操作数的操作符出现在左操作数之后右操作数之前。但是这种表达式有歧义如 x y ∗ z xy*z xy∗z是解释为 ( x y ) ∗ z (xy)*z (xy)∗z还是 x ( y ∗ z ) x(y*z) x(y∗z)呢因此有时候会使用括号来表示优先级。 后序遍历左孩子右孩子根。对应于后缀表达式在后缀postfix表达式中每个操作符跟在操作数之后操作数从左到右顺序出现。不会存在歧义无需括号和优先级。 层序遍历从顶层到底层在同一层中从左到右依次访问树的元素。
练习题
24.编写一个C 函数复制一个数组表示的二叉树。27.编写一个函数计算一棵链式二叉树的高度。确定其时间复杂性。29.编写一个函数确定一棵链式二叉树在哪一层具有最多的节点提示用层次遍历。确定其时间复杂性。33.设有一棵二叉树每个节点的数据都不相同。数据域的前序和中序序列是否可以唯一地确定这棵二叉树如果可以编写一个函数用前序和中序序列来构造这棵二叉树。计算函数的时间复杂性。34.按前序和后序遍历方法完成练习33。35.按后序和中序遍历方法完成练习33。36.编写一个C函数输入后缀表达式构造其二叉树表示。假设每个操作符有一个或两个操作数。37.用前缀表达式完成练习36。38.编写一个 C函数把后缀表达式转换为完全括号化的中缀表达式。40.编写一个函数把一个中缀形式表达式不一定是完全括号化的转换成后缀表达式。假定操作符可以是二元操作符、一、*、1分界符可以是左括号和右括号。因为操作数的顺序在中缀、前缀、后缀表达式中都是一样的所以在从中缀向前缀或后缀转换时仅需要从左到右扫描中缀表达式。把扫描到的操作数直接输出而遇到的操作符保留在栈中根据操作符和左括号的优先级来确定输出。假定和-的优先级为1*和/的优先级为 2。栈外的左括号优先级为 3栈内的左括号优先级为 0。41.完成练习40但是生成前缀表达式。43.编写一个函数计算后缀表达式的值。假设表达式以数组方式表示。44.编写类linkedBinaryTree的一个复制构造函数。测试代码。计算时间复杂性。45.编写方法linkedBinaryTree Ecomparex比较二叉树*this与二叉树x。当且仅当它们相同时返回 true。测试你的代码。计算时间复杂性。46.编写方法linkedBinaryTreeEswapTrees它交换每一个节点的左右子树。测试你的代码。计算时间复杂性。
二叉树的应用
设置信号放大器
在一个分布式网络中资源从生产地送往其他地方。例如汽油或天然气经过管道网络从生产基地送到消费地。同样的电力也是通过电网从发电厂输送到各消费点。可以用术语信号signal来指称输送的资源汽油、天然气、电力等。当信号在网络中传输时它在某一方面或某几个方面的性能可能会损失或衰减。例如天然气管道中的气压会减少电网上的电压会降低。另一方面在信号传输中噪声会增加。在信号从信号源到消费点传输的过程中仅能容忍一定范围内的信号衰减。为了保证信号衰减不超过容忍值tolerance应在网络中至关重要的位置上放置信号放大器signal booster。信号放大器可以增加信号的压强或电压使它与源点相同可以增强信号使信号与噪声之比与源点的相同。本节将设计一个算法以计算信号放大器的放置地点。目标是放大器的数目最少同时保证信号衰减与源点信号相关不超过给定的容忍值。
为简化问题假设分布网络是一树形结构源点是树的根。树的每一个非根节点表示一个可以放置放大器的地点某些节点同时也表示消费点。信号从一个节点流向其子节点。图11-12 是一树形分布网络。每条边上的数字是信号从父节点流到其子节点的信号衰减量。衰减量的单位假设可以附加。在图 11-12中信号从节点p流到节点v的衰减量是5。从节点q到节点x的衰减量为3。如果把一个信号放大器放在节点r那么虽然当信号从节点p到达节点r时它的强度比在节点p时衰减了3个单位但是当它从节点r流出时又恢复了它在源点p的强度。因此信号到达节点v时强度比在源点p时衰减了2个单位到达节点z时强度比在源点p时衰减了 4个单位。如果在节点r没有信号放大器那么在节点 z 的信号将衰减 7个单位。 设 degradeFromParenti表示节点i与其父节点间的衰减量。因此在图 11-12 中degradeFromParents2degradeFromParentp0degradeFromParentr3。因为信号放大器只能放在树形分布网的节点上所以节点i的degradeFromParenti如果大于容忍值那么即使在节点i放置了信号放大器信号的衰减量依然要超过容忍值。例如若容忍值为2则在图11-12的节点r上即使有信号放大器信号的衰减量也不会小于或等于2。
在以节点i为根的子树中从节点i到子树的每个叶子都有一个衰减量我们把这些衰减量的最大者记为degradeToLeafi。若i是叶节点则degradeToLeafi0。在图11-12中当iEwxtyz时degradeToLeafi0。对于其他节点degradeToLeafi可以用下面的方程式来计算 因此degradeToLeafs3。在此公式中要计算节点的degradeToLeaf值就要先计算其子节点的degradeToLeaf值因此必须对树进行遍历。先访问子节点再访问父节点。在访问一个节点时同时计算它的degradeToLeaf值。这种遍历方法是对后序遍历的一种自然扩充其树的度大于 2。
按照上述方法在计算 degradeToLeaf过程中遇到一节点i它有一子节点j满足
如果不在j节点放置放大器那么从i节点到叶节点的信号衰减量将超过容忍值即使在i节点处放置了放大器也是如此。例如在图 11-12 中当计算degradeToLeafq时有 如果容忍值为 3那么在 q 点或其祖先的任意一点放置放大器都不能减少 q 与其后代间的衰减量。我们需要在s点放一个放大器这时degradeToLeafg3。
测试中使用的是下面这棵树测试时输入的a的degradeToLeaf为0degradeFromParent为1输入的b的degradeToLeaf为0degradeFromParent为2。 并查集
问题描述有 n个元素从1 到 n编号。开始时每一个元素在自己的类中然后执行一系列find和combine操作。操作findtheElement返回元素theElement所在类的唯一特征而combineab把包含a和b的两个类合并。
建模为树任何一个集合 S 都可以描述为一棵具有 ∣ S ∣ \lvert S \rvert ∣S∣个节点的树一个节点代表一个元素。任何一个元素可以作为根元素剩余元素的任何子集可以作为根元素的孩子再剩余元素的任何子素集可以作为根元素的孙子等等。 举例如图11-16我们说元素1、2、20、30 等属于以20为根的集合元素 11、16、25、28 属于以16为根的集合元素 15 属于以 15 为根的集合元素 26 和 32 属于以 26 为根的集合。
求解策略并查集问题的求解策略是把每一个集合表示为一棵树。在查找时我们把根元素作为集合标志符。因此find3的返回值是20见图11-16find1的返回值是20find26的返回值是26。因为每一个集合都有唯一的根所以当且仅当i和j属于同一个集合时有findifindj。为了确定元素theElement属于哪一个集合我们从元素theElement 的节点开始沿着节点到其父节点向上移动直到根节点为止。
在合并时我们假设在调用语句uniteclassAclassB中classA 和 classB分别是两个不同树集合的根即classA classB。为了把两个集合合并我们让一棵树成为另一棵树的子树。例如假设classA16而classB26见图11-16如果让 classA 成为 classB 的子树那么结果如图11-17a所示如果让classB成为classA的子树那么结果如图 11-17b所示。 C实现查集问题的求解策略是模拟指针的一个极好的应用。这里需要树的链表描述其中每个节点必须有一个parent域但不必有孩子域。还需要直接访问节点。为找到含有元素10的集合先要找到元素10的节点然后沿着节点的parent指针找到根节点。如果n个节点的索引号从1到nn是元素个数且节点e表示元素e那么很容易实现直接访问。每个parent域给出父节点的索引因此parent域为整数类型。 图11-18就是采用这种方法来表示图 11-16的。节点内的数字是其parent域的值节点外的数字是该节点的索引。索引同时也是该节点所表示的元素。根节点的 parent 域被置为 0。因为没有索引是 0 的节点所以 parent为0 表示不指向任何节点即为空链。 性能分析构造函数的时间性能是OnumberOfElements查找函数find的时间性能是Oh其中h是树的高度。合并函数unite的时间性能是O1。假设一个系列操作要执行u次合并和f次查找一个系列操作的时间为O(fu)。
每次合并前都要执行两次查找这些查找决定了要合并的树的根,此处可以优化因为查找比较费时间如果每次合并都查找的话就很占用时间。
合并函数的性能改进在对根为 i和根为j的树进行合并操作时利用重量规则或高度规则可以提高并查集算法的性能。
**定义 11-3[重量规则]**若根为i的树的节点数少于根为 j的树的节点数则将j作为i 的父节点。否则将i作为j的父节点。 **定义 11-4[高度规则]**若根为 i 的树的高度小于根为j 的树的高度则将j 作为 i 的父节点否则将i作为j的父节点。
使用重量队则的测试见代码_28binaryTreeChains.cpp
**引理 11-1[重量规则引理]**假设从单元素集合出发用重量规则进行合并操作。若以此方式构建一棵具有 p 个节点的树 t则 t 的高度最多为 ⌊ l o g 2 p ⌋ 1 \lfloor log_2p\rfloor1 ⌊log2p⌋1。
若使用重量规则合并和查找序列的代价不包括初始化时间为O(uflogu) O(flogu)因为我们假定fu。
查找函数的性能改进缩短从元素e到根的查找路径。这个方法利用了路径压缩path compression过程这个过程的实现至少有3种不同的途径–路径紧缩path compaction、路径分割path splitting和路径对折path halving。
在路径紧缩中从待查节点到根节点的路径上所有节点的parent 指针都被改为指向根节点。以图 11-20 为例当执行查找操作find10时从10到根的路径有节点10、15和3。把这些节点的parent域改为 2就得到图 11-21节点 3 的指针本来就指向 2因此其 parent域不必修改。但是为简化起见程序还是对路径上的每个节点都进行了修改。 路径紧缩代码 在路径分割中从e节点到根节点的路径上除根节点和其子节点之外每个节点的parent指针都被改为指向各自的祖父。在图11-20中路径分割从节点13开始结果得到图11-22 的树。在路径分割时只考虑从e到根节点的一条路径就够了。 在路径对折中从e节点到根节点的路径上除根节点和其子节点之外每隔一个节点其parent指针都被改为指向各自的祖父。在路径对折中指针改变的个数仅为路径分割中的一半。同样在路径对折中只考虑从e到根的一条路径就够了。在图11-20中路径对折从节点13开始结果得到图11-23的树。 仿真测试
main.cpp
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月13日17点38分
Last Version: V1.0
Descriptions: main()函数控制运行所有的测试函数
*/
#include _28binaryTreeChains.hint main()
{binaryTreeChainsTest();treeExpressionsTest();treeApplicationTest();return 0;
}_28binaryTreeChains.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月27日09点44分
Last Version: V1.0
Descriptions: 用链表表示的二叉树.h
笔记1.静态函数指针初始化格式void (*binaryTreeChainsE::visit)(binaryTreeNodeE*) 0;2.不能单独专门化成员模板函数只能针对整个类专门化。3.在模板函数中可以使用typeid()区别对待特定数据类型。
本程序注意事项1.所有关于前缀、后缀、中缀表达式的全部使用了char类型代表元素char类型数组存储整个表达式
*/
#pragma once
#ifndef _BINARYTREECHAINS_H_
#define _BINARYTREECHAINS_H_
#include iostream
#include vector
#include cstring
#include stack
#include queue
#include _1myExceptions.h
#include _28binaryTreeNode.h
#include _28binaryTree.h
#include _28booster.h
#include _28treeUnionFindNode.h
using namespace std;
/*二叉树基础测试函数*/
void binaryTreeChainsTest();
/*二叉树树表达式测试函数*/
void treeExpressionsTest();
/*二叉树应用的测试函数*/
void treeApplicationTest();templateclass E
class binaryTreeChains : public binaryTreebinaryTreeNodeE
{
public:/*二叉树的基础成员函数*//*构造函数函数*/binaryTreeChains() {root nullptr; treeSize 0;}/*练习44:编写类linkedBinaryTree的一个复制构造函数。测试代码。*//* 计算时间复杂性。复制构造函数*/binaryTreeChains(binaryTreeChainsE m) {root treeCreateTree(m.root);}/*练习题33和练习题35*//*构造函数---先序和中序遍历或后序和中序创建二叉树*//*flag false时是先序和中序遍历构建二叉树flag true时是后序和中序构建二叉树*/binaryTreeChains(E preOrPostOrder[], E inOrder[],int length,bool flag){if(flag false)root preInCreateTree(preOrPostOrder, inOrder, length);elseroot postInCreateTree(preOrPostOrder, inOrder, length);}/*构造函数---前缀或后缀或中缀表达式创建二叉树*//*练习37当flag 1时前缀表达式创建二叉树当flag 2时中缀表达式创建二叉树练习36当flag 3时后缀表达式创建二叉树*/binaryTreeChains(E expression[], int length,int flag){switch (flag){case 1:root preExprCreateTree(expression, length);break;case 2:root inExprCreateTree(expression, length);break;case 3:root postExprCreateTree(expression, length);break;}}/*析构函数*/~binaryTreeChains() { erase(); }/*当树为空时返回true否则返回false*/bool empty() const { return treeSize 0; }/*返回元素个数*/int size() const { return treeSize; }/*前序遍历二叉树使用函数指针的目的是是的本函数可以实现多种目的*/void preOrder(void(*theVisit)(binaryTreeNodeE*)){visit theVisit;/*是因为递归所以才要这样的*/preOrder(root);/*这里调用的是成员函数preOrder()*/}/*前序遍历---输出endl*/void preOrderOutput() { preOrder(output); cout endl; }/*前序遍历---不使用递归而使用迭代函数*/vectorE iterativePreOrder();/*中序遍历二叉树使用函数指针的目的是是的本函数可以实现多种目的*/void inOrder(void(*theVisit)(binaryTreeNodeE*)){visit theVisit;/*是因为递归所以才要这样的*/inOrder(root);/*这里调用的是静态成员函数inOrder()*/}/*中序遍历---输出endl*/void inOrderOutput() { inOrder(output); cout endl; }/*中序遍历---不使用递归而使用迭代函数*/vectorE iterativeInOrder();/*后续遍历二叉树使用函数指针的目的是是的本函数可以实现多种目的*/void postOrder(void(*theVisit)(binaryTreeNodeE*)){visit theVisit;/*是因为递归所以才要这样的*/postOrder(root);/*这里调用的是静态成员函数inOrder()*/}/*后序遍历---输出endl*/void postOrderOutput() { postOrder(output); cout endl; }/*后序遍历---不使用递归而使用迭代函数*/vectorE iterativePostOrder();/*层次遍历二叉树*/void levelOrder(void (*theVisit)(binaryTreeNodeE*));/*层次遍历---输出endl*/void levelOrderOutput() { levelOrder(output); cout endl; }/*清空二叉树 这里必须使用后序遍历 不然会出错*/void erase(){postOrder(dispose);root nullptr;treeSize 0;}/*输入时为了将root根节点传递给createBiTree()函数*/void input(void){createBiTree(root);}/*是一个手动创建二叉树的函数使用本函数得手动设置各节点之间的关系见信号放大器应用的使用*//*将左数和右数合并为一个树(也就是this树)*/void makeTree(const E element, binaryTreeChainsE, binaryTreeChainsE);/*练习45比较二叉树*this和二叉树m*/bool compare(binaryTreeChainsE m){return compareTree(root, m.root);}/*练习46交换每一个结点的左右子树*/void swapTrees(){swapTrees(root);}/*练习27计算二叉树高度*/int height() const { return height(root); }/*练习47计算二叉树的最大高度差*/int maxHeightDifference(){return maxHeightDifference(root);}/*练习29计算二叉树在那一层具有最多的结点---返回值为结点最多的层*/int layerMaxNumOfNode();/*计算二叉树在在哪一层具有最多的结点--返回值为结点最多的层的结点数量*/int maxNumOfNodeInLayer();/*二叉树表达式的成员函数*//*计算树的表达式的值*/int compulateTree(){return compulateTree(root);}
private:/*二叉树基础私有成员*/binaryTreeNodeE* root;//指向根的指针int treeSize;//树的结点个数static void (*visit)(binaryTreeNodeE*);//是一个函数指针,返回值为void 函数参数为binaryTreeNodeE*static void preOrder(binaryTreeNodeE* t);static void inOrder(binaryTreeNodeE* t);static void postOrder(binaryTreeNodeE* t);static void dispose(binaryTreeNodeE* t) { delete t; }static void output(binaryTreeNodeE* t) { cout t-element ; }/*创建二叉树---递归---作为私有成员只能被成员函数调用*/void createBiTree(binaryTreeNodeE* tree);/*复制构造函数调用的函数*/binaryTreeNodeE* treeCreateTree(binaryTreeNodeE* node);/*私有成员函数---用于比较二叉树compare()*/bool compareTree(binaryTreeNodeE* thisNode, binaryTreeNodeE* xNode);/*私有成员函数---交换树的每个结点的左右子树---递归*/void swapTrees(binaryTreeNodeE* node);/*私有成员函数---计算二叉树高度---返回根为node的树的高度*/int height(binaryTreeNodeE* node) const;/*私有成员函数---计算结点node的左右子树高度的差值*/int heightDifference(binaryTreeNodeE* node) const;/*私有成员函数---计算二叉树的最大高度差---返回值为二叉树的最大高度差*/int maxHeightDifference(binaryTreeNodeE* node) const;binaryTreeNodeE* preInCreateTree(E preOrder[], E inOrder[], int size);binaryTreeNodeE* postInCreateTree(E postOrder[], E inOrder[], int size);/*二叉树表达式的私有成员*//*计算树的表达式的值*//*本程序所有关于前缀、中缀、后缀表达式的处理全部是char类型并且只能进行个位数的计算*/int compulateTree(binaryTreeNodeE* node) const;binaryTreeNodeE* preExprCreateTree(E expression[], int length);binaryTreeNodeE* inExprCreateTree(E expression[], int length);binaryTreeNodeE* postExprCreateTree(E expression[], int length);
};
/*私有静态成员初始化*/
/*这里是静态函数指针成员的初始化不初始化会引发LINK错误*/
templateclass E
void (*binaryTreeChainsE::visit)(binaryTreeNodeE*) 0; // visit function/*非成员函数*/
/*返回元素data在数组中的位置,找到则返回该元素的位置未找到则返回-1*/
templateclass E
int findRootLoc(E list[], E data, int length);
/*练习38将后缀表达式转换为完全括号化的中缀表达式 完全括号化的中缀表达式如((a)(b))*/
/*参数说明postExpr是后缀表达式数组的指针inExpr用于存储生成的前缀表达式length是后缀表达式的长度*/
void postExprToIn(char postExpr[], string inExpr, int length);
/*获取操作符的优先级不包括栈外左括号的优先级因为遇到栈外左括号直接入栈就行*/
int getPriority(char op);
/*将中缀表达式转换为后缀表达式*/
/*参数说明inExpr为指向中缀表达式的指针postExpr为指向生成的后序表达式的指针length表示中缀表达式的长度*/
void inExprToPost(char inExpr[], char postExpr[], int length);
/*练习41将中缀表达式转换为前缀表达式---从后往前归入前缀表达式*/
/*参数说明inExpr为指向中缀表达式的指针preExpr为指向生成的后序表达式数组的指针inLength表示中缀表达式的长度,preLength表示前缀表达式的长度*/
void inExprToPre(char inExpr[], char preExpr[], int inLength, int preLength);
/*练习39将前缀表达式转换为带括号的中缀表达式 如((ab)(c*d))*/
/*参数说明postExpr是后缀表达式数组的指针inExpr用于存储生成的前缀表达式length是后缀表达式的长度*/
void preExprToIn(char preExpr[], string inExpr, int length);/*计算表达式的值*/
/*前缀表达式计算表达式的值*/
/*参数说明preExpr表示指向前缀表达式数组的指针length表示前缀表达式的长度返回值为计算的结果*/
int preCalculate(char preExpr[], int length);
/*中缀表达式计算表达式的值*/
/*参数说明inExpr表示指向中缀表达式数组的指针length表示中缀表达式的长度返回值为计算的结果*/
int inCalculate(char inExpr[], int length);
/*练习43后缀表达式计算表达式的值*/
/*参数说明postExpr表示指向后缀表达式数组的指针length表示后缀表达式的长度返回值为计算的结果*/
int postCalculate(char postExpr[], int length);/*二叉树的应用*/
/*设置信号放大器*/
void placeBoosters(binaryTreeNodebooster* x);
/*并查集*/
void initialize(int numberOfElements);
int find(int theElement);
void unite(int rootA, int rootB);/*二叉树的普通成员函数*/
/*前序遍历 递归*/
templateclass E
void binaryTreeChainsE::preOrder(binaryTreeNodeE* t)
{if (t ! nullptr){visit(t);/*访问树根*/preOrder(t-leftChild);/*前序遍历左子树*/preOrder(t-rightChild);/*前序遍历右子树*/}
}
/*前序遍历---不使用递归而使用迭代函数*/
templateclass E
vectorE binaryTreeChainsE::iterativePreOrder()
{binaryTreeNodeE* currentNode root;stackbinaryTreeNodeE* st;vectorE result;/*写法1---前序中序后序遍历非递归统一版*//*首先将父节点入栈*/if (currentNode ! nullptr)st.push(currentNode);while (!st.empty()){currentNode st.top();st.pop();/*如果遇到nullptr,则输出当前栈顶元素*/if (currentNode nullptr){result.push_back(st.top()-element);st.pop();}/*如果没有遇到nullptr,则按照右左中的顺序入栈结点最后入栈nullptr*/else{if (currentNode-rightChild ! nullptr)st.push(currentNode-rightChild);if (currentNode-leftChild ! nullptr)st.push(currentNode-leftChild);st.push(currentNode);/*每次都在已遍历的根节点后入栈nullptr*/st.push(nullptr);}}///*写法2*////*当结点为nullptr并且栈为空时结束循环*///while (currentNode ! nullptr || !st.empty())//{// /*先将左边的左边的元素入栈*/// while (currentNode ! nullptr)// {// st.push(currentNode);// result.push_back(currentNode-element);// currentNode currentNode-leftChild;// }// /*然后一个一个遍历左边的元素并将该元素存储到vector中*/// currentNode st.top();// st.pop();// currentNode currentNode-rightChild;//}return result;
}/*中序遍历 递归*/
templateclass E
void binaryTreeChainsE::inOrder(binaryTreeNodeE* t)
{if (t ! nullptr){inOrder(t-leftChild);/*中序遍历左子树*/visit(t);/*访问树根*/inOrder(t-rightChild);/*中序遍历右子树*/}
}
/*中序遍历---不使用递归而使用迭代函数*/
templateclass E
vectorE binaryTreeChainsE::iterativeInOrder()
{binaryTreeNodeE* currentNode root;stackbinaryTreeNodeE* st;vectorE result;/*写法1---前序中序后序遍历非递归统一版*//*首先将父节点入栈*/if (currentNode ! nullptr)st.push(currentNode);while (!st.empty()){currentNode st.top();st.pop();/*如果遇到nullptr,则输出当前栈顶元素*/if (currentNode nullptr){result.push_back(st.top()-element);st.pop();}/*如果没有遇到nullptr,则按照右左中的顺序入栈结点最后入栈nullptr*/else{if (currentNode-rightChild ! nullptr)st.push(currentNode-rightChild);st.push(currentNode);/*每次都在已遍历的根节点后入栈nullptr*/st.push(nullptr);if (currentNode-leftChild ! nullptr)st.push(currentNode-leftChild);}}/*写法2*////*当结点为nullptr并且栈为空时结束循环*///while (currentNode ! nullptr || !st.empty())//{// /*先将左边的左边的元素入栈*/// while (currentNode ! nullptr)// {// st.push(currentNode);// currentNode currentNode-leftChild;// }// /*然后一个一个遍历左边的元素并将该元素存储到vector中*/// currentNode st.top();// st.pop();// result.push_back(currentNode-element);// currentNode currentNode-rightChild;//}return result;
}/*后序遍历 递归*/
templateclass E
void binaryTreeChainsE::postOrder(binaryTreeNodeE* t)
{if (t ! nullptr){postOrder(t-leftChild);/*后序遍历左子树*/postOrder(t-rightChild);/*后序遍历右子树*/visit(t);/*访问树根*/}
}
/*后序遍历---不使用递归而使用迭代函数*/
templateclass E
vectorE binaryTreeChainsE::iterativePostOrder()
{binaryTreeNodeE* currentNode root;stackbinaryTreeNodeE* st;vectorE result;/*前序中序后序遍历非递归统一版*//*首先将父节点入栈*/if (currentNode ! nullptr)st.push(currentNode);while (!st.empty()){currentNode st.top();st.pop();/*如果遇到nullptr,则输出当前栈顶元素*/if (currentNode nullptr){result.push_back(st.top()-element);st.pop();}/*如果没有遇到nullptr,则按照右左中的顺序入栈结点最后入栈nullptr*/else{st.push(currentNode);/*每次都在已遍历的根节点后入栈nullptr*/st.push(nullptr);if (currentNode-rightChild ! nullptr)st.push(currentNode-rightChild);if (currentNode-leftChild ! nullptr)st.push(currentNode-leftChild);}}return result;
}/*层次遍历二叉树 非递归*/
templateclass E
void binaryTreeChainsE::levelOrder(void (*theVisit)(binaryTreeNodeE*))
{visit theVisit;binaryTreeNodeE* temp;queuebinaryTreeNodeE* que;que.push(root);while (!que.empty()){temp que.front();que.pop();visit(temp);if (temp-leftChild ! nullptr)que.push(temp-leftChild);if (temp-rightChild ! nullptr)que.push(temp-rightChild);}
}
/*创建二叉树---递归---模板的实现*/
templateclass E
void binaryTreeChainsE::createBiTree(binaryTreeNodeE* tree)
{E data;cout Please enter the tree element:;while (!(cin data)){cin.clear();//清空标志位while (cin.get() ! \n)//删除无效的输入continue;cout Please enter the tree element:;}cin.get();/*针对char类型的特例*/if (typeid(data) typeid(char)) {if (data #)tree nullptr;else {treeSize;tree new binaryTreeNodeE(data);createBiTree(tree-leftChild);createBiTree(tree-rightChild);}/*关于二叉树对于设置信号放大器的应用我新定义了成员函数maketree()生成二叉树这里会报错C2228“.degradeFromParent”的左边必须有类/结构/联合我实在是不知道怎么改*///else if (typeid(data) typeid(booster))// if (data.degradeFromParent 999)// tree nullptr;// else// {// treeSize;// tree new binaryTreeNodeE(data);// createBiTree(tree-leftChild);// createBiTree(tree-rightChild);// }}else/*针对其他类型*/{if (data 999)tree nullptr;//当遇到999时令树的根节点为nullptr,从而结束该分支的递归else{treeSize;tree new binaryTreeNodeE(data);createBiTree(tree-leftChild);createBiTree(tree-rightChild);}}
}
/*是一个手动创建二叉树的函数使用本函数得手动设置各节点之间的关系见信号放大器应用的使用*/
/*将左树和右树合并为一个树*/
templateclass E
void binaryTreeChainsE::makeTree(const E element, binaryTreeChainsE left, binaryTreeChainsE right)
{// Combine left, right, and element to make new tree.// left, right, and this must be different trees.// create combined treeroot new binaryTreeNodeE(element, left.root, right.root);treeSize left.treeSize right.treeSize 1;// deny access from trees left and rightleft.root right.root NULL;left.treeSize right.treeSize 0;
}/*练习24根据二叉树创建二叉树---用于复制构造函数*/
templateclass E
binaryTreeNodeE* binaryTreeChainsE::treeCreateTree(binaryTreeNodeE* node)
{binaryTreeNodeE* head nullptr;if (node ! nullptr){treeSize;
// cout node-element node-element endl;head new binaryTreeNodeE(node-element);head-leftChild treeCreateTree(node-leftChild);head-rightChild treeCreateTree(node-rightChild);}return head;
}/*练习45私有成员函数---用于比较二叉树compare()*/
templateclass E
bool binaryTreeChainsE::compareTree(binaryTreeNodeE* thisNode, binaryTreeNodeE* xNode)
{/*两个结点都为空时二叉树相等*/if (thisNode nullptr xNode nullptr)return true;/*一个结点为空一个结点非空则二叉树不相等*/if ((thisNode nullptr xNode ! nullptr) || (thisNode ! nullptr xNode nullptr))return false;/*两个结点的元素不等则二叉树不相等*/if (thisNode-element ! xNode-element)return false;else/*两个结点相等则比较彼此的左子树和右子树*/return compareTree(thisNode-leftChild, xNode-leftChild) compareTree(thisNode-rightChild, xNode-rightChild);
}/*练习46私有成员函数---交换树的每个结点的左右子树---递归*/
templateclass E
void binaryTreeChainsE::swapTrees(binaryTreeNodeE* node)
{if (node ! nullptr){swapTrees(node-leftChild);swapTrees(node-rightChild);binaryTreeNodeE* temp node-leftChild;node-leftChild node-rightChild;node-rightChild temp;}
}/*练习27私有成员函数---计算二叉树高度---返回根为node的树的高度*/
templateclass E
int binaryTreeChainsE::height(binaryTreeNodeE* node) const
{if (node nullptr)return 0;int hl height(node-leftChild);int hr height(node -rightChild);if (hl hr)return hl;elsereturn hr;
}/*私有成员函数---计算结点node的左右子树高度的差值*/
templateclass E
int binaryTreeChainsE::heightDifference(binaryTreeNodeE* node) const
{if (node nullptr)return 0;int lh height(node-leftChild);int rh height(node-rightChild);
// cout node-element : lh endl;
// cout node-element : rh endl;if (lh rh)return lh - rh;elsereturn rh - lh;
}/*练习47私有成员函数---计算二叉树的最大高度差---返回值为二叉树的最大高度差*/
templateclass E
int binaryTreeChainsE::maxHeightDifference(binaryTreeNodeE* node) const
{if (node nullptr)return 0;int height heightDifference(node);//当前结点的左右子树的高度差int hl maxHeightDifference(node-leftChild);//当前结点的左子树的左右子树的高度差int hr maxHeightDifference(node-rightChild);//当前结点的右子树的左右子树的高度差if (height hl height hr)return height;else if (hl height hl hr)return hl;else if (hr height hr hl)return hr;
}/*练习29计算二叉树在那一层具有最多的结点---返回值为结点最多的层*/
/*当二叉树为空时返回0*/
templateclass E
int binaryTreeChainsE::layerMaxNumOfNode()
{if (root nullptr)return 0;int num 0;//累加每层的结点数int layer 0;//记录当前的层数int maxNum 0;//存储结点最多的层的结点个数int maxLayer 0;//存储结点最多的层的层数binaryTreeNodeE* lastNode root;//存储上一层最后一个结点的元素位置binaryTreeNodeE* nextNode nullptr;//存储当前层最后一个结点的元素位置binaryTreeNodeE* currentNode;queuebinaryTreeNodeE* que;que.push(root);while (!que.empty()){currentNode que.front();que.pop();num;if (currentNode-leftChild ! nullptr){que.push(currentNode-leftChild);nextNode currentNode-leftChild;}if (currentNode-rightChild ! nullptr){que.push(currentNode-rightChild);nextNode currentNode-rightChild;}if (currentNode lastNode){layer;//刚刚处理完第几层lastNode nextNode;nextNode nullptr;if (num maxNum){maxNum num;maxLayer layer;}num 0;}}return maxLayer;
}/*计算二叉树在在哪一层具有最多的结点--返回值为结点最多的层的结点数量*/
/*当二叉树为空时返回0*/
templateclass E
int binaryTreeChainsE::maxNumOfNodeInLayer()
{if (root nullptr)return 0;int num 0;//累加每层的结点数int layer 0;//记录当前的层数int maxNum 0;//存储结点最多的层的结点个数int maxLayer 0;//存储结点最多的层的层数binaryTreeNodeE* lastNode root;//存储上一层最后一个结点的元素位置binaryTreeNodeE* nextNode nullptr;//存储当前层最后一个结点的元素位置binaryTreeNodeE* currentNode nullptr;queuebinaryTreeNodeE* que;que.push(root);while (!que.empty()){currentNode que.front();que.pop();num;if (currentNode-leftChild ! nullptr){que.push(currentNode-leftChild);nextNode currentNode-leftChild;}if (currentNode-rightChild ! nullptr){que.push(currentNode-rightChild);nextNode currentNode-rightChild;}if (currentNode lastNode){layer;//刚刚处理完第几层lastNode nextNode;nextNode nullptr;if (num maxNum){maxNum num;maxLayer layer;}num 0;}}return maxNum;
}/*使用前序和中序遍历构建二叉树*/
/*关键点在于找到根节点在中序中的位置该位置之前为该根的左子树该位置之后为该根的右子树*/
templateclass E
binaryTreeNodeE* binaryTreeChainsE::preInCreateTree(E preOrder[], E inOrder[], int size)
{/*如果没有左右子树则返回nullptr*/if (size 0)return nullptr;binaryTreeNodeE* rootData new binaryTreeNodeE(preOrder[0]);/*找到根节点的位置中序中该位置左侧就是该根节点的左子树该位置右侧就是该根节点的右子树*/int rootLoc findRootLocE(inOrder, preOrder[0] ,size);/*创建左子树和右子树*/rootData-leftChild preInCreateTree(preOrder 1, inOrder, rootLoc);rootData-rightChild preInCreateTree(preOrder 1 rootLoc, inOrder rootLoc 1, size - 1 - rootLoc);return rootData;
}
/*使用后序和中序遍历构建二叉树*/
/*关键点在于找到根节点在中序中的位置该位置之前为该根的左子树该位置之后为该根的右子树*/
templateclass E
binaryTreeNodeE* binaryTreeChainsE::postInCreateTree(E postOrder[], E inOrder[], int size)
{/*如果没有左右子树则返回nullptr*/if (size 0)return nullptr;binaryTreeNodeE* rootData new binaryTreeNodeE(postOrder[size-1]);/*找到根节点的位置中序中该位置左侧就是该根节点的左子树该位置右侧就是该根节点的右子树*/int rootLoc findRootLocE(inOrder, postOrder[size-1], size);/*创建左子树和右子树*/rootData-leftChild postInCreateTree(postOrder, inOrder, rootLoc);rootData-rightChild postInCreateTree(postOrder rootLoc, inOrder rootLoc 1, size - 1 - rootLoc);return rootData;
}/*二叉树表达式的成员函数*/
/*计算树的表达式的值*/
/*用字符串记录表达式*/
/*这个函数需要使用char类型的树其他类型的二叉树不满足要求*/
templateclass E
int binaryTreeChainsE::compulateTree(binaryTreeNodeE* node) const
{if (node nullptr)return 0;if (node-leftChild nullptr node-rightChild nullptr) //左右子树都是nullptr时说明它是叶子节点而叶子结点就是数而非符号return node-element - 0;//就返回叶子结点int a compulateTree(node-leftChild);//先计算左子树int b compulateTree(node-rightChild);//再计算右子树switch (node-element)//当前结点不是叶子节点时说明他是符号结点{case :return a b;case -:return a - b;case *:return a * b;case /:if (b ! 0)return a / b;elsethrow illegalParameterValue(除数不能为0);}
}/*使用全部是二元操作符的前缀表达式创建二叉树*/
/*从尾元素开始遍历表达式的元素*/
/*如果是数据则生成binaryTreeNode并入栈*/
/*如果不是数据则生成binaryTreeNode从栈中弹出两个数据形成其子树,第一个弹出的是其左子树第二个弹出的是其右子树然后再将当前结点入栈*/
templateclass E
binaryTreeNodeE* binaryTreeChainsE::preExprCreateTree(E expression[],int length)
{stackbinaryTreeNodeE* st;//用于存储已经处理的数据生成的binaryTreeNodebinaryTreeNodeE* temp nullptr;for (int i length-1; i 0; i--){/*如果是数据则生成二叉树结点入栈*/if (expression[i] 0 expression[i] 9){temp new binaryTreeNodeE(expression[i]);st.push(temp);}else{temp new binaryTreeNodeE(expression[i]);temp-leftChild st.top();st.pop();temp-rightChild st.top();st.pop();st.push(temp);}}return temp;
}/*使用全部是二元操作符的中缀表达式(包含括号以表明优先级)创建二叉树*/
/*如果是数据则生成binaryTreeNode并入数据栈*/
/*
操作符处理规则如果当前操作符优先级大于操作符栈的顶部元素直接入操作符栈如果当前操作符优先级小于或等于操作符栈的顶部元素先将顶部元素出操作符栈再将当前操作符入操作符栈当前操作符为左括号时直接入栈当前操作符为右括号时让栈顶到左括号为止的操作符出操作符栈括号不出现在后缀表达式中
出操作符栈时生成当前符号的binaryTreeNode其右子树为数据栈的栈顶元素数据栈顶元素出栈其左子树为数据栈当前的栈顶元素数据栈顶元素出栈当前符号binaryTreeNode入数据栈。
*/
/*获取操作符优先级的getPriority()函数是一个非成员函数*/
templateclass E
binaryTreeNodeE* binaryTreeChainsE::inExprCreateTree(E expression[], int length)
{stackbinaryTreeNodeE* st;//用于存储已经处理的数据生成的binaryTreeNodestackE opStack;binaryTreeNodeE* temp nullptr;E data;for (int i 0; i length; i){data expression[i];/*如果是数据则生成二叉树结点入栈*/if (data 0 data 9){temp new binaryTreeNodeE(data);st.push(temp);}else{if (opStack.empty())opStack.push(data);elseswitch (data){case (:opStack.push(data); break;//当遇到左括号时直接将其入栈case )://当遇到右括号时让栈顶到左括号的操作符出栈while (opStack.top() ! (){temp new binaryTreeNodeE(opStack.top());opStack.pop();temp-rightChild st.top();st.pop();temp-leftChild st.top();st.pop();st.push(temp);}opStack.pop();//让(出栈break;/*当遇到 - * /时,当其优先级大于栈顶元素时入栈否则先将栈顶元素出栈再将当前元素入栈*/case :case -:case *:case /:if (getPriority(data) getPriority(opStack.top()))opStack.push(data);else{temp new binaryTreeNodeE(opStack.top());opStack.pop();temp-rightChild st.top();st.pop();temp-leftChild st.top();st.pop();st.push(temp);}break;default:break;}/*当检查到中缀表达式的最后一个元素且栈非空时将栈中的元素全部输出到后缀表达式*/if (!opStack.empty() i length - 1)while (!opStack.empty()){temp new binaryTreeNodeE(opStack.top());opStack.pop();temp-rightChild st.top();st.pop();temp-leftChild st.top();st.pop();st.push(temp);}}}return temp;
}/*使用全部是二元操作符的后缀表达式创建二叉树*/
/*从首元素开始遍历表达式的元素*/
/*如果是数据则生成binaryTreeNode并入栈*/
/*如果不是数据则生成binaryTreeNode从栈中弹出两个数据形成其子树,第一个弹出的是其右子树第二个弹出的是其左子树然后再将当前结点入栈*/
templateclass E
binaryTreeNodeE* binaryTreeChainsE::postExprCreateTree(E expression[], int length)
{stackbinaryTreeNodeE* st;//用于存储已经处理的数据生成的binaryTreeNodebinaryTreeNodeE* temp nullptr;for (int i 0; i length; i){/*如果是数据则生成二叉树结点入栈*/if (expression[i] 0 expression[i] 9){temp new binaryTreeNodeE(expression[i]);st.push(temp);}else{temp new binaryTreeNodeE(expression[i]);temp-rightChild st.top();st.pop();temp-leftChild st.top();st.pop();st.push(temp);}}return temp;
}#endif_28binaryTreeChains.cpp
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月27日09点44分
Last Version: V1.0
Descriptions: 用链表表示的二叉树.cpp
笔记1.静态函数指针初始化格式void (*binaryTreeChainsE::visit)(binaryTreeNodeE*) 0;2.不能单独专门化成员模板函数只能针对整个类专门化。3.在模板函数中可以使用typeid()区别对待特定数据类型。
本程序注意事项1.所有关于前缀、后缀、中缀表达式的全部使用了char类型代表元素char类型数组存储整个表达式
*/
#include _2myFunctions.h
#include _28binaryTreeChains.h
/*二叉树应用的全局变量*/
/*设置信号放大器*/
int tolerance 3;//设置容忍值为3
/*并查集*/
treeUnionFindNode* node;void binaryTreeChainsTest()
{cout endl ******************************binaryTreeChainsTest()函数开始********************************** endl;cout endl 测试成员函数******************************************* endl;cout 输入**************************** endl;cout 默认构造函数******************** endl;binaryTreeChainsint a;a.input();cout a.preOrderOutput() ;a.preOrderOutput();cout 复制构造函数******************** endl;binaryTreeChainsint b(a);cout b.preOrderOutput() ;b.preOrderOutput();cout 前序中序构造函数**************** endl;int preOrder[] { 1, 2, 4, 5, 3,7, 6 };int inOrder[] { 4, 2, 5, 1, 7, 3,6 };binaryTreeChainsinte(preOrder, inOrder, 7,false);cout e.preOrderOutput() ;e.preOrderOutput();cout e.inOrderOutput() ;e.inOrderOutput();cout e.postOrderOutput() ;e.postOrderOutput();cout 后序中序构造函数**************** endl;int postOrder[] { 4,5,2,7,6,3,1 };binaryTreeChainsintf(postOrder, inOrder, 7,true);cout f.preOrderOutput() ;f.preOrderOutput();cout f.inOrderOutput() ;f.inOrderOutput();cout f.postOrderOutput() ;f.postOrderOutput();cout 输出**************************** endl;cout 前序输出************************ endl;cout a.preOrderOutput() ;a.preOrderOutput();cout b.preOrderOutput() ;b.preOrderOutput();//迭代函数遍历cout a.iterativePreOrder() ;vectorint result a.iterativePreOrder();vectorint::iterator ite;ite result.begin();for (; ite ! result.end(); ite) {cout *ite ;}cout endl;cout 中序输出************************ endl;//递归遍历cout a.inOrderOutput() ;a.inOrderOutput();cout b.inOrderOutput() ;b.inOrderOutput();//迭代函数遍历cout a.iterativeInOrder() ;result a.iterativeInOrder();ite result.begin();for (; ite ! result.end(); ite) {cout *ite ;}cout endl;cout 后序输出************************ endl;cout a.postOrderOutput() ;a.postOrderOutput();cout b.postOrderOutput() ;b.postOrderOutput();//迭代函数遍历cout a.iterativePostOrder() ;result a.iterativePostOrder();ite result.begin();for (; ite ! result.end(); ite) {cout *ite ;}cout endl;cout 层序输出************************ endl;cout a.levelOrderOutput() ;a.levelOrderOutput();cout b.levelOrderOutput() ;b.levelOrderOutput();cout endl;cout empty()************************* endl;cout a.empty() a.empty() endl;cout b.empty() b.empty() endl;cout size()************************** endl;cout a.size() a.size() endl;cout b.size() b.size() endl;cout compare()*********************** endl;cout a.compare(b) a.compare(b) endl;binaryTreeChainsint c;c.input();cout a.compare(c) a.compare(c) endl;cout swapTrees()********************* endl;cout a.preOrderOutput() ;a.preOrderOutput();a.swapTrees();cout a.preOrderOutput() ;a.preOrderOutput();cout height()************************ endl;cout a.height() a.height() endl;cout maxHeightDifference()*********** endl;cout a.maxHeightDifference() a.maxHeightDifference() endl;cout layerMaxNumOfNode()************* endl;cout a.layerMaxNumOfNode() a.layerMaxNumOfNode() endl;cout maxNumOfNodeInLayer()*********** endl;cout a.maxNumOfNodeInLayer() a.maxNumOfNodeInLayer() endl;cout ******************************binaryTreeChainsTest()函数结束********************************** endl;}void treeExpressionsTest()
{cout endl *******************************treeExpressionTest()函数开始*********************************** endl;cout endl 二叉树表达式测试*************************************** endl;/*使用前缀表达式创建二叉树*/cout 前缀表达式构造函数************** endl;char preExpression[] { /,,-,1,2,,3,4,*,,5,6,*,7,8};binaryTreeChainscharg(preExpression, 15, 1);cout g.preOrderOutput() ;g.preOrderOutput();cout g.inOrderOutput() ;g.inOrderOutput();cout g.postOrderOutput() ;g.postOrderOutput();/*使用中缀表达式创建二叉树*/cout 中缀表达式构造函数************** endl;char inExpression[] { (,(,1,-,2,),,(,3,,4,),),/,(,(,5,,6,),*,(,7,*,8,),) };/*这里的长度11是包含括号的长度*/binaryTreeChainschari(inExpression, 27, 2);cout i.preOrderOutput() ;i.preOrderOutput();cout i.inOrderOutput() ;i.inOrderOutput();cout i.postOrderOutput() ;i.postOrderOutput();/*使用后缀表达式创建二叉树*/cout 后缀表达式构造函数************** endl;char postExpression[] { 1,2,-,3,4,,,5,6,,7,8,*,*,/};binaryTreeChainscharh(postExpression, 15, 3);cout h.preOrderOutput() ;h.preOrderOutput();cout h.inOrderOutput() ;h.inOrderOutput();cout h.postOrderOutput() ;h.postOrderOutput();/*计算树表达式的值*/cout 计算树表达式的值**************** endl;cout compulateTree()***************** endl;binaryTreeChainschar d;d.input();cout d.preOrderOutput() ;d.preOrderOutput();cout d.compulateTree() d.compulateTree() endl;/*将后缀表达式转换为中缀表达式*/cout 将后缀表达式转换为中缀表达式**** endl;cout postExprToIn()****************** endl;char postExpr1[9] { 1,2,3,,4,*,5,-, };string inExpr1;postExprToIn(postExpr1, inExpr1, 9);cout postExpr1[9] ;traverse1dArraychar(postExpr1, 9);cout inExpr1 inExpr1 endl;/*将前缀表达式转换为中缀表达式*/cout 将前缀表达式转换为中缀表达式**** endl;cout preExprToIn()******************* endl;char preExpr1[9] { ,1,-,*,,2,3,4,5 };string inExpr2;preExprToIn(preExpr1, inExpr2, 9);cout preExpr1[9] ;traverse1dArraychar(preExpr1, 9);cout inExpr1 inExpr2 endl;/*将中缀表达式转换为后缀表达式需要注意的是一定要使用括号标出优先级*/cout 将中缀表达式转换为后缀表达式**** endl;cout inExprToPost()****************** endl;char inExpr[25] { (,(,-,1,),,(,2,,3,),),/,(,(,,4,),*,(,5,*,6,),) };char postExpr[13];//这里的长度13是后缀表达式的长度inExprToPost(inExpr, postExpr, 25);//这里的长度25是带有括号的中缀表达式的长度cout inExpr[25] ;traverse1dArraychar(inExpr, 25);cout postExpr[13] ;traverse1dArraychar(postExpr, 13);cout 将中缀表达式转换为前缀表达式**** endl;/*将中缀表达式转换为前缀表达式需要注意的是一定要使用括号标出优先级*/cout inExprToPre()****************** endl;char preExpr[13];//这里的长度13是前缀表达式的长度inExprToPre(inExpr, preExpr, 25,13);//这里的长度25是带有括号的中缀表达式的长度cout inExpr[25] ;traverse1dArraychar(inExpr, 25);cout preExpr[13] ;traverse1dArraychar(preExpr, 13);/*计算表达式的值*//*计算前缀表达式的值*/cout 计算前缀表达式的值************** endl;cout preCalculate()****************** endl;char preExpr2[9] { ,1,-,*,,2,3,4,5 };int result preCalculate(preExpr2, 9);cout result result endl;/*计算中缀表达式的值*/cout 计算中缀表达式的值************** endl;cout inCalculate()****************** endl;char inExpr3[17] {(,1,,(,(,(,2,,3,),*,4,),-,5,),)};result inCalculate(inExpr3, 17);cout result result endl;char inExpr4[27] { (,(,5,-,2,),,(,3,,4,),),/,( ,(,1,,1,),*,(,1,*,1,),) };result inCalculate(inExpr4, 27);cout result result endl;/*练习43计算后缀表达式的值*/cout 计算后缀表达式的值************** endl;cout postCalculate()***************** endl;char postExpr2[9] { 1,2,3,,4,*,5,-, };result postCalculate(postExpr2, 9);cout result result endl;cout *******************************treeExpressionTest()函数结束*********************************** endl;
}void treeApplicationTest()
{cout endl ******************************treeApplicationTest()函数开始*********************************** endl;cout endl 二叉树应用测试***************************************** endl;cout 设置信号放大器****************** endl;booster a, b;/*输入*/cin a;// 这里输入0和1cin b;// 这里输入0和2binaryTreeChainsbooster t, u, v, w, x, y;u.makeTree(a, x, x);v.makeTree(b, u, x);u.makeTree(a, x, x);w.makeTree(a, u, x);b.degradeFromParent 3;u.makeTree(b, v, w);v.makeTree(a, x, x);b.degradeFromParent 3;w.makeTree(b, x, x);y.makeTree(a, v, w);w.makeTree(a, x, x);t.makeTree(b, y, w);b.degradeFromParent 0;v.makeTree(b, t, u);v.postOrder(placeBoosters);v.postOrderOutput();v.preOrderOutput();v.inOrderOutput();cout 并查集************************** endl;initialize(10);unite(1, 2);unite(3, 4);unite(1, 3);cout find(1) find(1) find(2) find(2) endl;cout find(3) find(3) find(4) find(4) endl;cout find(5) find(5) find(6) find(6) endl;cout ******************************treeApplicationTest()函数结束*********************************** endl;
}/*非成员函数*/
/*返回元素data在数组中的位置,找到则返回该元素的位置未找到则返回-1*/
templateclass E
int findRootLoc(E list[], E data, int length)
{for (int i 0; i length; i){if (list[i] data)return i;}return -1;
}
/*获取优先级---inExprToPost中使用*/
int getPriority(char op)
{switch (op){case :return 1;case -:return 1;case *:return 2;case /:return 2;case(:return 0;case ):return 0;//右括号的优先级是0default:break;}
}
/*练习38将后缀表达式转换为完全括号化的中缀表达式 完全括号化的中缀表达式如((a)(b))*/
/*参数说明postExpr是后缀表达式数组的指针inExpr用于存储生成的前缀表达式length是后缀表达式的长度*/
void postExprToIn(char postExpr[], string inExpr, int length)
{inExpr.clear();stackstring st;/*用于存储中间结果*/string a, b, c;char data;for (int i 0; i length; i){data postExpr[i];/*当遇到数字时直接入栈*/if (data 0 data 9)st.push({ data,\0 });else{/*每执行一次计算就添加括号每个数据都加括号实在不需要看起来很冗余*/b st.top() \0;st.pop();a st.top() \0;st.pop();c ( a data b );st.push(c);}}if (st.size() 1)inExpr st.top();elseinExpr 后缀表达式非法转换失败;
}
/*练习40将中缀表达式转换为后缀表达式*/
/*条件必须要包含括号---用于区分优先级*/
/*操作数处理规则因为操作数的顺序在中缀、前缀、后缀表达式中是一样的所以在从中缀向前缀或后缀转换时仅需要从左到右扫描中缀表达式*/
/*
操作符处理规则如果当前操作符优先级大于操作符栈的顶部元素直接入栈如果当前操作符优先级小于或等于操作符栈的顶部元素先将顶部元素出栈再将当前操作符入栈当前操作符为左括号时直接入栈当前操作符为右括号时让栈顶到左括号为止的操作符出栈括号不出现在后缀表达式中
*/
/*把扫描到的操作数直接输出而遇到的操作符保留在栈中根据操作符和左括号的优先级来确定输出*/
/*-的优先级为1*和/的优先级为2,栈外左括号的优先级为3栈内左括号的优先级为0*/
/*返回后缀表达式---使用postExpr[]数组返回*/
/*参数说明inExpr为指向中缀表达式的指针postExpr为指向生成的后序表达式的指针length表示中缀表达式的长度*/
void inExprToPost(char inExpr[], char postExpr[], int length)
{int postLoc 0;//记录后缀表达式的当前位置char data 0;//记录读取的前缀表达式的元素stackchar opStack;//用于存储中间过程的符号/*顺序访问中缀表达式*/for (int i 0; i length; i){data inExpr[i];/*当遇到数字时直接将其存储到后缀表达式中*/if (data 0 data 9){postExpr[postLoc] data;postLoc;//后缀表达式存储一个值当前位置1}else/*当遇到的是符号时*/{if (opStack.empty())opStack.push(data);elseswitch (data){case (:opStack.push((); break;//当遇到左括号时直接将其入栈case )://当遇到右括号时让栈顶到左括号的操作符出栈while (opStack.top() ! (){postExpr[postLoc] opStack.top();postLoc;opStack.pop();}opStack.pop();//让(出栈break;/*当遇到 - * /时,当其优先级大于栈顶元素时入栈否则先将栈顶元素出栈再将当前元素入栈*/case :case -:case *:case /:if (getPriority(data) getPriority(opStack.top()))opStack.push(data);else{postExpr[postLoc] opStack.top();postLoc;opStack.pop();opStack.push(data);}break;default:break;}/*当检查到中缀表达式的最后一个元素且栈非空时将栈中的元素全部输出到后缀表达式*/if (!opStack.empty() i length - 1)while (!opStack.empty()){postExpr[postLoc] opStack.top();postLoc;opStack.pop();}}}
}
/*练习41将中缀表达式转换为前缀表达式---从后往前归入前缀表达式*/
/*
首先设定一个操作符栈从右到左顺序扫描整个中缀表达式如果是操作数则直接归入前缀表达式
如果是操作符1.如果是右括号则直接将其入栈2.如果是左括号则将操作符栈中的操作符依次弹栈归入前缀表达式直至遇到右括号将右括号弹栈处理结束3.如果是其他操作符如果栈顶操作符优先级大于当前操作符的优先级则弹栈并归入前缀表达式直至栈顶操作符优先级小于等于当前操作符优先级这时将当前操作符压栈。
*/
/*参数说明inExpr为指向中缀表达式的指针preExpr为指向生成的后序表达式数组的指针inLength表示中缀表达式的长度,preLength表示前缀表达式的长度*/
void inExprToPre(char inExpr[], char preExpr[], int inLength, int preLength)
{int postLoc preLength - 1;//记录前缀表达式的当前位置char data 0;//记录读取的中缀表达式的元素stackchar opStack;//用于存储中间过程的符号/*顺序访问中缀表达式*/for (int i inLength - 1; i 0; i--){data inExpr[i];/*当遇到数字时直接将其存储到前缀表达式中*/if (data 0 data 9){preExpr[postLoc] data;postLoc--;//前缀表达式存储一个值当前位置-1}else/*当遇到的是符号时*/{/*当操作符栈为空时直接将当前操作符入栈*/if (opStack.empty())opStack.push(data);elseswitch (data){case ):opStack.push()); break;//当遇到右括号时直接将其入栈case (://当遇到左括号时让栈顶到右括号的操作符出栈while (opStack.top() ! )){preExpr[postLoc] opStack.top();postLoc--;opStack.pop();}opStack.pop();//让)出栈break;/*当遇到 - * /时,当栈顶元素优先级大于当前操作符优先级时入栈否则将栈顶元素出栈出栈直到当前操作符优先级大于栈顶元素优先级最后将当前元素入栈*/case :case -:case *:case /:while (getPriority(opStack.top()) getPriority(data))/*栈顶元素操作符优先级大于当前操作符优先级就出栈*/{preExpr[postLoc] opStack.top();postLoc--;opStack.pop();}opStack.push(data);/*直到上述条件不成立就入栈*/break;default:break;}/*当检查到中缀表达式的最后一个元素且栈非空时将栈中的元素全部输出到前缀表达式*/if (!opStack.empty() i 0)while (!opStack.empty()){preExpr[postLoc] opStack.top();postLoc--;opStack.pop();}}}
}/*练习39将前缀表达式转换为带括号的中缀表达式 如((ab)(c*d))*/
/*参数说明postExpr是后缀表达式数组的指针inExpr用于存储生成的前缀表达式length是后缀表达式的长度*/
void preExprToIn(char preExpr[], string inExpr, int length)
{inExpr.clear();stackstring st;/*用于存储中间结果*/string a, b, c;char data;for (int i length-1; i 0; i--){data preExpr[i];/*当遇到数字时直接入栈*/if (data 0 data 9)st.push({ data,\0 });else{/*每执行一次计算就添加括号每个数据都加括号实在不需要看起来很冗余*/a st.top() \0;st.pop();b st.top() \0;st.pop();c ( a data b );st.push(c);}}if (st.size() 1)inExpr st.top();elseinExpr 后缀表达式非法转换失败;
}/*计算表达式的值*/
/*前缀表达式计算表达式的值*/
/*参数说明preExpr表示指向前缀表达式数组的指针length表示前缀表达式的长度返回值为计算的结果*/
int preCalculate(char preExpr[], int length)
{stackint st;/*用于存储中间结果*/char data;int a, b;for (int i length - 1; i 0; i--){data preExpr[i];/*当遇到数字时直接入栈*/if (data 0 data 9)st.push(data-0);else{switch (data)//当前结点不是叶子节点时说明他是符号结点{case :a st.top();st.pop();b st.top();st.pop();st.push(a b);break;case -:a st.top();st.pop();b st.top();st.pop();st.push(a - b);break;case *:a st.top();st.pop();b st.top();st.pop();st.push(a * b);break;case /:a st.top();st.pop();b st.top();st.pop();if (b ! 0)st.push(a / b);elsethrow illegalParameterValue(除数不能为0);break;default:break;}}}if (st.size() 1)return st.top();elsecout 前缀表达式非法计算失败 endl;return 0;
}
/*针对不同的操作符执行不同的运算*/
/*参数说明op即为操作符a是左操作数b是右操作数返回值为运算的结果*/
int calculate(char op, int a, int b)
{switch (op){case :return a b;case -:return a - b;case *:return a * b;case /:if (b 0)throw illegalParameterValue(除数不能为0);elsereturn a / b;}
}
/*中缀表达式计算表达式的值*/
/*参数说明inExpr表示指向中缀表达式数组的指针length表示中缀表达式的长度返回值为计算的结果*/
int inCalculate(char inExpr[], int length)
{stackint st;/*用于存储中间结果*/stackchar opStack;/*用于存储操作符*/char data;int a, b;for (int i 0; i length; i){data inExpr[i];/*如果是数据则生成二叉树结点入栈*/if (data 0 data 9)st.push(data - 0);else{if (opStack.empty())opStack.push(data);elseswitch (data){case (:opStack.push(data); break;//当遇到左括号时直接将其入栈case )://当遇到右括号时让栈顶到左括号的操作符出栈while (opStack.top() ! (){/*获取数据*/b st.top();st.pop();a st.top();st.pop();/*获取符号*/data opStack.top();opStack.pop();/*计算结果并入栈*/st.push(calculate(data, a, b));}opStack.pop();//让(出栈break;/*当遇到 - * /时,当其优先级大于栈顶元素时入栈否则先将栈顶元素出栈再将当前元素入栈*/case :case -:case *:case /:if (getPriority(data) getPriority(opStack.top()))opStack.push(data);else{b st.top();st.pop();a st.top();st.pop();st.push(calculate(data, a, b));}break;default:break;}}/*当检查到中缀表达式的最后一个元素且栈非空时将操作符栈中的元素弹出并计算运算的值*/if (!opStack.empty() i length - 1)while (!opStack.empty()){/*获取数据*/b st.top();st.pop();a st.top();st.pop();/*获取符号*/data opStack.top();opStack.pop();/*计算结果并入栈*/st.push(calculate(data, a, b));}}return st.top();
}
/*练习43后缀表达式计算表达式的值*/
/*参数说明postExpr表示指向后缀表达式数组的指针length表示后缀表达式的长度返回值为计算的结果*/
int postCalculate(char postExpr[], int length)
{stackint st;/*用于存储中间结果*/char data;int a, b;for (int i 0; i length; i){data postExpr[i];/*当遇到数字时直接入栈*/if (data 0 data 9)st.push(data - 0);else{switch (data)//当前结点不是叶子节点时说明他是符号结点{case :b st.top();st.pop();a st.top();st.pop();st.push(a b);break;case -:b st.top();st.pop();a st.top();st.pop();st.push(a - b);break;case *:b st.top();st.pop();a st.top();st.pop();st.push(a * b);break;case /:b st.top();st.pop();a st.top();st.pop();if (b ! 0)st.push(a / b);elsethrow illegalParameterValue(除数不能为0);break;default:break;}}}if (st.size() 1)return st.top();elsecout 后缀表达式非法计算失败 endl;return 0;
}/*二叉树的应用---设置信号放大器*/
void placeBoosters(binaryTreeNodebooster* x)
{//计算节点x的衰减值如果衰减值超过容忍值则放置放大器x-element.degradeToLeaf 0; //初始化节点x的 到叶子节点的衰减值为0//计算x的左子树的衰减值根据需求放置放大器//为什么在设置左右子树到叶子的衰减值时方法不一样原因是在设置左子树时没有管其右子树到叶子的衰减值是否更大//但是呢每个根节点都有左子树和右子树该根节点到叶子的衰减值设置为左右子树的最大衰减值因此在设置右子树时//就必须考虑左子树到叶子的衰减是否大于右子树binaryTreeNodebooster* y x-leftChild;if (y ! nullptr){//如果x的左子树为空则不管//计算x到叶子节点的衰减值int degradation y-element.degradeToLeaf y-element.degradeFromParent;//如果衰减值大于容忍值if (degradation tolerance){//则在x的左子树放置放大器y-element.boosterHere true;x-element.degradeToLeaf y-element.degradeFromParent;}else //不需要放大器x-element.degradeToLeaf degradation;//将x到叶子节点的衰减值设置为degradation}//计算节点x的衰减值如果衰减值超过容忍值则放置放大器y x-rightChild;if (y ! nullptr){ //当x的右子树不为空时int degradation y-element.degradeToLeaf y-element.degradeFromParent;if (degradation tolerance){//在x的右子树放置放大器y-element.boosterHere true;degradation y-element.degradeFromParent;}if (x-element.degradeToLeaf degradation)x-element.degradeToLeaf degradation;}
}/*二叉树的应用---并查集*/
void initialize(int numberOfElements)
{//初始化numberOfElements个树每个树都是一个元素node new treeUnionFindNode[numberOfElements 1];
}int find(int theElement)
{//返回元素theElement所在树的根while (!node[theElement].root)//只要节点的root不为true,就一直找他的父节点theElement node[theElement].parent; // move up one levelreturn theElement;
}
/*rootA和rootB是索引*/
void unite(int rootA, int rootB)
{//使用重量规则合并其根不同的树//重量大的作为根节点if (node[rootA].parent node[rootB].parent){node[rootB].parent node[rootA].parent;node[rootA].parent rootB;node[rootA].root false;}else{node[rootA].parent node[rootB].parent;node[rootB].parent rootA;node[rootB].root false;}
}_28binaryTreeNode.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月27日09点44分
Last Version: V1.0
Descriptions: 二叉树的结点结构体
*/
#pragma once
#ifndef _BINARYTREENODE_H_
#define _BINARYTREENODE_H_
templateclass T
struct binaryTreeNode
{T element;binaryTreeNodeT* leftChild,//左子树*rightChild;//右子树/*默认构造函数*/binaryTreeNode() { leftChild rightChild nullptr; }/*只初始化element*/binaryTreeNode(T melement){element melement;leftChild rightChild nullptr;}/*三个元素都初始化*/binaryTreeNode(T melement, binaryTreeNodeT* mleftChild, binaryTreeNodeT* mrightChild){element melement;leftChild mleftChild;rightChild mrightChild;}
};#endif_28binaryTree.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月27日09点43分
Last Version: V1.0
Descriptions: 二叉树的抽象类
*/
#pragma once
#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_
templateclass T
class binaryTree
{
public:virtual ~binaryTree() {}virtual bool empty() const 0;virtual int size() const 0;virtual void preOrder(void (*)(T*)) 0;virtual void inOrder(void (*)(T*)) 0;virtual void postOrder(void (*)(T*)) 0;virtual void levelOrder(void (*)(T*)) 0;
};
#endif_28booster.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年9月17日10点47分
Last Version: V1.0
Descriptions: 二叉树的应用 设置信号放大器 节点结构体
*/
#pragma once
#ifndef _BOOSTER_H_
#define _BOOSTER_H_
#include iostream
using namespace std;struct booster
{int degradeToLeaf, //到叶子结点的衰减degradeFromParent; //父节点到该节点的衰减bool boosterHere; //是否在此节点放置放大器/*重载操作符*/friend ostream operator(ostream out, booster m){out m.boosterHere m.degradeToLeaf m.degradeFromParent ;return out;}/*重载操作符*/friend istream operator(istream in, booster m){cout Please enter the degradeToLeaf:;while (!(in m.degradeToLeaf)){in.clear();//清空标志位while (in.get() ! \n)//删除无效的输入continue;cout Please enter the degradeToLeaf:;}cout Please enter the degradeFromParent:;while (!(in m.degradeFromParent)){in.clear();//清空标志位while (in.get() ! \n)//删除无效的输入continue;cout Please enter the degradeFromParent:;}m.boosterHere 0;return in;}
};
#endif_28treeUnionFindNode.h
#pragma once
#ifndef _TREEUNIONFINDNODE_H_
#define _TREEUNIONFINDNODE_H_
/*
注意事项
1.当且仅当一个节点是当前根节点时他的root域为true;
2.每个根节点的parent域用来记录该树的节点总数规则
1.重量规则若根为i的树的节点数少于根为j的树的节点数则将j作为i的父节点否则将i作为j的父节点。
2.高度规则若根为i的树的高度小于根为j的树的高度则将j作为i的父节点否则将i作为j的父节点。
*/
struct treeUnionFindNode
{int parent; // if true then tree weight// otherwise pointer to parent in treebool root; // true iff roottreeUnionFindNode(){parent 1; root true;}
};
#endif_1myExceptions.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月13日17点38分
Last Version: V1.0
Descriptions: 综合各种异常
*/
#pragma once
#ifndef _MYEXCEPTIONS_H_
#define _MYEXCEPTIONS_H_
#include string
#includeiostreamusing namespace std;// illegal parameter value
class illegalParameterValue
{
public:illegalParameterValue(string theMessage Illegal parameter value){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// illegal input data
class illegalInputData
{
public:illegalInputData(string theMessage Illegal data input){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// illegal index
class illegalIndex
{
public:illegalIndex(string theMessage Illegal index){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// matrix index out of bounds
class matrixIndexOutOfBounds
{
public:matrixIndexOutOfBounds(string theMessage Matrix index out of bounds){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// matrix size mismatch
class matrixSizeMismatch
{
public:matrixSizeMismatch(string theMessage The size of the two matrics doesnt match){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// stack is empty
class stackEmpty
{
public:stackEmpty(string theMessage Invalid operation on empty stack){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// queue is empty
class queueEmpty
{
public:queueEmpty(string theMessage Invalid operation on empty queue){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// hash table is full
class hashTableFull
{
public:hashTableFull(string theMessage The hash table is full){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// edge weight undefined
class undefinedEdgeWeight
{
public:undefinedEdgeWeight(string theMessage No edge weights defined){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// method undefined
class undefinedMethod
{
public:undefinedMethod(string theMessage This method is undefined){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};
#endif_2myFunctions.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月13日17点38分
Last Version: V1.0
Descriptions: 综合各种非成员函数
*/
#pragma once
#ifndef _MYFUNCTIONS_H_
#define _MYFUNCTIONS_H_
#includeiostream
#include _1myExceptions.h
#includecmath
#include exception
using std::min;
using std::endl;
using std::cout;
using std::bad_alloc;
/*交换两数据*/
templateclass V
void Swap(V a, V b)
{V temp a;a b;b temp;
}
/*
作用将数组的长度加倍
输入指针a指向需要改变长度的数组oldLength表示数组原来的长度newLength表示需要改变的新长度
结果将数组扩容/缩容 为newLength
*/
templateclass T
void changeLength(T* a, int oldLength, int newLength)
{if (newLength 0)throw illegalParameterValue(new length must be 0);T* temp new T[newLength];int number min(oldLength, newLength);copy(a, a number, temp);delete[] a;a temp;
}
/*遍历一维数组*/
templateclass T
void traverse1dArray(T* x, int length)
{for (int i 0; i length; i)cout x[i] ;cout endl;
}
/*创建二维数组*/
template class T
bool make2dArray(T** x, int numberOfRows, int numberOfColumns)
{try {//行指针x new T * [numberOfRows];//为每一行分配内存for (int i 0; i numberOfRows; i)x[i] new int[numberOfColumns];return true;}catch (bad_alloc) { return false; }
}/*遍历二维数组*/
templateclass T
void traverse2dArray(T** x, int numberOfRows, int numberOfColumns)
{for (int i 0; i numberOfRows; i){for (int j 0; j numberOfColumns; j){cout.width(4);cout x[i][j] ;}cout endl;}
}
#endif运行结果
******************************binaryTreeChainsTest()函数开始**********************************测试成员函数*******************************************
输入****************************
默认构造函数********************
Please enter the tree element:1
Please enter the tree element:2
Please enter the tree element:999
Please enter the tree element:999
Please enter the tree element:3
Please enter the tree element:999
Please enter the tree element:999
a.preOrderOutput() 1 2 3
复制构造函数********************
b.preOrderOutput() 1 2 3
前序中序构造函数****************
e.preOrderOutput() 1 2 4 5 3 7 6
e.inOrderOutput() 4 2 5 1 7 3 6
e.postOrderOutput() 4 5 2 7 6 3 1
后序中序构造函数****************
f.preOrderOutput() 1 2 4 5 3 7 6
f.inOrderOutput() 4 2 5 1 7 3 6
f.postOrderOutput() 4 5 2 7 6 3 1
输出****************************
前序输出************************
a.preOrderOutput() 1 2 3
b.preOrderOutput() 1 2 3
a.iterativePreOrder() 1 2 3
中序输出************************
a.inOrderOutput() 2 1 3
b.inOrderOutput() 2 1 3
a.iterativeInOrder() 2 1 3
后序输出************************
a.postOrderOutput() 2 3 1
b.postOrderOutput() 2 3 1
a.iterativePostOrder() 2 3 1
层序输出************************
a.levelOrderOutput() 1 2 3
b.levelOrderOutput() 1 2 3empty()*************************
a.empty() 0
b.empty() 0
size()**************************
a.size() 3
b.size() 3
compare()***********************
a.compare(b) 1
Please enter the tree element:66
Please enter the tree element:88
Please enter the tree element:999
Please enter the tree element:999
Please enter the tree element:99
Please enter the tree element:999
Please enter the tree element:999
a.compare(c) 0
swapTrees()*********************
a.preOrderOutput() 1 2 3
a.preOrderOutput() 1 3 2
height()************************
a.height() 2
maxHeightDifference()***********
a.maxHeightDifference() 0
layerMaxNumOfNode()*************
a.layerMaxNumOfNode() 2
maxNumOfNodeInLayer()***********
a.maxNumOfNodeInLayer() 2
******************************binaryTreeChainsTest()函数结束*****************************************************************treeExpressionTest()函数开始***********************************二叉树表达式测试***************************************
前缀表达式构造函数**************
g.preOrderOutput() / - 1 2 3 4 * 5 6 * 7 8
g.inOrderOutput() 1 - 2 3 4 / 5 6 * 7 * 8
g.postOrderOutput() 1 2 - 3 4 5 6 7 8 * * /
中缀表达式构造函数**************
i.preOrderOutput() / - 1 2 3 4 * 5 6 * 7 8
i.inOrderOutput() 1 - 2 3 4 / 5 6 * 7 * 8
i.postOrderOutput() 1 2 - 3 4 5 6 7 8 * * /
后缀表达式构造函数**************
h.preOrderOutput() / - 1 2 3 4 * 5 6 * 7 8
h.inOrderOutput() 1 - 2 3 4 / 5 6 * 7 * 8
h.postOrderOutput() 1 2 - 3 4 5 6 7 8 * * /
计算树表达式的值****************
compulateTree()*****************
Please enter the tree element:
Please enter the tree element:2
Please enter the tree element:#
Please enter the tree element:#
Please enter the tree element:3
Please enter the tree element:#
Please enter the tree element:#
d.preOrderOutput() 2 3
d.compulateTree() 5
将后缀表达式转换为中缀表达式****
postExprToIn()******************
postExpr1[9] 1 2 3 4 * 5 -
inExpr1 (1(((23)*4)-5))
将前缀表达式转换为中缀表达式****
preExprToIn()*******************
preExpr1[9] 1 - * 2 3 4 5
inExpr1 (1(((23)*4)-5))
将中缀表达式转换为后缀表达式****
inExprToPost()******************
inExpr[25] ( ( - 1 ) ( 2 3 ) ) / ( ( 4 ) * ( 5 * 6 ) )
postExpr[13] 1 - 2 3 4 5 6 * * /
将中缀表达式转换为前缀表达式****
inExprToPre()******************
result 16
result 5
计算后缀表达式的值**************
postCalculate()*****************
result 16
*******************************treeExpressionTest()函数结束*****************************************************************treeApplicationTest()函数开始***********************************二叉树应用测试*****************************************
设置信号放大器******************
Please enter the degradeToLeaf:0
Please enter the degradeFromParent:1
Please enter the degradeToLeaf:0
Please enter the degradeFromParent:2
0 0 1 0 0 3 1 3 1 0 0 1 1 1 3 0 0 1 0 1 2 0 0 1 0 1 1 1 3 3 0 3 0
0 3 0 1 1 3 1 3 1 0 0 1 0 0 3 0 0 1 1 3 3 0 1 2 0 0 1 0 1 1 0 0 1
0 0 1 1 3 1 0 0 3 1 1 3 0 0 1 0 3 0 0 0 1 0 1 2 1 3 3 0 0 1 0 1 1
并查集**************************
find(1) 1 find(2) 1
find(3) 1 find(4) 1
find(5) 5 find(6) 6
******************************treeApplicationTest()函数结束***********************************Process finished with exit code 0
