c++ - 如何使用后序遍历打印排序数组？

Question

我正在尝试使用后序遍历打印给定排序数组的所有索引的值。我不明白问题是什么!请帮助我。如您所知，排序数组是一个最小堆，这里将通过后序遍历打印出来。

#include <iostream>
#include <cstdlib>
#include <fstream>
#include <cmath>
using namespace std;
int a, b, temp;
char c;
int B[10] = { NULL };

int L(int i) //returning the index of left child
{
    i = ((2 * i) + 1);
    return i;
}

int R(int i) //returning the index of right child
{
    i = ((2 * i) + 2);
    return i;
}

int P(int i) //returning the index of parent
{
    if (i % 2 == 0) { i = ((i - 2) / 2); }
    else { i = ((i - 1) / 2); }
    return i;
}

//printing function
void f(int A[], int i) //printing using post order format 
{
    while (A[L(i)] != NULL && B[L(i)] != 1) 
    {
        i = L(i); 
    }

    cout << A[i] << " A "; 
    B[i] = 1; // B[i] is a kind of flag that checks whether A[i] has already been printed or not 

    if (i == 2) //I noticed that when it approaches the index 2, it only needs to print A[0] and gets out of the function
    {
        cout << A[0] << endl<< endl; 
        return;
    } 

    if (A[L(i+1)] == NULL) 
    {
        cout << A[i + 1] << " "; B[i + 1] = 1; 
    } //checks if the right node hasn't a child, prints it
    else 
    {
        f(A, i + 1); 
    }

        cout << A[P(i)] << " "; B[P(i)] = 1;
// When looking at the parent, if its index is odd, it means that you have already printed a left child so you should go the right index
        if (P(i) % 2 == 1)
        {

            f(A, P(i) + 1);
        }
// When looking at the parent, if its index is even, it means that you have already printed a right child so you should go up to its parent : (P(P(i))
        else 
        {
            f(A, P(P(i))); 
        } 


} 
int main()
{
int A[10]={0,1,2,3,4,5,6,7,8,9};
f(A,0);
return 0;
}

Answer 1

首先，我认为 int B[10] = { NULL }; 不是您想要的任何好方法。如果只想进行后序遍历，更简单的实现方式是:

void postTraversal(int a[], int n)
{
    if (n <=9  && n >= 0)
    {
        postTraversal(a, L(n));
        postTraversal(a, R(n));
        cout << a[n] << " ";
    }

}
int main()
{
int A[10]={0,1,2,3,4,5,6,7,8,9};
//f(A,0);
postTraversal(A, 0);
cout << endl;
return 0;
}