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

Question

Учитывая бинарное дерево (только с левым и правым потомком), как написать рекурсивную функцию, чтобы превратить ее в простой связанный список на месте? (Новая структура данных не должна создаваться. Псевдокод в порядке). Предположим, что каждый узел имеет целочисленное значение, например 123, или 2, или 3. Окончательный список ссылок должен содержать все узлы в дереве. Порядок не важен.

Обновление: должно быть на месте. новая структура данных не должна создаваться.

Answer 1

Всегда есть разные способы итерации по дереву, такие как:

• заказовМои
• PREORDER
• PostOrder

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

Например (псевдокод, PreOrder):

function treeToList(LinkedList l, Tree t)
    if(t not nil)
        l.add(t.element)
        treeToList(l, t.Left)
        treeToList(l, t.Right)
    endif
end function

Remenber: если вы выполнили InOrder в бинарном дереве поиска, вы получите элементы в отсортированном порядке.

Answer 2

Чтобы получить список из двух избранных, отсортированный так же, как исходное дерево, код C #:

function Listify(Node n, out Node First, out Node Last)
{
    if ( Node.Left != null )
    {
        Node Tmp;
        Listify(Node.Left, out First, out Tmp);
        Node.Left = Tmp;
    }
    else
    {
        First = Node;
    }
    if ( Node.Right != null )
    {
        Node Tmp;
        Listify(Node.Right, out Tmp, out Last);
        Node.Right = Tmp;
    }
    else
    {
        Last = Node;
    }
}

Answer 3

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

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

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

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

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

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

Итак, чтобы обработать корневой узел, мы делаем это:

• Если корень содержит значение: добавьте значение в список

Это заботится об одном значении, которое может храниться в корневом узле. Некоторые двоичные деревья хранят значения только в конечных узлах (узлах без дочерних элементов), большинство хранит значения также во внутренних узлах (узлах с дочерними элементами).

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

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

И мы также знаем, что если у корневого узла есть дочерние элементы в правильном «направлении», эти значения последуют за ним.

Итак, что мы можем сделать, это:

• Обработка всех узлов в левом поддереве
• Добавить значение в узел
• Обработка всех узлов в правом поддереве

Этот подход предполагает, что:

• Упорядочены значения узлов (т. Е. Левое поддерево предшествует значению самого узла и т. Д.)
• Вы хотите значения в их упорядоченной последовательности

Если вы определите вышеуказанный подход как метод, у вас будет что-то вроде этого:

to process a node, do this:
    first process the left-child sub-node, if present
    then append the value of the node, if any
    then process the right-child sub-node, if present

В приведенном выше псевдокоде, где вы видите слово «процесс», вы применяете тот же процесс к этим узлам, как описано выше.

Вот код C # для обработки простого двоичного дерева и добавления результата к заданному связанному списку:

public void AppendTreeToLinkedList<T>(Node<T> node, LinkedList<T> list)
{
    if (node.LeftChild != null)
        AppendTreeToLinkedList(node.LeftChild, list);
    list.Append(node.Value);
    if (node.RightChild != null)
        AppendTreeToLinkedList(node.RightChild, list);
}

Answer 4

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

• Вы создаете пустой связанный список для результата.

• Создайте функцию справки, которая принимает связанный список и узел.

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

• Добавление корневого узла в список результатов.

• Вызовите вспомогательную функцию в корневом узле и список результатов.

• Возвращает список результатов вызывающей стороне.

В Википедии, конечно, об этом много: двоичные деревья и обход дерева .

Редактировать: или посмотреть псевдокод, опубликованный Кевином: -)

Answer 5

В Схеме с использованием запомненной рекурсии алгоритм упорядочения будет иметь вид:

(define (tree->list tree)
  (define empty-set (list))
  (define (copy-to-list tree result-list)
    (if (null? tree)
      result-list
      (copy-to-list (left-branch tree)
                    (cons (entry tree)
                          (copy-to-list (right-branch tree)
                                        result-list)))))
   (copy-to-list tree empty-set))

