257-根据数组下标完成对二叉树的中序遍历

根据数组下标完成对二叉树的中序遍历

即顺序存储的物理结构

题目图解如下

根据数组ar完成对二叉树的先序遍历。

解题思路如下

我们是从上到下，从左到右，依次进行编号，即数组的下标。-1代表结点不存在。

我们知道，数组（物理结构）和二叉树的图（逻辑结构）有个对应的数学关系。
假设结点的下标为i，它的左孩子就是2i+1，它的右孩子的下标就是2i+2;

代码如下

void InOrder(const int* ar, int i, int n)
{
	if (i < n && ar[i] != -1)
	{
		InOrder(ar, i * 2 + 1, n);//left
		cout << ar[i] << " ";
		InOrder(ar, i * 2 + 2, n);//right
	}
}
int main()
{
	int ar[] = { 7,8,23,9,15,-1,18,-1,-1,10,20 };
	int n = sizeof(ar) / sizeof(ar[0]);

	InOrder(ar, 0, n);
	cout << endl;

	return 0;
}

运行结果如下