我目前的理解是可以使用数组(一维)来表示左 balancer 二叉树 . 换句话说,从节点排列在二叉树图中的方式来看,我们可以填充数组的位置 .
但是,这是正确的吗?相反,我们应该使用二叉树图来表示数组中的元素吗?在这种情况下,我们使用数组中的元素创建二叉树图,并使用公式l = 2n 1和r = 2n 2(其中n =父节点的数组索引,l =左子节点的数组索引和r =右子节点的数组索引)知道如何确定特定父节点的子节点的数组索引 .
哪个是正确的 - 使用数组表示二叉树图,或使用二叉树图表示数组?或两种方式都正确吗?
2 回答
感谢Riddhesh和ryanyuyu,感谢您的回答和建议 .
经过进一步研究,我意识到左 balancer 二叉树(也称为"Complete Binary Tree") can 在编程代码中表示为一维数组 . 此表示的目的是为了便于实现操作完整二叉树的节点的代码 .
相反,一维数组也可以在概念上表示为完整二叉树 . 这种表示的目的是为了易于实现使用二叉树理论对数组元素进行排序的代码 . 一个例子是“堆排序”,其中完整二叉树被转换为完全排序的最小或最大堆 .
感谢你的帮助 :)
有用的链接:https://www.cpp.edu/~ftang/courses/CS241/notes/heap.htm http://courses.cs.vt.edu/~cs3114/Fall09/wmcquain/Notes/T03a.BinaryTreeTheorems.pdf
P.S . :抱歉使用“答案”选项发布此内容 . 由于角色限制,我无法将此作为评论发布 .
使用您的公式从Array创建二叉树并不能帮助我轻松想象二进制树的外观,而从二进制树图中节点的排列方式来看,如果我们填充数组的位置,则很容易可视化 .
我们使用数组或链表或任何其他数据结构来将现实问题映射到编程中 . 我们不反过来 .