17.13 Consider a simple node-like data structure called BiNode, which has pointers to two other nodes. The data structure BiNode could be used to represent both a binary tree (where nodel is the left node and node2 is the right node) or a doubly linked list (where nodel is the previous node and node2 is the next node). Implement a
method to convert a binary search tree (implemented with BiNode) into a doubly linked list. The values should be kept in order and the operation should be performed in place (that is, on the original data structure).
这道题定义了一个双向节点BiNode的类，其既可以表示二叉树的结构，也可以表示为双向链表的结构，让我们把一个二叉树的结构转化为双向链表的结构。我们有很多种方法可以实现，首先来看一种建立一种新数据结构NodePair类，保存了链表的首节点和尾节点，用递归的方法来实现压平二叉树，参见代码如下：
解法一：
class BiNode { public: BiNode *node1; BiNode *node2; int data; BiNode(int d): data(d), node1(NULL), node2(NULL) {} }; class NodePair { public: BiNode *head; BiNode *tail; NodePair(BiNode *h, BiNode *t): head(h), tail(t) {} }; void concat(BiNode *x, BiNode *y) { x->node2 = y; y->node1 = x; } NodePair* convert(BiNode *root) { if (!root) return NULL; NodePair *part1 = convert(root->node1); NodePair *part2 = convert(root->node2); if (part1) concat(part1->tail, root); if (part2) concat(root, part2->head); return new NodePair(part1 ? part1->head : root, part2 ? part2->tail : root); }
我们也可以不使用别的数据结构，那么我们如何返回链表的首结点和尾结点呢，我们可以返回首结点，然后通过遍历链表来找到尾结点，参见代码如下：
解法二：
int cnt = 0; class BiNode { public: BiNode *node1; BiNode *node2; int data; BiNode(int d): data(d), node1(NULL), node2(NULL) {} }; void concat(BiNode *x, BiNode *y) { x->node2 = y; y->node1 = x; } BiNode* get_tail(BiNode *node) { if (!node) return NULL; while (node->node2) { ++cnt; node = node->node2; } return node; } BiNode* convert(BiNode *root) { if (!root) return NULL; BiNode *part1 = convert(root->node1); BiNode *part2 = convert(root->node2); if (part1) concat(get_tail(part1), root); if (part2) concat(root, part2); return part1 ? part1 : root; }
还有一种方法是创建一个循环链表，当我们建立了循环链表，那么我们返回首结点时，尾结点可以通过head->node1直接找到，参见代码如下：
解法三：
class BiNode { public: BiNode *node1; BiNode *node2; int data; BiNode(int d): data(d), node1(NULL), node2(NULL) {} }; void concat(BiNode *x, BiNode *y) { x->node2 = y; y->node1 = x; } BiNode* convert_to_circular(BiNode *root) { if (!root) return NULL; BiNode *part1 = convert_to_circular(root->node1); BiNode *part3 = convert_to_circular(root->node2); if (!part1 && !part3) { root->node1 = root; root->node2 = root; return root; } BiNode *tail3 = part3 ? part3->node1 : NULL; // Join left to root if (!part1) concat(part3->node1, root); else concat(part1->node1, root); // Join right to root if (!part3) concat(root, part1); else concat(root, part3); // Join right to left if (part1 && part3) concat(tail3, part1); return part1 ? part1 : root; } BiNode* convert(BiNode *root) { BiNode *head = convert_to_circular(root); head->node1->node2 = NULL; head->node1 = NULL; return head; }
本文转自博客园Grandyang的博客，原文链接：双向节点[CareerCup] 17.13 BiNode ，如需转载请自行联系原博主。