Основы бинарного дерева в C ++

Question

У меня есть структура данных двоичного дерева:

//Declare Data Structure
struct CP {
    int id;         //ID of the Node
    int data;       //Data of the Node
    CP * left;      //Pointer to the Left Subtree 
    CP * right;     //Pointer to the Right Subtree
};

typedef CP * CPPtr; 

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

Answer 1

в вашем коде отсутствуют базовые шаги или необходимые инициализации.

 BTree_Helper(BTree *Tree){// this is roughly written like pseudo code
    if(TLeft == NULL && TRight == NULL){
      depth of tree = 0 ;       
    }
    else if (TLeft == NULL){
      depth of tree = depth of right tree ;       
    }
    else if(TRight==NULL){
      depth of tree = depth of left tree;        
    }
    else{
      depth of tree = the maximum between depth of left and depth of right;
    }
 }

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

Answer 2

Вы можете рассчитать глубину от любого узла, используя рекурсию:

int countChildren(CPPtr node) {

    if ( node != null )
        return 1 + countChildren(node->left) + countChildren(node->right);

    else 
        return 0;

}

Answer 3

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

Преимущества этого подхода:

1. В худшем случае производительность O (log n) (при условии, что дерево сбалансировано).
2. Очень просто писать нерекурсивно

Answer 4

Я собираюсь предположить, что id является ключом поиска для дерева.Другими словами, id любого узла в левом поддереве меньше, чем id этого узла, а id любого узла в правом поддереве больше, чем id этого узла.Кроме того, id считается уникальным.

Чтобы найти узел с заданным идентификатором по указателю на корневой узел дерева, вы просто делаете:

CP* find(CP* root, int searchID)
{
    // Starting point.
    CP* node = root;
    while(node)
    {
        // Search hit?
        if(node->id == searchID)
            return node;
        // Turn left or right?
        if(node->id < searchID)
            node = node->left;
        else
            node = node->right;
    }
    return 0; // No node with the given ID found.
}

Поиск глубины - это простая модификация этой функции: вместо того, чтобы возвращать узел, вы сохраняете счет того, сколько уровней вы опускаете.Глубина 0 означает, что вам нужен корневой узел;глубина 1 означает либо левый, либо правый узлы;Глубина 2 означает любого из их прямых потомков и т. д. Так что на самом деле, сколько раз вам нужно выполнить цикл:

int depth(CP* root, int searchID)
{
    // Starting point.
    CP* node = root;
    int depth = 0;
    while(node)
    {
        // Search hit?
        if(node->id == searchID)
            return depth;
        // Descending a level...
        ++depth;
        // Turn left or right?
        if(node->id < searchID)
            node = node->left;
        else
            node = node->right;
    }
    return -1; // No node with the given ID found.
}

Обратите внимание на специальное значение -1 для "not found".

Answer 5

Исходя из того, что предложил y26jin, может быть, что-то вроде этого?

BTree_Helper(CP *TreeNode) {
    CP *TLeft = TreeNode->left;
    CP *TRight = TreeNode->right;
    if(TLeft == NULL && TRight == NULL){
      return 0;       
    }
    else if (TLeft == NULL){
      return 1+(BTree_Helper(TRight));       
    }
    else if(TRight==NULL){
      return 1+(BTree_Helper(TLeft));        
    }
    else{
      return 1+max(BTree_Helper(TLeft),BTree_Helper(TRight));
    }
 }

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

Answer 6

Прочтите об основных алгоритмах поиска по дереву / графику: поиск в ширину (BFS) и поиск в глубину (DFS).Попробуйте реализовать DFS как рекурсивно, так и с явным stack<T>.Внедрите BFS, используя queue<T>.

Обратите внимание на эффективность вашего подхода.Если вы хотите многократно просматривать глубину узлов, вероятно, будет гораздо быстрее сохранить глубину каждого узла в дереве в некоторой таблице поиска.В идеале, в большинстве случаев подойдет хеш-таблица, но map<T1, T2>.

Вы многому научитесь из приведенных выше упражнений.Удачи!

Answer 7

Вы должны передавать указатели на lDepth и rDepth, а не сами значения, например:

nodeDepth_Helper(tree,id, &lDepth, &rDepth);

Более того, я думаю, что аргументы для nodeDepth_helper должны быть объявлены как указатели наInts:

void nodeDepth_Helper(CPPtr tree, int id, int* lDepth,int* rDepth)

внесение этих изменений повсеместно должно решить вашу проблему.