преобразовать двоичное дерево в двоичное дерево поиска на месте, используя C - PullRequest
Новая
       66

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

0 голосов
/ 29 марта 2011

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

BTtoBST (узел * root)

1.Если корень равен NULL, возвращается

2. Еще ток = корень

3.if (текущий-> левый> текущий) своп (текущий-> левый, текущий)

4.if (текущий-> правый <текущий) своп (текущий-> правый, текущий)

5.current = current-> левый

6 перейти к 3, если текущий! = NULL, иначе перейти к 4

7.current = current-> правый

Заранее спасибо

PS: я видел эту ссылку, но не очень помог !! Преобразовать двоичное дерево -> BST (сохранение первоначальной формы дерева)

Ответы [ 2 ]

1 голос
/ 29 марта 2011

Вы можете поменять узлы, включая поддеревья (не только содержимое узла), как в дереве AVL http://en.wikipedia.org/wiki/AVL_tree

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

0 голосов
/ 28 марта 2012

Выполните обход дерева по порядку (снизу вверх), взяв посещенные узлы и вставив их в BST.

Исключает ли "без лишних пробелов" рекурсию?

Если нет, то что-то вроде: 

# top level call passes null for bst
bt_to_bst (root, bst)
  # nothing to add to bst; just return it
  if null(root) -> return bst
  # if this is a leaf node, stick it into the BST
  if null(root->left) && null(root->right)
    return bst_insert(bst, root)
  # otherwise add all of left subtree into the bst and then the right tree
  bst = bt_to_bst (root->left, bst);
  return bt_to_bst (root->right, bst);

bt_to_bst - операция фильтрации; он берет существующий bst и возвращает новый с добавленным в него узлом.

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

...