Предполагается, что древовидная структура представлена ​​в виде:

(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
  (list entry left right))

N.B. Я мог бы использовать литерал '() для empty-set, но ТАК испортил цветовое кодирование кода в кавычках.

Answer 6

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

listify( node )
    if node has no children 
        return

    else if node.left == null
        listify(node.right)

    else if node.right == null
        listify(node.left)
        mode.right = node.left

    else
        listify(node.left)
        listify(node.right)

        temp = node.left
        while temp.right != null
            temp = temp.right

        temp.right = node.right

        node.right = node.left

Answer 7

/* bst.c: sort the input numbers and print them forward and backward with no duplicates */

#include <stdio.h>
#include <stdlib.h>

struct node {
    int key;
    struct node *left;
    struct node *right;
};

static struct node **bst_find(struct node **root, int key) {
    struct node **n;

    n = root;
    while (*n != NULL && (*n)->key != key) {
        if (key < (*n)->key) {
            n = &(*n)->left;
        } else {
            n = &(*n)->right;
        }
    }
    return n;
}

static void bst_insert(struct node **root, int key) {
    struct node **n;

    n = bst_find(root, key);
    if (*n == NULL) {
        *n = malloc(sizeof (**n));
        (*n)->key = key;
        (*n)->left = NULL;
        (*n)->right = NULL;
    }
}

/* massage the tree rooted at "root" to be a doubly-linked list
 * return the leftmost and rightmost nodes via the parameters "leftend" and "rightend"
 * bst_flatten() is invoked 2N+1 times, where N is the number of tree elements
 */
static long Flatten_count = 0;
static void bst_flatten(struct node **leftend, struct node **rightend, struct node *root) {
    Flatten_count++;
    if (root != NULL) {
        /* flatten the left side of the tree */
        *leftend = root;
        bst_flatten(leftend, &root->left, root->left);
        /* if necessary, splice "root" onto the right end */
        if (root->left != NULL) {
            root->left->right = root;
        }
        /* flatten the right side of the tree */
        *rightend = root;
        bst_flatten(&root->right, rightend, root->right);
        /* if necessary, splice "root" onto the left end */
        if (root->right != NULL) {
            root->right->left = root;
        }
    }
}

int main(void) {
    int key;
    long N = 0;
    struct node *root = NULL;
    struct node *leftend = NULL;
    struct node *rightend = NULL;
    struct node *n;

    /* read the input into a bst */
    while (scanf("%d", &key) == 1) {
        N++;
        bst_insert(&root, key);
    }
    /* make a list */
    bst_flatten(&leftend, &rightend, root);
    /* traverse the list forward */
    for (n = leftend; n != NULL; n = n->right) {
        printf("%d\n", n->key);
    }
    /* traverse the list backward */
    for (n = rightend; n != NULL; n = n->left) {
        printf("%d\n", n->key);
    }
    fprintf(stderr, "%ld items input, %ld invocations of bst_flatten()\n", N, Flatten_count);
    return 0;
}

Answer 8

Вы можете «ходить по дереву» во многих порядках, основными из которых являются пред-, пост- и по порядку. Вот некоторый псевдокод для заказа, например:

def in_walk(tree, doit):
  if tree is null: return
  in_walk(tree.left, doit)
  doit(tree.root)
  in_walk(tree.right, doit)

Я надеюсь, что предположения в этом псевдокоде очевидны: дерево имеет левые и правые ссылки, которые могут быть нулевыми, означая «больше здесь не ходить», и корневой узел; Вы можете передать функцию или замыкание, которое правильно мыслит (добавить в связанный список или что-то еще) с учетом аргумента узла.

Answer 9

Вы действительно спрашиваете, как мне пройти бинарное дерево. Ответ можно найти в любой книге об алгоритмах и структурах данных.