преобразование бинарного дерева поиска в двусвязный список

Это рекурсивный подход. Обратите внимание, что здесь root будет указывать на некоторый промежуточный элемент сформированного списка. Итак, просто пройдите от корня назад, чтобы получить голову.

#define NODEPTR struct node*

NODEPTR convert_to_ll(NODEPTR root){
    if(root->left == NULL && root->right == NULL)
        return root;
    NODEPTR temp = NULL;
    if(root->left != NULL){
        temp = convert_to_ll(root->left);
        while(temp->right != NULL)
            temp = temp->right;
        temp->right = root;
        root->left = temp;
    }
    if(root->right != NULL){
        temp = convert_to_ll(root->right);
        while(temp->left != NULL)
            temp = temp->left;
        temp->left = root;
        root->right = temp;
    }
    return root;
    }

Самый простой способ. Этого можно добиться за один неупорядоченный обход и с пространственной сложностью всего O(1). Сохраните указатель с именем lastPointer и отслеживайте его после посещения каждого узла. использовать левый и правый

public void toll(T n) {
    if (n != null) {
        toll(n.left);
        if(lastPointer==null){
            lastPointer=n;
        }else{
            lastPointer.right=n;
            n.left=lastPointer;
            lastPointer=n;
        }
        toll(n.right);
    }
}

Код С++:

 Node<T> *BTtoDoublyLLZigZagOrder(Node<T> *root)
 {
        if (root == 0)
            return 0;
        if (root->mLeft == 0 && root->mRight == 0)
            return root;

        queue<Node<T> *> q;
        q.push(root);
        Node<T> *head = root;
        Node<T> *prev = 0,*curr = 0;

        while(!q.empty())
        {
            curr = q.front();
            q.pop();
            if (curr->mLeft)
                q.push(curr->mLeft);
            if (curr->mRight)
                q.push(curr->mRight);
            curr->mRight = q.front();
            curr->mLeft = prev;
            prev = curr;
        }

        return head;
 }

Решение, упомянутое в ссылке на библиотеку Стэнфорда, является идеальным решением для BST в циклическую DLL, нижеприведенное решение - это не совсем преобразование BST в циклическую DLL, но циклическая DLL может быть достигнута путем соединения концов DLL. Это не совсем зигзагообразное преобразование дерева в dll.

ПРИМЕЧАНИЕ. это решение не является идеальным преобразованием BST в циклическую DLL, но это легко понятный хак.

JAVA-код

public Node bstToDll(Node root ){
        if(root!=null){
            Node lefthead = bstToDll(root.left); // traverse down to left 
            Node righthead = bstToDll(root.right); // traverse down to right
            Node temp = null;
            /*
             * lefthead represents head of link list created in left of node
             * righthead represents head of link list created in right
             * travel to end of left link list and add the current node in end
             */
            if(lefthead != null) {
                temp = lefthead;
                while(temp.next != null){
                    temp = temp.next;
                }
                temp.next = root;
            }else{
                lefthead = root;
            }
            root.prev = temp;
            /*
             *set the next node of current root to right head of right list
             */
            if(righthead != null){
                root.next = righthead;
                righthead.prev = root;
            }else{
                righthead = root;
            }
            return lefthead;// return left head as the head of the list added with current node
        }
        return null;
}

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

Обход в обратном порядке без глобальных переменных — c# выполнение. При вызове null сначала будет передан параметру right. Окончательное возвращаемое значение — это head двусвязного списка.

public static Node ToDLL(Node node, Node right)
{
    if (node == null)
        return null;

    var rnd = ToDLL(node.Right, right);

    if (rnd != null)
    {
        node.Right = rnd;
        rnd.Left = node;
    }
    else
    {
        node.Right = right;
        if (right!= null)
            right.Left= node;
    }
    return ToDLL(node.Left, node) ?? node;
}

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

