| |
Title: Enter a search tree two yuan, two yuan to find the tree into a sort of two-way linked list. Requirements can not create any new node, adjust the pointers point only.
For example, dibasic search tree
10
/ \
614
/ \ / \
481216
Converted into a doubly linked list
4 = 6 = 8 = 10 = 12 = 14 = 16.
Ideas: a lot of problems for the tree, you can use the recursive method to deal with. This question is no exception. Our most basic way of considering this topic.
The right to a binary programming doubly linked list, the final is an ordered sequence, that is, after the results of traversal, then when we use the traversal traverse binary tree traversal to a node, the node is a preamble pointer to the current node, then left pointer points to the preamble of the current node node, then the node so that the preamble refers to the current node.
BinTree * head = NULL;
void helper (BinTree * root, BinTree * & pre)
{
if (root == NULL && root == NULL)
return;
helper (root-> left, pre);
if (head == NULL)
head = root;
if (pre == NULL)
pre = root;
else
{
root-> left = pre;
pre-> right = root;
pre = root;
}
// Cout < < root-> value < < "" < < endl;
helper (root-> right, pre);
}
BinTree * SearchTreeConverstToList (BinTree * root)
{
BinTree * pre = NULL;
helper (root, pre);
return head;
}
Thought two: If the current node, we put the right sub-tree into a doubly linked list, and then left sub-tree into a doubly linked list, when we marked the conversion of the head node and tail node of the list, so we only need to the current node and tail left subtree is connected to the head and right subtree is connected to.
void helper_second (BinTree * root, BinTree * & head, BinTree * & tail)
{
if (root == NULL || (root-> left == NULL && root-> right == NULL))
{
head = root;
tail = root;
return;
}
BinTree * left_head = NULL;
BinTree * left_tail = NULL;
BinTree * right_head = NULL;
BinTree * right_tail = NULL;
helper_second (root-> left, left_head, left_tail);
helper_second (root-> right, right_head, right_tail);
if (left_head == NULL)
head = root;
else
{
head = left_head;
left_tail-> right = root;
root-> right = left_tail;
}
if (right_head == NULL)
tail = root;
else
{
tail = right_tail;
root-> right = right_head;
right_head-> left = root;
}
}
BinTree * ConverstToList (BinTree * root)
{
BinTree * head = NULL;
BinTree * tail = NULL;
helper_second (root, head, tail);
return head;
} |
|
|
|