58 lines
3.7 KiB
TeX
58 lines
3.7 KiB
TeX
|
\documentclass[实验报告模板]{subfiles}
|
|||
|
|
|
|||
|
|
\renewcommand{\mydate}{
|
|||
|
|
2023/12/15
|
|||
|
|
}
|
|||
|
|
\renewcommand{\mychapternum}{7}
|
|||
|
|
|
|||
|
|
\begin{document}
|
|||
|
|
\mytitle
|
|||
|
|
\begin{enumerate}
|
|||
|
|
\myitem{实验目的}{
|
|||
|
|
\item 使用第七章的知识解决查找树的综
|
|||
|
|
合问题。
|
|||
|
|
}
|
|||
|
|
\myitem{实验内容}{
|
|||
|
|
\item 给出 N 个正整数作为二叉排序树的节点插入顺序.判断这串序列是否是
|
|||
|
|
该二叉树的先序序列或者是该二叉排序树的镜像树的先序序列.镜像树
|
|||
|
|
指的是交换根结点的左右子树形成的二叉树，如果对于输入的序列与二
|
|||
|
|
叉排序树的先序序列一致，则输出 Yes，并输出该二叉排序树的后序序
|
|||
|
|
列.若对于输入的序列与二叉排序树的镜像树的先序序列一致，则输出
|
|||
|
|
Yes，并输出该二叉排序树的后序序列.其余情况输出 No.
|
|||
|
|
|
|||
|
|
\item 根据二叉排序树的镜像树的后序遍历序列作为顺序，构造平衡二叉树。
|
|||
|
|
}
|
|||
|
|
\myitem{实验原理}{
|
|||
|
|
\item 程序设计原理。
|
|||
|
|
}
|
|||
|
|
\myitem{实验步骤}{
|
|||
|
|
\item 问题抽象
|
|||
|
|
\item 编写程序
|
|||
|
|
\item 调试程序
|
|||
|
|
\item 完善总结
|
|||
|
|
}
|
|||
|
|
\myitem{调试过程、结果和分析}{
|
|||
|
|
\item 树的结构确实不好调试，尤其是平衡二叉树，但好在可以进行中序遍历，正确的情况下中序遍历的结果应该是排好序的；
|
|||
|
|
\item 对于镜像树，可以修改比较操作的函数定义，就像C++内置的make\_heap一样，当然由于镜像树是对称的，可以直接在遍历时先遍历右子树，再遍历左子树，也能实现；
|
|||
|
|
\item 两道题的输入输出有关联性，第二题的输入是第一题的输出但又不完全是，第一题输出的是原二叉树的后序遍历结果，但第二题要使用第一题的镜像数的后序遍历结果，因此可以使用文件记录输出结果，第二题就可以进行输入重定向。
|
|||
|
|
}
|
|||
|
|
\myitem{总结}{
|
|||
|
|
\item 遵循指针应在初始化时分配资源，以及将资源交给变量作用域和变量生命周期自动管理，此次代码中将每个节点的左右指针都使用unique\_ptr定义，这样就不需要自己进行delete删除分配的资源了；
|
|||
|
|
\item 但是使用unique\_ptr要注意，此指针指向的对象不能再被其他对象指向，因此需要使用move进行转移资源的所有权，这在旋转子树时尤其明显；
|
|||
|
|
\item 借助std::function和匿名函数，我们可以很方便地实现简单的函数回调，尤其是涉及到类和对象的成员函数的时候；
|
|||
|
|
\item 类中的this是常量指针，是不能改变它所指向的地址的，即不能对*this赋值；
|
|||
|
|
\item C++中有类似Python的迭代器，也能用匿名函数实现类似JavaScript的回调；
|
|||
|
|
\item 但是C++中没法直接使用 this->left\_child \&\& this->left\_child->postorder\_traversal(output)，因为逻辑与操作中的函数调用会返回void，而void无法转换为bool类型；
|
|||
|
|
\item C++中的模板自动类型推断，还有解包参数，和Python、JavaScript中有相似之处，但又不完全一样，仍需深入了解。
|
|||
|
|
}
|
|||
|
|
\myitem{附件}{
|
|||
|
|
\itemsep 5em
|
|||
|
|
\item 第七章作业1.cpp
|
|||
|
|
\inputminted[]{cpp}{../C++/第七章作业/第七章作业1.cpp}
|
|||
|
|
\item 第七章作业2.cpp
|
|||
|
|
\inputminted[]{cpp}{../C++/第七章作业/第七章作业2.cpp}
|
|||
|
|
\item CMakeLists.txt
|
|||
|
|
\inputminted[]{cmake}{../C++/第七章作业/CMakeLists.txt}
|
|||
|
|
}
|
|||
|
|
\end{enumerate}
|
|||
|
|
\end{document}
|