public static Node binarySearchTreeToDoublyLinkedList(Node root) {

    // sentinel nodes
    Node head = new Node();
    Node tail = new Node();

    // in-order traversal
    binarySearchTreeToDoublyLinkedList(root, head, tail);

    // re-move the sentinels and re-link;
    head = head.right;
    tail = tail.left;

    if (head != null && tail != null) {
        tail.right = head;
        head.left = tail;
    }

    return head;
}

/** In-order traversal **/
private static void binarySearchTreeToDoublyLinkedList(Node currNode, Node head, Node tail) {
    if (currNode == null) {
        return;
    }


    // go left
    //

    binarySearchTreeToDoublyLinkedList(currNode.left, head, tail);

    // save right node for right traversal as we will be changing current
    // node's right to point to tail
    //

    Node right = currNode.right;

    // first time
    //

    if (head.right == null) {

        // fix head
        //

        head.right = currNode;
        currNode.left = head;

        // fix tail
        //

        tail.left = currNode;
        currNode.right = tail;

    } else {

        // re-fix tail
        //

        Node prev = tail.left;

        // fix current and tail
        //

        tail.left = currNode;
        currNode.right = tail;

        // fix current and previous
        //

        prev.right = currNode;
        currNode.left = prev;
    }

    // go right
    //

    binarySearchTreeToDoublyLinkedList(right, head, tail);
}

struct node{
int value;
struct node *left;
struct node *right;
};
typedef struct node Node;

Node * create_node(int value){
  Node * temp =  (Node *)malloc(sizeof(Node));
  temp->value = value;
  temp->right= NULL;
  temp->left = NULL;
  return temp;
}
Node * addNode(Node *node, int value){
  if(node == NULL){
    return create_node(value);
  }
  else{
    if (node->value > value){
        node->left = addNode(node->left, value);
    }
    else{
        node->right = addNode(node->right, value);
    }
  }
  return node;
}

void treeToList(Node *node){

    Queue *queue = NULL;
    Node * last = NULL;
    if(node == NULL)
            return ;

    enqueue(&queue, node);
    while(!isEmpty(queue)){
       /* Take the first element and put 
          both left and right child on queue */
            node = front(queue);
            if(node->left)
                    enqueue(&queue, node->left);
            if(node->right)
                    enqueue(&queue, node->right);
            if(last != NULL)
                    last->right = node;
            node->left = last;
            last = node;
            dequeue(&queue);
      }
  } 
  /* Driver program for the function written above */
 int main(){
    Node *root = NULL;
   //Creating a binary tree
    root = addNode(root,30);
    root = addNode(root,20);
    root = addNode(root,15);
    root = addNode(root,25);
    root = addNode(root,40);
    root = addNode(root,37);
    root = addNode(root,45);

    treeToList(root);

    return 0;
}

Реализацию API очередей можно найти по адресу http://www.algorithmsandme.com/2013/10/binary-search-tree-to-double-linked.html

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

void BST2DLL(node *root, node **prev, node **head)
{
    // Base case
    if (root == NULL) return;

    // Recursively convert left subtree
    BST2DLL(root->left, prev, head);

    if (*prev == NULL) // first iteration
        *head = root;
    else
    {
        root->left = *prev;
        (*prev)->right = root;
    }
    *prev = root; // save the prev pointer 

    // Finally convert right subtree
    BST2DLL(root->right, prev, head);
}

Надеюсь, это поможет вам.

class Solution(){
public:
    TreeNode* convertBST2DLL(TreeNode* root){
        TreeNode left, right;
        convert(root, &left, &right);
        TreeNode* head = left.right;
        head->left = NULL;
        right.left->right = NULL;
        return head;
    }   
    void convert(TreeNode* root, TreeNode* left, TreeNode* right){
        if(root->left == NULL){
            left->right = root;
            root->left = left;
        }
        else{
            convert(root->left, left, root);
        }
        if(root->right == NULL){
            right->left = root;
            root->right = right;
        }
        else{
            convert(root->right, root, right);
        }
    }
};

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

