将搜索二叉树转换成双向链表

【说明】：

　　本文是左程云老师所著的《程序员面试代码指南》第二章中“将搜索二叉树转换成双向链表”这一题目的C++复现。

　　本文只包含问题描述、C++代码的实现以及简单的思路，不包含解析说明，具体的问题解析请参考原书。

　　感谢左程云老师的支持。

【题目】：

　　对于二叉树的节点来说，有本身的值域，有指向左孩子和右孩子的两个指针；对双向链表的节点来说，有本身的值域，有指向上一个节点和下一个节点的指针。在结构上，两种结构有相似性，现有一棵搜索二叉树，请将其转为成一个有序的双向链表。

　　例如，节点定义为：

 1  class Node
 2   8 {
 3   9 public:
 4  10     Node(int data)
 5  11     {
 6  12         value = data;
 7  13         left = NULL;
 8  14         right = NULL;
 9  15     }
10  16 public: 
11  17     int value;
12  18     Node *left;
13  19     Node *right;
14  20 };

View Code

　　一棵搜索二叉树如图所示。

　　这棵二查搜索树转换后的双向链表从头到尾依次是 1～9。对于每一个节点来说，原来的 right 指针等价于转换后的 next 指针，原来的 left 指针等价于转换后的 last 指针，最后返回转换后的双向链表的头节点。

　　注：二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。　　

【思路】：

　　解法一：利用队列和二叉树的中序遍历；

　　解法二：递归实现，递归的返回值为链表的尾部节点，并且将尾部节点的 right 指向头节点；

【编译环境】：

　　CentOS6.7（x86_64）

　　gcc 4.4.7

【实现】：

　　头文件声明代码：

 1 /*
 2  *文件名：bt_convert_list.h
 3  *作者：
 4  *摘要：声明文件
 5  */
 6 #include <iostream>
 7 #include <queue>
 8 
 9 using namespace std;
10 
11 class Node
12 {
13 public:
14     Node(int data)
15     {
16         value = data;
17         left = NULL;
18         right = NULL;
19     }
20 public:
21     int value;
22     Node *left;
23     Node *right;
24 };
25 
26 void bt_insert(Node **head,int data);    //搜索二叉树之插入节点
27 void preOrderRecur(Node *head);    //先序遍历输出二叉树节点值
28 
29 //第一种转换方法
30 void inOrderToQueue(Node *head,queue<Node*> &q);
31 Node* convert1(Node *head);
32 //第二种转换方法
33 Node* process(Node *head);
34 Node* convert2(Node *head);
35 
36 void printList(Node *head);    //打印链表值

View Code

　　实现代码：

  1 /*
  2  *文件名：bt_convert_list.cpp
  3  *作者
  4  *摘要：将搜索二叉树转换成双向链表
  5  */
  6 
  7 #include "bt_convert_list.h"
  8 
  9 //搜索二叉树之插入节点
 10 void bt_insert(Node **head,int data)
 11 {
 12     if(NULL == *head)    //根节点为空
 13     {
 14         *head = new Node(data);
 15         return ;
 16     }
 17 
 18     if(NULL == (*head)->left && data < (*head)->value)    //插入左孩子
 19     {
 20         (*head)->left = new Node(data);
 21         return ;
 22     }
 23 
 24     if(NULL == (*head)->right && data > (*head)->value)    //插入右孩子
 25     {
 26         (*head)->right = new Node(data);
 27         return ;
 28     }
 29     
 30     if(data < (*head)->value)
 31         bt_insert(&((*head)->left),data);
 32     else if(data > (*head)->value)
 33         bt_insert(&((*head)->right),data);
 34     else
 35         return ;
 36 }
 37 
 38 //先序遍历
 39 void preOrderRecur(Node *head)
 40 {
 41     if(NULL == head)
 42         return ;
 43     cout << head->value << " ";
 44     preOrderRecur(head->left);
 45     preOrderRecur(head->right);
 46 }
 47 
 48 //利用中序遍历将二叉树节点插入队列中
 49 void inOrderToQueue(Node *head,queue<Node*> &q)
 50 {
 51     if(NULL == head)
 52         return ;
 53     inOrderToQueue(head->left,q);
 54     q.push(head);
 55     inOrderToQueue(head->right,q);
 56     return ;
 57 }
 58 
 59 Node* convert1(Node *head)
 60 {
 61     queue<Node*> q;
 62     inOrderToQueue(head,q);
 63     //处理头节点
 64     head = q.front();
 65     q.pop();
 66     Node *pre = head;
 67     pre->left = NULL;
 68     
 69     Node *cur = NULL;
 70     while(!q.empty())
 71     {
 72         cur = q.front();
 73         q.pop();
 74         pre->right = cur;
 75         cur->left = pre;
 76         pre = cur;
 77     }
 78     cur->right = NULL;
 79     return head;
 80 }
 81 
 82 //第二种方法
 83 Node* process(Node *head)
 84 {
 85     if(NULL == head)
 86         return NULL;
 87     Node *leftE = process(head->left);
 88     Node *rightE = process(head->right);
 89 
 90     Node *leftS = NULL != leftE ? leftE->right : NULL ;
 91     Node *rightS = NULL != rightE ? rightE->right : NULL ;
 92 
 93     if(NULL != leftE && NULL != rightE)
 94     {
 95         leftE->right = head;
 96         head->left = leftE;
 97         head->right = rightS;
 98         rightS->left = head;
 99         rightE->right = leftS;        //尾指向头
100         return rightE;        //返回尾部指针
101     }
102     else if(NULL != leftE)
103     {
104         leftE->right = head;
105         head->left = leftE;
106         head->right = leftS;    //尾指向头
107         return head;    //返回尾部指针
108     }
109     else if(NULL != rightE)
110     {
111         head->right = rightS;
112         rightS->left = head;
113         rightE->right = head;    //尾指向头
114         return rightE;            //返回尾
115     }
116     else
117     {
118         head->right = head;        //尾指向头
119         return head;            //返回尾
120     }
121 }
122 
123 Node* convert2(Node *head)
124 {
125     if(NULL == head)
126         return NULL;
127     Node *last = process(head);
128     head = last->right;
129     last->right = NULL;
130     return head;
131 
132 }
133 
134 //打印链表
135 void printList(Node *head)
136 {
137     while(NULL != head)
138     {
139         cout << head->value << " ";
140         head = head->right;
141     }
142     cout << endl;
143 }

View Code

　　测试代码：

 1 /*
 2  *文件名：mian.cpp
 3  *作者：
 4  *摘要：测试代码
 5  */
 6 
 7 #include "bt_convert_list.h"
 8 
 9 int main()
10 {
11     int arr[] = {6,4,7,2,5,9,1,3,8};
12     //创建搜索二叉树
13     Node *head = NULL;
14     for(int i = 0;i < 9; i++)
15     {
16         bt_insert(&head,arr[i]);
17     }
18     cout << "The nodes of Binary Tree are:" << endl;
19     preOrderRecur(head);
20     cout << endl;
21 
22     //head = convert1(head);
23     head = convert2(head);
24     cout << "The nodes of list are:" << endl;
25     printList(head);
26 
27 
28     return 0;
29 }

View Code

注：

　　转载请注明出处；

　　转载请注明源思路来自于左程云老师的《程序员代码面试指南》。