我目前的理解是可以用数组(一维)来表示左平衡二叉树。也就是说,我们可以从二叉 TreeMap 中节点的排列方式来填充数组的位置。
但是,这是正确的吗?相反,我们应该使用二叉 TreeMap 来表示数组中的元素吗?在本例中,我们使用数组中的元素创建二叉 TreeMap ,并使用公式 l = 2n + 1 和 r = 2n + 2(其中 >n = 父节点的数组索引,l = 左子节点的数组索引,r = 右子节点的数组索引)了解如何确定特定父节点的子节点的数组索引。
那么,用数组表示二叉 TreeMap ,还是用二叉 TreeMap 表示数组,哪个是正确的?还是两种方法都正确?
最佳答案
感谢 Riddhesh 和 ryanyuyu 的回答和建议。
经过进一步研究,我意识到左平衡二叉树(也称为“完全二叉树”)可以在编程代码中表示为一维数组。这种表示的目的是为了便于实现操作完全二叉树节点的代码。
相反,一维数组在概念上也可以表示为完全二叉树。这种表示的目的是为了便于实现使用二叉树理论对数组元素进行排序的代码。 “堆排序”就是一个例子,其中完整二叉树被转换为完全排序的最小堆或最大堆。
感谢您的帮助:)
有用的链接: https://www.cpp.edu/~ftang/courses/CS241/notes/heap.htm http://courses.cs.vt.edu/~cs3114/Fall09/wmcquain/Notes/T03a.BinaryTreeTheorems.pdf
P.S.:很抱歉使用“回答”选项来发布此内容。由于字符限制,我无法将此作为评论发布。
关于arrays - 我们应该使用数组来表示二叉树,还是反之亦然?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32200435/