这属于https://stackoverflow.com/help/on-topic
这是一个面试问题http://www.glassdoor.com/Interview/Yelp-Software-Engineering-Intern-Interview-Questions-EI_IE43314.0，4_KO5,32_IP2.htm，
特别是"通过数组或链表实现的二进制树的性能"
如何通过数组或链表实现二叉树？
我被教导做这件事的方式是通过有一个链接节点类型的结构，它有两个指针，左和右，也就是（来自https://courses.cs.washington.edu/courses/cse143/12wi/lectures/02-22/programs/IntTreeNode.java)
public class IntTreeNode {
public int data;
public IntTreeNode left;
public IntTreeNode right;
public IntTreeNode(int data) {
this(data, null, null);
}
public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}
然后在实际的二叉树中
public class IntTree {
IntTreeNode overallRoot;
public IntTree() {
overallRoot = null;
}
....
}
如果你只是使用一个数组或链表（一个指针），你会怎么做？
但不管怎样，这应该是一个火速的问题。即使你没有实现树，你也不应该实现，你会如何分析树的性能？性能是否取决于树的状态，就像它是BST一样？就像BST一样，find应该是O（logn），因为你每次都要砍掉一半的树。
您将如何立即基于这两个实现来分析性能？
我不确定我是否理解正确，但这就是我的想法。基本上，您可以将树中的节点存储为数组/列表的元素。
对于数组，可以这样想：
public class Node {
public int data;
public int left;
public int right;
...
}
您的树将是Node（Node[] tree）的数组，因此根将是第一个元素tree[0]。每个元素都将其左右两个子元素作为数组中的索引。例如，tree[ tree[0].left ]将是根的左侧子项。-1的left值可以指示该节点不具有左子节点；类似于CCD_ 7。
例如，考虑以下树：
5
/
2 8
/
3 6 9
假设您最初在数组中分配了10个元素。由于树中的节点少于10个，因此其中一些节点将是null。以下是它可能的样子：（我将每个Node表示为(data,left,right)元组）
{ (5,1,2) , (2,-1,4) , (8,5,3) , (9,-1,-1) , (3,-1,-1) , (6,-1,-1) , null , null , null , null }
因此，对于节点(8,5,3)，您可以判断出它的左子级是第六个元素（节点(6,-1,-1)），而它的右子级则是第四个元素（结点(9,-1,-1)）。
插入/删除功能的性能可能因您的精确实现而异。类似的想法也适用于链表（但请记住，它们没有随机访问权：找到第i个元素需要逐个元素遍历列表）。
希望这能有所帮助。
在分析算法时，您需要查看它是什么类型的二叉树（平衡与不平衡），以及与sapce/时间复杂性有关的三个因素：
- 插入
- 删除
- 搜索
比较链表与二进制树的数组实现，我们可以看到以下内容：
- 链表的插入和删除比在数组中执行要便宜得多（想想为了完成这两个操作而必须执行的数组元素移位
- 链表提供灵活的大小，而数组则没有；当数据不适合初始数组大小时，您将不得不处理数组扩展
- 数组提供随机访问，而链表则不提供；例如，当处理完整或完全二叉树的数组实现时，我们可以很容易地计算树中任何节点的索引
话虽如此，对于二进制搜索树的特定实现，链表是更好的实现，因为在二进制搜索树中，访问遵循二进制搜索树规则（根的值大于左子项，小于右子项）。因此，对于插入/删除和搜索，如果树是平衡的，则平均复杂度应该是O(log n)。如果二进制搜索树不平衡，那么所有操作的复杂性都将变为O(n)——这是最坏的情况。