实验四 二叉树
[toc]
- 掌握二叉树的逻辑结构定义和各种存储结构的实现。
- 熟练运用二叉树的各种存储结构以及各种基本操作。
- 根据实际问题的需要，选择二叉树适合的存储结构解决问题。
- 在二叉链表类模板中增加函数成员 CountLeaf()，统计二叉树中叶子结点的数目。
- 在二叉链表类模板中增加函数成员 Revolut()，实现二叉树中所有结点的左右子树交换。
- 在二叉链表类模板中增加函数成员 CountBreadth()，统计二叉树的最大宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。
- 在二叉链表类模板中增加函数成员 NonRecurringInOrder()，实现非递归中序遍历二叉树。
- 在中序线索二叉树类模板中增加函数成员 ReInOrder()，通过从中序序列最后一个结点开始依次找当前结点的前驱来逆中序遍历二叉树。
- 在中序线索二叉树类模板中增加函数成员 InsertLeftChild(p，e)，实现在中序线索二叉树指定结点 p 上插入左孩子结点 e。
- 在中序线索二叉树类模板中增加函数成员 PostOrder()，实现不用栈后序遍历二叉树。
- 修改最小堆中构造函数 MinHeap(ElemType a［］，int maxSize，int n)，从空堆开 始依次插入数组 a 中的元素构造堆。
- 把最小堆的类模板改造成最大堆。
参考二叉树的二叉链表类模板，设计并实现二叉树的顺序存储表示。增加函数成员，求离两个元素（编号为 i 和 j）最近的共同祖先。
参考二叉树的二叉链表类模板，设计并实现二叉树的三叉链表表示。增加函数成员，实现非递归先序、后序遍历二叉树。
参考中序线索二叉树的类模板，设计并实现后序线索二叉树。增加函数成员，利用线索求指定结点 p 在后序序列中的后继结点。
参考中序线索二叉树的类模板，设计并实现先序线索二叉树。增加函数成员，利用线索求指定结点 p 在先序序列中的后继结点。
一棵二叉树，根节点标记为（1,1），规定：如果一个结点标记为（a，b），则它的左 孩子（如果存在）标记为（a＋b，b），它的右孩子（如果存在）标记为（a，a＋b）。现在 已知某个结点的标记为（a，b），求从根节点开始需要经过多少次左分支和多少次右分支 才能到达结点（a，b）。
输入文件第一行只有一个整数 n，表示测试的数据组数。 接下来 n 行（第 2-n＋1 行），每行包括两个整数 a 和 b。
输出有 n 行，每行包括两个整数，分别表示从根节点开始到结点（a，b）需要经过的 左分支数和右分支数。
2
42 1
3 4
41 1
2 1
表达式可以用一棵二叉树表示，叶子结点代表操作数，分支结点代表操作符。对于表示简单四则运算表达式（操作数只有变量和常量，没有数组元素和函数）的表达式二叉树，要求实现以下功能：
- 输入表达式，生成其二叉树表示。
- 对于一棵构造好的表达式二叉树，输出相应的中缀表达式（不允许有冗余的括号）。所谓冗余的括号就是去掉括号后不影响表达式的计算顺序。例如，“$(c+b)+a$”中的括号是冗余的，它可以表示成不冗余的“$c+b+a$”形式。例如，如图所示的表达式二叉树，对应的中缀表达式为：
$a-(b-c)/(e*(f+g))$ 。 - 对于一棵构造好的表达式二叉树，输出相应的后缀表达式。例如，表达式“$a-(b-c)/(e*(f+g))$”的后缀表达式为：$abc-efg+*/-$。
- 对于操作数都是正数的表达式二叉树，计算该表达式的值。
- 输出表达式二叉树的树形结构。
提供一个菜单，方便选择不同的功能。根据选择的功能输出相应的结果。
有一棵高度为 h 的满二叉树，所有结点从上到下、自左向右编号为：$1, 2, 3, \cdots, 2^h+1$ 在根结点处放一个小球，它会沿着分支往下滑落到叶子结点。除叶子结点外，每个结点上都有一个开关，初始全部关闭，当有小球经过结点时，开关状态会改变。小球到达结点时，如果该结点开关处于关闭状态，则小球往左分支滑落，否则往右分支滑落，直到滑到叶子结点。
输入多组数据，每组数据一行两个数，分别表示满二叉树的高度 h（$h≤20$）和小球数目 n （$n≤2h-1$）。
输出第 n 个小球所滑到的叶子结点编号。
4 2
3 4
10 1
2 2
8 128
16 1345
12
7
512
3
255
36358