BST与双向链表

把BST转换为双向链表

给出一棵BST，将其转换为双向链表，left保存前节点，right保存后节点。

例如：

                4

                /  \

            1      7

          /  \    / \   

        0    2  5    8

                \  \    \           

                  3  6    9

变为：0<->1<->2<->3<->4<->5<->6<->7<->8<->9.

解答：这里我们可以看到一个节点的左子树的最后节点就是本节点的前驱，右子树的最左节点就是后继。于是需要一个函数能够返回这样的需求，也就有了一个可以返回本棵树的左右节点的函数。

同时，在细节上进行一些处理。

#include <iostream>

using namespace std;

struct Node  {

    int val;

    Node *left;

    Node *right;

    Node():left(NULL), right(NULL){}

};

struct LeftRightNode

{

    Node *left;

    Node *right;

    LeftRightNode(){}

                    LeftRightNode(Node *l, Node *r):left(l), right(r){}

};

LeftRightNode convert(Node *node)

{

    if (node == NULL)

    {

        LeftRightNode ret;

        return LeftRightNode(NULL, NULL);

    }

LeftRightNode leftTree = convert(node->left);

LeftRightNode rightTree = convert(node->right);

      node->left = leftTree.right;

    if (leftTree.right)

        leftTree.right->right = node;

        node->right = rightTree.left; if (rightTree.left)

        rightTree.left->left = node;

Node *leftNode = leftTree.left ? leftTree.left : node;

Node *rightNode = rightTree.right ? rightTree.right : node;

return LeftRightNode(leftNode, rightNode);

}

Node *convert2List(Node *head)

{

      LeftRightNode ret = convert(head);                return ret.left;

}

void print(Node *node)

{

    while(node)

    {   

cout << "Node val:" << node->val << " address:" << node << " left:" << node->left << " right:" << node->right << endl;            node = node->right; 

    }

}

    int main()

  {

          Node node[10];

          for(int i = 0; i < 10; i++)

              node[i].val = i;

          node[4].left = &node[1];

          node[4].right = &node[7];

          node[1].left = &node[0];

          node[1].right = &node[2];

          node[2].right = &node[3];

        node[7].left = &node[5];

        node[7].right = &node[8];

        node[5].right = &node[6];

        node[8].right = &node[9];

        Node *head = convert2List(&node[4]);

        print(head);

}