根據陣列下標完成對二叉樹的中序遍歷
即順序存盤的物理結構
題目圖解如下
根據陣列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;
}
運行結果如下
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/272584.html
標籤：其他
上一篇：密室逃脫
下一篇：第41節 C程式結構/陳述句小節