Рекурсивный обход ширины двоичного дерева

Question

Я пытаюсь найти способ реализации двоичного обхода дерева с использованием рекурсии на языке C или C++.

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

Таким образом, проблема такова: Для каждого уровня печати индекса уровня (на основе 0) и информации об узле.

Пример: Уровень 0: A Уровень 1: BC

Благодаря

Answer 1

Вот пример кода

/* Function to print level order traversal a tree*/ 
void printLevelOrder(struct node* root) 
{ 
    int h = height(root); 
    int i; 
    for(i=1; i<=h; i++) 
    printGivenLevel(root, i); 
}  

/* Print nodes at a given level */ 
void printGivenLevel(struct node* root, int level) 
{ 
    if(root == NULL) 
    return; 
    if(level == 1) 
    printf("%d ", root->data); 
    else if (level > 1) 
    { 
    printGivenLevel(root->left, level-1); 
    printGivenLevel(root->right, level-1); 
    } 
} 

Решение доступно здесь http://www.geeksforgeeks.org/level-order-tree-traversal/

Answer 2

Вот Внедрение JavaScript, которое подделывает вывод Breadth First Trav ersal, о котором вы просите, но с глубиной Первая рекурсия. Я храню значения узлов на каждой глубине внутри массива внутри хеша. Если уровень уже существует (у нас есть столкновение), мы просто нажимаем на массив на этом уровне. Вы можете использовать массив вместо объекта JavaScript, так как наши уровни являются числовыми и могут служить индексами массива. Вы можете возвращать узлы, значения, конвертировать в связанный список или что угодно. Я просто возвращаю ценности ради простоты.

BinarySearchTree.prototype.breadthFirstRec = function() { 

    var levels = {}; 

    var traverse = function(current, depth) { 
     if (!current) return null; 
     if (!levels[depth]) levels[depth] = [current.value]; 
     else levels[depth].push(current.value); 
     traverse(current.left, depth + 1); 
     traverse(current.right, depth + 1); 
    }; 

    traverse(this.root, 0); 
    return levels; 
}; 


var bst = new BinarySearchTree(); 
bst.add(20, 22, 8, 4, 12, 10, 14, 24); 
console.log('Recursive Breadth First: ', bst.breadthFirstRec()); 
/*Recursive Breadth First: 
{ '0': [ 20 ], 
    '1': [ 8, 22 ], 
    '2': [ 4, 12, 24 ], 
    '3': [ 10, 14 ] } */ 

Вот пример фактического широтой первой Traversal использованием итеративного подхода, в JavaScript, в случае, если кто-то заинтересован. Правила JavaScript!

BinarySearchTree.prototype.breadthFirst = function() { 

    var result = '', 
     queue = [], 
     current = this.root; 

    if (!current) return null; 
    queue.push(current); 

    while (current = queue.shift()) { 
     result += current.value + ' '; 
     current.left && queue.push(current.left); 
     current.right && queue.push(current.right); 
    } 
    return result; 
}; 

console.log('Breadth First: ', bst.breadthFirst()); 
//Breadth First: 20 8 22 4 12 24 10 14