- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我已经编写了一个红黑树实现,具有内置的顺序遍历(使用嵌套的 class Iterator
)。
我正在寻找一种(迭代,如果可能的话)算法,该算法使用中序遍历以图形方式打印二叉树。
打印方向不相关,即命令行输出中的树可以像这样定向(格式化):
2
/ \
1 4
/ \
3 5
或者像这样:
|1
|
|
2
| |3
| |
|4
|
|5
甚至是颠倒的,但是应该使用 in-oder 遍历打印树,使用下面提供的方法:
void Iteraor::first(); // Traverses to the first node.
void Iterator::next(); // Traverses to the next node.
void Iterator::last(); // Traverses to the last node.
所以有可能做这样的事情:
RBTree tree;
/* Tree init. */
Iterator from(&tree), until(&tree);
from.first();
until.last();
for (Iterator i = from; i != until; i.next()) {
// PRINTING.
}
这是原始代码:
/** A program for Red-Black Tree manipulation: insertion and value retrieval.
* All position relations (first, last, previous, next) are in-order.
*/
class RBTree {
struct Node {
enum class Colour : bool { RED, BLACK };
int value;
Node *left, *right, *parent;
Colour colour;
public:
/* ... */
};
class Iterator {
class Stack {
/* ... */
};
Stack stack;
const RBTree* const tree; // Once set, neither the reference nor the referenced object's attributes can be modified.
Node* pointer;
public:
Iterator(const RBTree*);
void first();
void next();
void last();
/* ... */
Node* getNode() const;
bool operator != (const Iterator&) const;
};
Node *root;
Iterator iterator;
public:
RBTree() : root(nullptr), iterator(this) {}
/* ... */
bool printTree() const;
~RBTree() { deleteTree(); }
};
// TREE // public: //
/* ... */
bool RBTree::printTree() const {
if (root != nullptr) {
// print ??
return true;
}
else
return false;
}
// NODE: Ensures the proper connection. //
void RBTree::Node::setLeft(Node *p_left) {
left = p_left;
if (p_left != nullptr)
p_left->parent = this;
}
void RBTree::Node::setRight(Node *p_right) {
right = p_right;
if (p_right != nullptr)
p_right->parent = this;
}
// ITERATOR //
RBTree::Iterator::Iterator(const RBTree* p_tree) : tree(p_tree), pointer(p_tree->root) {}
// Traverses to the first node (leftmost).
void RBTree::Iterator::first() {
if (pointer != nullptr) {
while (true) {
if (pointer != nullptr) {
stack.push(pointer);
pointer = pointer->left;
}
else {
pointer = stack.peek();
break;
}
}
}
}
// Traverses to next node in-order.
void RBTree::Iterator::next() {
if (pointer != nullptr) {
if (!stack.isEmpty()) {
pointer = stack.pop();
if (pointer->right != nullptr) {
pointer = pointer->right;
first();
}
}
}
}
// Traverses to the last node (rightmost).
void RBTree::Iterator::last() {
pointer = tree->root;
if (pointer != nullptr)
while (pointer->right != nullptr)
pointer = pointer->right;
stack.clear();
}
/* ... */
RBTree::Node* RBTree::Iterator::getNode() const {
return pointer;
}
bool RBTree::Iterator::operator != (const Iterator& p_iterator) const {
return pointer != p_iterator.pointer ? true : false;
}
我已经研究了 similar question 的回复, 但是没有一个算法利用了中序遍历(而且大部分都是递归的)。
编辑:
按照@nonsensickle 的建议,代码被精简到最低限度。
最佳答案
使用迭代算法进行中序遍历的规范方法是维护需要打印的节点的堆栈(或后进先出队列)。每个循环迭代做两件事之一:
如果您不在叶节点上,则将当前节点压入堆栈并移动到其最左边的子节点。
如果您在一片叶子上,打印它,从堆栈中弹出顶部节点,打印它,然后继续到它最右边的 child 。
你继续,直到你的堆栈为空并且你在一片叶子上。
节点间分支的格式和图形表示的生成显然取决于您。请记住,它需要一些额外的状态变量。
编辑
我所说的“一些额外的状态变量”是这个意思。
要提供 pretty-print ,您需要跟踪三件事:
您当前要打印的节点位于树的哪个级别(从底部开始计算)。这会告诉您(部分)缩进多远(或者如果您使用的是 2D 绘图库,它会从 Canvas 的边缘偏移)。
您当前要打印的节点是左子节点还是右子节点。这会(再次)告诉您它与其兄弟之间的缩进距离,以及连接它与父级的分支的方向。
您的节点距离“中心”有多少个节点。这对于与其(非兄弟)邻居的适当间距也很有用。
可能可以使用较少的迭代到迭代状态,但这对我有用。
关于c++ - 二叉树 : iterative inorder print,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33769837/
在一些情况下,能够比较二叉搜索树中的最后一个元素和第一个元素,元素对,将被证明是有用的。 例如:找到 2 个总和为给定数字的元素。 (最快的方法是尝试将最小和最大的数字相加,然后根据与给定数字的结果总
顺序、前序和后序名称背后的逻辑是什么?他们为什么这么叫? 为了。为什么是“在”这个词,“在”是什么? 预购。 “前”,意思是“上一个”,但前一个是什么? 下单。 “后”的意思是“之后”,但是之后呢?
我试图编写一段简单的代码来通过 inorder 遍历来遍历二叉搜索树。我能够完美地纠正插入代码,因为调试器显示的树与我想要的一模一样。但是我的递归遍历没有给出正确的结果。这是我的调试器的屏幕截图: 左
最近,我的问题被标记为重复的,比如this,即使没有。所以,让我从下面开始,然后我将解释我的问题。 为什么这个问题不是重复的? 我不想问如何创建一个二叉树时,顺序和前序遍历给出。我要求证明,inord
我的任务是实现一个函数,该函数迭代 bin 树并按顺序返回其所有值的数组。代码如下: interface BinTree { root: number; left?: BinTree; right?:
很简单的问题: 如何递归地创建使用此构造函数的二叉搜索树数组(按顺序): public class OrderedSet> { private class TreeNode { pri
下面提到的示例树可能的总遍历组合是 DLR, LDR, LRD, DRL, RDL, RLD 示例树 [ D=root , L= LeftNode , R= RightNode ] D / \
如何使用回调模式和 Promises 实现“inOrder”。 var logOne = setTimeout(function() { console.log("one!"); },
我写了这段代码- #include #include struct nd{ int data; struct nd *left; struct nd *right; }; struc
我必须编写一个函数,它接受一棵树作为参数,并将其作为按顺序排列的字符串返回。 这就是我得到的。 public static String concatInOrder( StringTreeNode t
我目前正在大学学习数据结构类(class),我们正在学习使用链表的二叉搜索树。我们已经递归地检查了 inOrder 方法,但我想尝试迭代地执行该方法。经过一些研究,我意识到我必须在遍历树时使用堆栈。我
我正在为家庭作业实现一个 InOrder 迭代器,这意味着迭代器是这样前进的: 拜访左孩 访问节点 拜访正确的 child 还有这些复杂性限制:遍历整棵树的运行时复杂度应为 o(n),其中 n 是树中
我在打印二叉树的有序遍历时遇到一些问题。即使在树中插入许多项目后,它也只打印 3 个项目。 public class BinaryTree { private TreeNode root;
我正在尝试编写一个单元测试来检查方法是否按顺序调用。为此,我使用 Mockito 的 inOrder.verify() ,如下所示: @Test public void shouldExecuteAl
尝试将 InOrder 遍历的输出返回到 Java JLabel。我能够返回 ArrayList 的内容,但需要输出为不带 [,,,] 的字符串。我确信这是一个简单的解决方案,但我已经被困了一段时间尝
我正在测试使用 Architecture Components 中的 Room 库生成的 DAO 类。我想检查连接多个表的查询返回的 LiveData 是否会在数据更改时更新。 我一开始使用 InOr
我正在尝试测试是否以预期顺序调用模拟对象的方法。下面是简化的例子: @Test public void test() { List mockedList = Mockito.mock(List
我创建了一个二叉搜索树,我可以添加和删除它,但是当我尝试使用 getInorderIterator 方法并打印树时,它会打印“TreePackage.BinaryTree$InorderIterato
我想测试模拟上的方法是否以正确的顺序、正确的参数以及与相应参数相关的正确的方法调用数量进行调用。 假设我想测试 List.add 被调用,如下所示: List listMock = Mockito.m
就在我坐下来为 morris 中序遍历编写代码之前,我尝试了这个例子,但对于它在这种特殊情况下的工作方式有点困惑: 80 / \ 60 100
我是一名优秀的程序员,十分优秀!