Назначение глубины каждому узлу

Question

Я прочитал еще несколько статей, которые выглядели похожими, но не совсем ответили на мою проблему. Мне задан вопрос о назначении назначить каждому узлу в двоичном дереве соответствующую глубину. Я просто не могу это получить.

Для справки это мой код:

struct treeNode { 
    int item; 
    int depth; 
    treeNode *left; 
    treeNode *right; 
}; 
typedef treeNode *Tree; 

int assignDepth(Tree &T, int depth) 
{ 
    if(T!=NULL) 
    { 
     depth = assignDepth(T->left, depth++); 
     T->depth = depth; 
     depth = assignDepth(T->right, depth++); 
    } 
    else //leaf 
     return depth--; 
} 

Я попытался запустить его через с ручкой и бумагой, и это выглядело хорошо, но мой стол проверки навыков явно не хватает.

Может ли кто-нибудь указать мне в правильном направлении, пожалуйста? Это мой первый раз, когда я использую деревья, а рекурсия - не моя сильная сторона.

Ответ:

void treecoords(Tree &T, int depth) 
{ 
    static int count = -1; //set to -1 so the precrement before assignment doesn't give the wrong values 
    if(T!=NULL) 
    { 
     treecoords(T->left, depth+1); //depth decrements automatically once this function call is removed from the stack 
     count++; 
     T->x = count; 
      T->y = depth; 
     treecoords(T->right, depth+1); 
    } 
} 

Answer 1

Вы надеваете»т нужно

else //leaf 
    return depth--; 

Вы также не хотите, чтобы увеличить переменную глубину, просто передать глубину + 1 к следующему Интерактивного.

Также нет необходимости возвращать значение.

Попробуйте это:

void assignDepth(Tree T, int depth) 
{ 
    if(T!=NULL) 
    { 
     assignDepth(T->left, depth+1); 
     T->depth = depth; 
     assignDepth(T->right, depth+1); 
    } 
} 

Answer 2

Ну, для начала, вы используете после увеличения/уменьшения, вы, вероятно, имел в виду ++depth/--depth для правильного присвоения и еще вернется;

Кроме того, зачем передавать указатель в качестве ссылочной переменной?

Answer 3

int assignDepth(Tree &T, int depth) 

Вы определили Tree как указатель на treeNode. Вам не нужно передавать его по ссылке. Вы можете изменить узел, на который все указали.

{ 
    if(T!=NULL) 
    { 
     depth = assignDepth(T->left, depth++); 

Постфиксная ++ гарантирует, что вы передаете оригинальный depth вниз. Это не то, что вы хотите. Приращение depth до этого, и забудьте о возврате его как результат функции.

T->depth = depth; 

Все в порядке.

 depth = assignDepth(T->right, depth++); 

Похожие, как и для предыдущего рекурсивного вызова, за исключением того, что здесь вы не должны изменять depth вообще, потому что он уже увеличивается.

} 
    else //leaf 
     return depth--; 

Вам не нужно возвращать информацию о глубине (или это неустановленное требование?).

} 

Приветствия & НТН.,

Answer 4

1. После того, как вы достигли листового узла, вы не заботитесь о его глубине любой более, так что возвращаемое значение, кажется, не достичь ничего.

2. В двух утверждениях:

   depth = assignDepth(T->left, depth++); 
   // and 
   depth = assignDepth(T->right, depth++); 
   

Вы неопределенное поведение от модификации depth дважды без промежуточной точки последовательности (хотя кажется, что там должно быть, есть не точка последовательности между правая и левая стороны задания).

Answer 5

1. Почему вы возвращаетесь, когда узел NULL. В соответствии с вашей спецификацией вам не нужно возвращать какую-либо глубину.

2. В другом случае вам просто нужно увеличить глубину и отправить вызов функции. Ниже моя версия кода

   недействительным assignDepth (Tree & T, глубина ИНТ) { если (T == NULL) возврата; прочее { T-> глубина = глубина; если (T-> left! = NULL) assignDepth (T-> left, depth + 1); if (T-> right! = NULL) assignDepth (T-> right, depth + 1); }}

Answer 6

У меня есть несколько более сложная конструкция с различными типами узлов и сделал это, так я думал, что доля ID.

Если у вас есть дерево, которое варьируется в типе Node to Node (Binary, Unary и т. Д.), Стоит упростить традиционный метод, чтобы избежать неприятных встроенных IFs для проверки типа Nodes.

две функция:

• 1: Из корня, проходит через каждый узел и проверить его расстояние до корня по recursivly называющего себя и добавления 1 для каждого родителя. Дайте каждому узлу переменную глубины, чтобы сохранить это.
• 2: Из полного набора узлов в дереве выполните проверку MAX против каждой глубины узлов, наибольшее число будет равно глубине дерева.

Обработка этого способа удаляет явную проверку типов и просто подсчитывает узел независимо от того, имеет ли он один, два или сотни детей.

Надеюсь, это поможет кому-то!