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

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 для правильного назначения, а возвращение else;

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

Answer 3

У меня есть немного более сложный дизайн с различными типами узлов, и я сделал это, поэтому я подумал, что id share.

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

Две функции:

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

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

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

Answer 4

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

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

   void assignDepth (Tree & T, int глубина) { если (T == NULL) вернуть; еще { T-> глубина = глубина; if (T-> left! = NULL) assignDepth (T-> left, глубина + 1); if (T-> right! = NULL) assignDepth (T-> right, глубина + 1); } }

Answer 5

1. Как только вы достигли конечного узла, вам больше не нужна его глубина, поэтому возвращаемое значение, похоже, ничего не дает.

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

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

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

Answer 6

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--;

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

}

Приветствия и hth.,