Массивы Vs Vector во время рекурсии

Question

У меня есть некоторое сомнение между массивом и вектором в следующем двоичном древовидном коде.

Ниже приведен код, чтобы найти Print все узлы, которые находятся на расстоянии к от узла листа

void TraceLeaves(node *temp,int k,vector<int> v,vector<int> visited) 
{ 

    if(temp->left==NULL&&temp->right==NULL) 
    { 
     v.push_back(temp->data); 

     if(visited[v.size()-k-1]==0) 
     { 
      visited[v.size()-k-1]=1; 
      cout<<v[v.size()-k-1]<<"\n"; 
     } 

     return; 
    } 
    else 
    { 
     v.push_back(temp->data); 
     visited.push_back(0); 
    } 

    TraceLeaves(temp->left,k,v,visited); 

    TraceLeaves(temp->right,k,v,visited); 

} 

int main() 
{ 
    root = createnode(1); 
    root->left=createnode(2); 
    root->right=createnode(3); 
    root->left->left = createnode(4); 
    root->left->right = createnode(5); 
    root->right->left = createnode(6); 
    root->right->right = createnode(7); 
    vector<int> v; 
    vector<int> visited; 
    TraceLeaves(root,1,v,visited); 
} 

Выход вышеуказанного метода является

2 
2 
3 
3 

Когда я заменить векторный визит массив с bool visited []

как

void TraceLeaves(node *temp,int k,vector<int> v,bool visited[]) 
{ 

    if(temp->left==NULL&&temp->right==NULL) 
    { 
     v.push_back(temp->data); 

     if(visited[v.size()-k-1]==0) 
     { 
      visited[v.size()-k-1]=1; 
      cout<<v[v.size()-k-1]<<"\n"; 
     } 

     return; 
    } 
    else 
    { 
     v.push_back(temp->data); 
     visited[v.size()-1]=0; 
    } 

    TraceLeaves(temp->left,k,v,visited); 

    TraceLeaves(temp->right,k,v,visited); 

} 

int main() 
{ 
    root = createnode(1); 
    root->left=createnode(2); 
    root->right=createnode(3); 
    root->left->left = createnode(4); 
    root->left->right = createnode(5); 
    root->right->left = createnode(6); 
    root->right->right = createnode(7); 
    vector<int> v; 
    bool visited[5]={false}; 
    TraceLeaves(root,1,v,visited); 
} 

Я получаю

2 
3 

, которая на самом деле правильно ..

Так я искал в Интернете .., который говорит мне, что

void TraceLeaves(node *temp,int k,vector<int> v,vector<int> visited) 

следует заменить на

void TraceLeaves(node *temp,int k,vector<int> v,vector<int> &visited) 

Полный после этого изменения

#include<bits/stdc++.h> 
using namespace std; 
struct node 
{ 
    int data; 
    struct node *left; 
    struct node *right; 
}*root; 

node* createnode(int d) 
{ 
    node *New; 
    New = new node; 
    New->data = d; 
    New->left=NULL; 
    New->right=NULL; 
} 

void TraceLeaves(node *temp,int k,vector<int> v,vector<int>& visited) 
{ 

    if(temp->left==NULL&&temp->right==NULL) 
    { 
     v.push_back(temp->data); 

     if(visited[v.size()-k-1]==0) 
     { 
      visited[v.size()-k-1]=1; 
      cout<<v[v.size()-k-1]<<"\n"; 
     } 

     return; 
    } 
    else 
    { 
     v.push_back(temp->data); 
     visited.push_back(0); 
    } 

    TraceLeaves(temp->left,k,v,visited); 

    TraceLeaves(temp->right,k,v,visited); 

} 

int main() 
{ 
    root = createnode(1); 
    root->left=createnode(2); 
    root->right=createnode(3); 
    root->left->left = createnode(4); 
    root->left->right = createnode(5); 
    root->right->left = createnode(6); 
    root->right->right = createnode(7); 
    vector<int> v; 
    vector<int> visited(5,0); 
    TraceLeaves(root,1,v,visited); 
} 

, но это дает мне выход

2 

, как мы используем массив по ссылке означает, что изменения будут обновлены

2, 3 находятся на одном уровне. Так что только 2 печатается.

Так что мой вопрос

почему я получаю 2,3, как вывод, когда BOOL посещенных [] используется в коде и передается по ссылке и получение только 2, когда вектор & v используется ??

Заранее спасибо.

Answer 1

Существует разница между

bool visited[5]={false}; 

и

vector<int> visited; 

кроме очевидного массива C-стиле против std::vector. В первом случае массив имеет ровно 5 элементов, все инициализируются false. Во втором случае вектор пуст, и вы ничего не вставляете в него (по крайней мере, не в коде, который вы указали). Поэтому в этом случае, когда вы получаете доступ к visited[v.size()-k-1] в этой функции, вы пытаетесь читать и изменять элементы, которые не существуют, что является неопределенным поведением.

Чтобы получить такое же поведение при использовании std::vector, вы должны инициализировать его теми же элементами перед его использованием.

Answer 2

Обратите внимание:

Вы неопределенное поведение в вашей createNode функции. Вы не возвращаете значение, но функция должна вернуть node*. Вам необходимо решить эту проблему, прежде чем продолжить.

---

Во-первых, вы должны понимать, что оба примера вы вывешенные в корне отличаются, не только отличается тем, что вы использовали вектор в первом примере, а затем массив во втором примере.

Во-первых, массив не может быть изменен. Таким образом, ваш первый пример делает это, когда visited является вектор:

visited.push_back(0); // resizes 

Это большая разница между этой линией и это (в вашем примере массива):

visited[v.size()-1]=0; // does not resize 

Таким образом, мы могли бы остановились прямо здесь с различиями в двух примерах. Однако здесь есть другая разница:

void TraceLeaves(node *temp,int k,vector<int> v,vector<int> visited) 

Здесь visited вектор передается по значению. Это означает, что любые изменения в TraceLeaves, которые происходят с вектором visited, являются локальными и не отражаются обратно вызывающему абоненту.

Сравните это это в вашем примере массива:

void TraceLeaves(node *temp,int k,vector<int> v,bool visited[]) 

Параметр visited является bool *. Синтаксис [] не изменяет этот факт. Таким образом, выше декларация является такой же, как это:

void TraceLeaves(node *temp,int k,vector<int> v,bool* visited) 

Это много отличается от vector версии выше. То, что вы здесь делаете, это передать указатель на visited, таким образом, изменения вы сделаете на visited «массив» будет отразить обратно вызывающему.

Если вы действительно хотите, чтобы оба примера были одинаковыми, вы должны написать им, чтобы они были одинаковыми, а не разными. Во-первых, вы меняете вектор на тот же размер, что и пример массива. В main:

std::vector<bool> visited(5,false); 

Тогда функция TraceLeaves будет выглядеть точно такой же, как в примере массива, с той разницей, прототип функции, чтобы имитировать пример указателя:

void TraceLeaves(node *temp,int k,vector<int> v,vector<int>& visited) 

Live Example with changes described above