【东华大学oj】二叉树：后序遍历非递归实现

2024-06-18 16:34| 来源: 网络整理| 查看: 265

二叉树：后序遍历非递归实现

时间限制: 1s

类别: DS：树->中等

问题描述

目的：使用C++模板设计二叉树的抽象数据类型（ADT）。并在此基础上，使用二叉树ADT的基本操作，设计并实现简单应用的算法设计。

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

（2）ADT的简单应用：使用该ADT设计并实现若干应用二叉树的算法设计。

应用5：要求设计一个非递归算法，实现二叉树的后序遍历。二叉树的存储结构的建立参见二叉树应用1。

提示：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

参考函数原型：

//二叉树后序遍历的非递归算法

template

void PostOrder( BinaryTree &T );

输入说明

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

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

输出说明

第一行：后序遍历的结果

#include #include #include #include #include using namespace std; template struct BinaryTreeNode { ElemType data; BinaryTreeNode* LChild; BinaryTreeNode* RChild; BinaryTreeNode(ElemType item = ElemType(), BinaryTreeNode* L = nullptr, BinaryTreeNode* R = nullptr) : data(item), LChild(L), RChild(R){} }; template class BinaryTree { private: BinaryTreeNode* root; void destroy(BinaryTreeNode*& node) { if (node != nullptr) { destroy(node->LChild); destroy(node->RChild); delete node; node = nullptr; } } void preorder(BinaryTreeNode* node, vector& result) { if (node != nullptr) { result.push_back(node->data); preorder(node->LChild, result); preorder(node->RChild, result); } } void inorder(BinaryTreeNode* node, vector& result) { if (node != nullptr) { inorder(node->LChild, result); result.push_back(node->data); inorder(node->RChild, result); } } void postorder(BinaryTreeNode* node, vector& result) { if (node != nullptr) { postorder(node->LChild, result); postorder(node->RChild, result); result.push_back(node->data); } } public: BinaryTree() : root(nullptr){} ~BinaryTree() { destroy(root); } void createFromPreorder(vector elements, ElemType empty) { auto it = elements.begin(); root = create(it, elements.end(), empty); } BinaryTreeNode* create(typename vector::iterator& it, typename vector::iterator end, ElemType empty) { if (it == end || *it == empty) { return nullptr; } BinaryTreeNode* node = new BinaryTreeNode(*it); ++it; node->LChild = create(it, end, empty); ++it; node->RChild = create(it, end, empty); return node; } // 非递归后序遍历算法 void PostOrderTraversal() { stack S; BinaryTreeNode* p = root; BinaryTreeNode* lastVisited = nullptr; vector result; while (p != nullptr || !S.empty()) { if (p != nullptr) { S.push(p); p = p->LChild; } else { BinaryTreeNode* topNode = S.top(); if (topNode->RChild != nullptr && topNode->RChild != lastVisited) { p = topNode->RChild; } else { S.pop(); result.push_back(topNode->data); lastVisited = topNode; } } } // 输出结果 for (size_t i = 0; i < result.size(); ++i) { cout item) { elements.push_back(item); } BinaryTree tree; tree.createFromPreorder(elements, nullSymbol); tree.PostOrderTraversal(); cout

【本文地址】

公司简介

联系我们