在我的二叉树数据结构中：
//Every node has value and index
class Node<T> {
Node<T> left,right;
int index;
T value;
Node(T value, int index){
this.index = index;
this.value = value;
}
}
class Tree<T> {
int depth;
Node<T> root;
//Create an empty binary tree
private static Tree<Object> empty = new Tree<>();
@SuppressWarnings("unchecked")
public static <K> Tree<K> empty(){
return (Tree<K>) Tree.empty;
}
//creating a binary tree by taking depth as input
public static <K> Tree<K> depth(int deepest){
if(deepest > 0) {
Tree<K> tree = Tree.empty();
tree.root = new Node<>(null,0);
tree.addLevel(tree.root, 0, deepest, 0);
return tree;
}
else {
throw new Error();
}
}
private void addLevel(Node<T> node, int depth, int deepest,int index){
if (depth == deepest - 1) {
return;
} else {
node.left = new Node<>(node.value,index*2+1);
node.right = new Node<>(node.value,index*2+2);
addLevel(node.left,depth+1,deepest, index*2+1);
addLevel(node.right,depth+1,deepest,index*2+2);
}
}
public void getAllElem(Node<T> node, List<HashMap<T,Integer>> list) {
if (node == null) {
return;
}
else {
HashMap<T, Integer> pairs = new HashMap<T, Integer>();
getAllElem(node.left,list);
pairs.put(node.value, node.index);
list.add(pairs);
getAllElem(node.right,list);
}}在这种情况下，我想创建一个getparent（int index）方法，当用户将索引号传递给该方法时，它将返回父节点的值。例如，当输入的索引=3时，它将得到节点的值（索引=1）。但我不知道怎么做，有什么建议吗？谢谢！
1条答案
按热度按时间zbwhf8kr1#
一个简单的算法是从父节点检查叶索引，并在找到所需的叶索引后立即返回父值，即：
在最坏的情况下，该算法将具有时间复杂度
N，效率很低。然而，人们可以尝试改进它以O(log2N)，如果根据当前父索引只在右叶或左叶上搜索。因此，你需要找到一个表达式，让你知道哪个叶继续搜索。解决这个问题最有效的算法是
O(1). 因为对于给定的索引节点n，它们的叶子将在2n + 1以及2n + 2，这样您就可以制作一个小表并尝试找出公式（基于叶索引返回父索引）：基于该表，我们可以推断，在代码方面，可以使用以下公式获得父索引
(i-1)/2与i > 0，和i开始查找的叶的索引：所以代码应该是简单明了的：
但是，要使此算法正常工作，您需要有一个额外的结构来按索引存储节点，以便您可以在中访问它们的值
O(1). 例如，使用arraylist：将节点添加到树中时，也会将其添加到该列表中。然后用
getParentIndex方法可以访问列表中的索引，并检索节点值。这是在二进制堆上使用的典型方法。