算法作业
代做算法作业 将下列算法补充完整，使其能将一个用带双标记的层次表示法表示的森林转换为左子结点/右兄弟表示。// 注：代码中为了简洁将 top( )和 pop( )合并为了 Pop( )，即读栈顶并出栈。template <T>struct DualTagTreeNode
三、 算法填空(每空 2 分，共 10 分) 代做算法作业
将下列算法补充完整，使其能将一个用带双标记的层次表示法表示的森林转换为左子结点/右兄弟表示。
// 注：代码中为了简洁将 top( )和 pop( )合并为了 Pop( )，即读栈顶并出栈。
template <T>
struct DualTagTreeNode <T> {
int ltag; // 左标记
T info;
int rtag; // 右标记
}; // 带双标记的层次表示法的结点类
struct TreeNode<T> {
public: 代做算法作业
T info;
TreeNode* Child;
// 指向最左子结点的指针
TreeNode* Sibling;
// 指向右兄弟的指针
}; // 左子/右兄弟结点中的结点类
TreeNode<T>* Convert (DualTagTreeNode* nodes, int size) {
// nodes 为带双标记的层次法表示的森林的序列，size 为序列长度。
queue <TreeNode <T>*> aQueue;
TreeNode<T> *pointer = new TreeNode<T>;
root = pointer;
// 根结点
for (int i=0; i<size-1; i++) {
pointer->info = nodes[i].info;
if(nodes[i].ltag == 1)
填空 1 ;
else
填空 2 ;
TreeNode<T>* temppointer = new TreeNode<T>;
if(nodes[i].rtag == 0) { // 有右兄弟，其后的结点即为其右兄弟
pointer->Sibling = temppointer;
}
else { // 否则，Sibling 为空并出队列
pointer->Sibling = NULL;
pointer = aQueue.Pop(); 代做算法作业
填空 3 ;
}
填空 4 ;5
}
// 处理最后一个结点
填空 5 ;
pointer->Child = NULL;
pointer->Sibling = NULL;
}
四、 算法设计与实现 (每题 10 分，共 20 分) 代做算法作业
- 请设计一个算法，判断输入的一个由 1,2,…,n 组成的排列是否可以通过入栈、出栈操作 得到有序序列，并输出相应入栈出栈序列。请给出算法伪代码，并分析算法的时间复杂度。
例如：
输入序列 4 3 1 2；
输出 Yes; push push push pop push pop pop pop 代做算法作业
- 请设计一个算法对树序列化和反序列化（所谓序列化是将一棵树用一个字符串表示；而反 序列化则为根据字符串恢复原本的树结构）。此处对序列化的格式没有限制，可以自定义。 可写伪代码，需要相应的注释；或者写出详细算法设计思路。
五、 分析证明题 (10 分)
设一棵度为 k 的非空树上的叶子结点数为 ?0，度为 i 的结点数为 ??(1 ≤ i ≤ k)。试证明以下 关系成立：
发表回复
要发表评论，您必须先登录。