1. If left subtree exists, process the left subtree
…..1.a) Recursively convert the left subtree to DLL.
…..1.b) Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).
…..1.c) Make inorder predecessor as previous of root and root as next of inorder predecessor.
2. If right subtree exists, process the right subtree (Below 3 steps are similar to left subtree).
…..2.a) Recursively convert the right subtree to DLL.
…..2.b) Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).
…..2.c) Make inorder successor as next of root and root as previous of inorder successor.
3. Find the leftmost node and return it (the leftmost node is always head of converted DLL).
要求将二叉树转换为其对应的中序遍历双向链表
注意,在每次递归后返回的都是之前传递来的root
对于左子树的递归处理使得左子树成为其对应于中序遍历顺序的双向 链表。当递归
返回到根节点时left(递归中定义的那个)指向原来左子树的根 节点(现在在中
序遍历双向链表的中间),root指向根节点;通过for (; left->right!=NULL;
left=left->right) 将left指向中序遍历过程中的根节点的前序节点,现在将新的
left和root联系起来
同理, 对于右子树的递归处理使得右子树成为其对应于中序遍历顺序的双向 链表。
当递归返回到根节点时,right(递归中定义的那个)指向原来 右子树的根节点
(现在在中序遍历双向链表的中间),root指向根节点;通过 for (;
right->left!=NULL; right = right->left) 将right指向中序遍历过程中的根节点
的后继节点,现在将新的right和root联系起来
Read full article from Convert a given Binary Tree to Doubly Linked List | Set 1 | GeeksforGeeks
…..1.a) Recursively convert the left subtree to DLL.
…..1.b) Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).
…..1.c) Make inorder predecessor as previous of root and root as next of inorder predecessor.
2. If right subtree exists, process the right subtree (Below 3 steps are similar to left subtree).
…..2.a) Recursively convert the right subtree to DLL.
…..2.b) Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).
…..2.c) Make inorder successor as next of root and root as previous of inorder successor.
3. Find the leftmost node and return it (the leftmost node is always head of converted DLL).
要求将二叉树转换为其对应的中序遍历双向链表
注意,在每次递归后返回的都是之前传递来的root
对于左子树的递归处理使得左子树成为其对应于中序遍历顺序的双向
返回到根节点时left(递归中定义的那个)指向原来左子树的根 节点(现在在中
序遍历双向链表的中间),root指向根节点;通过for (; left->right!=NULL;
left=left->right)
left和root联系起来
同理,
当递归返回到根节点时,right(递归中定义的那个)指向原来 右子树的根节点
(现在在中序遍历双向链表的中间),root指向根节点;通过 for (;
right->left!=NULL; right = right->left)
的后继节点,现在将新的right和root联系起来
/* This is the core function to convert Tree to list. This function follows
steps 1 and 2 of the above algorithm */
node* bintree2listUtil(node* root)
{
// Base case
if
(root == NULL)
return
root;
// Convert the left subtree and link to root
if
(root->left != NULL)
{
// Convert the left subtree
node* left = bintree2listUtil(root->left);
// Find inorder predecessor. After this loop, left
// will point to the inorder predecessor
for
(; left->right!=NULL; left=left->right);
// Make root as next of the predecessor
left->right = root;
// Make predecssor as previous of root
root->left = left;
}
// Convert the right subtree and link to root
if
(root->right!=NULL)
{
// Convert the right subtree
node* right = bintree2listUtil(root->right);
// Find inorder successor. After this loop, right
// will point to the inorder successor
for
(; right->left!=NULL; right = right->left);
// Make root as previous of successor
right->left = root;
// Make successor as next of root
root->right = right;
}
return
root;
}
// The main function that first calls bintree2listUtil(), then follows step 3
// of the above algorithm
node* bintree2list(node *root)
{
// Base case
if
(root == NULL)
return
root;
// Convert to DLL using bintree2listUtil()
root = bintree2listUtil(root);
// bintree2listUtil() returns root node of the converted
// DLL. We need pointer to the leftmost node which is
// head of the constructed DLL, so move to the leftmost node
while
(root->left != NULL)
root = root->left;
return
(root);
}