def convert(n, head=None):
  if n.right:
    head = convert(n.right, head)
  if head:
    head.left = n
  n.right = head
  if n.left:
    head = convert(n.left, n)
  else:
    head = n
  return head

Надеюсь, это кому-то пригодится.

Вот код Java. Сложность O(N). Я также добавляю несколько тестовых случаев для этой проблемы.

public class BinaryToDoubleLinkedList {

    static class Node {
        int value;
        Node left;
        Node right;

        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    static class Pair {
        Node head;
        Node tail;

        public Pair(Node head, Node tail) {
            this.head = head;
            this.tail = tail;
        }
    }

    static Pair convertToDoubleLinkedList(Node root) {
        return convert(root);
    }

    static Pair convert(Node root) {
        if (root == null) return new Pair(null, null);

        Node head, last;

        Pair left = convert(root.left);
        if (left.tail != null) {
            left.tail.right = root;
            root.left = left.tail;
            head = left.head;
        } else {
            head = root;
        }

        Pair right = convert(root.right);
        if (right.head != null) {
            right.head.left = root;
            root.right = right.head;
            last = right.tail;
        } else {
            last = root;
        }

        return new Pair(head, last);
    }

    static void Print(Node root, boolean fromLeft) {
        System.out.println("---------");
        if (fromLeft) {
            while (root != null) {
                System.out.print(root.value + ",");
                root = root.right;
            }
        } else {
            while (root != null) {
                System.out.print(root.value + ",");
                root = root.left;
            }
        }

        System.out.println();
    }

    public static void main(String[] args) {
        test1();
        test2();
        test3();
    }

    // test 1: normal test case
    public static void test1() {
        Node root = new Node(10, null, null);
        root.left = new Node(12, null, null);
        root.right = new Node(15, null, null);

        root.left.left = new Node(25, null, null);
        root.left.right = new Node(30, null, null);
        root.right.left = new Node(36, null, null);

        Pair res = convertToDoubleLinkedList(root);
        Print(res.head, true);
        Print(res.tail, false);
    }

    // test 2: binary tree as linked list
    public static void test2() {
        Node root = new Node(1, null, null);
        root.left = new Node(2, null, null);
        root.left.left = new Node(3, null, null);
        root.left.left.left = new Node(4, null, null);

        Pair res = convertToDoubleLinkedList(root);
        Print(res.head, true);
        Print(res.tail, false);
    }

    // test 3: null and single
    public static void test3() {
        Node root = new Node(1, null, null);
        Pair res = convertToDoubleLinkedList(root);
        Print(res.head, true);
        Print(res.tail, false);

        res = convertToDoubleLinkedList(null);
        Print(res.head, true);
        Print(res.tail, false);
    }
}

Поиск предшественника по порядку и указание слева и справа на предшественника текущего корня сделает эту работу за вас. Временная сложность для запуска приведенного ниже кода равна O(N) и займет вспомогательное пространство O(H), где H = Height of the Tree неявно используется для стека рекурсии. Код ниже написан с использованием Python 3.

def convertToDLL(root):
    # Base check
    if root is None:
        return root

    # Converting left sub-tree to root
    if root.left:

        # Convert the left subtree
        left = convertToDLL(root.left)

        while left.right:
            left = left.right

        left.right = root
        root.left = left

    # Converting right sub-tree to root
    if root.right:

        # Convert the right subtree
        right = convertToDLL(root.right)

        while right.left:
            right = right.left

        right.left = root
        root.right = right

    return root


def bToDLL(root):
    if root is None:
        return root

    # Convert to DLL
    root = convertToDLL(root)

    while root.left:
        root = root.left

    return root


def display(head):
    # Display
    if head is None:
        return
    while head:
        print(head.data, end=" ")
        head = head.right