1 #include <iostream>
  2 
  3 using namespace std;
  4 
  5 template<class T>
  6 struct tree_node
  7 {
  8     T data;
  9     tree_node * left_child;
 10     tree_node * right_child;
 11 };
 12 
 13 /*************************************************
 14 Function:       // double_stack
 15 Description:    // 二叉樹構建函數(shù)，采用遞歸方法
 16                    實現(xiàn)二叉樹到雙列表的轉換。通過
 17                    中序遍歷方法遞歸遍歷整個樹
 18 Input:          // root： 樹根節(jié)點
 19 Return:         // 無
 20 *************************************************/
 21 template<class T>
 22 void recursion(tree_node<T> * root)
 23 {
 24     tree_node<T> *temp;
 25     if(root != NULL)
 26     {
 27         //遍歷左子樹，找到已經(jīng)轉換成列表的左子樹列表中最右邊的一個node
 28         //與root節(jié)點連接成為其左邊節(jié)點
 29         recursion(root->left_child);
 30         temp = root->left_child;        
 31         if(temp != NULL)
 32         {
 33             while(temp->right_child != NULL)
 34             {
 35                 temp = temp->right_child;
 36             }
 37             temp->right_child = root;
 38             root->left_child = temp;
 39         }
 40 
 41         //遍歷右子樹，找到已經(jīng)轉換成列表的左子樹列表中最左邊的一個node
 42         //與root節(jié)點連接成為其左邊節(jié)點
 43         recursion(root->right_child);
 44         temp = root->right_child;
 45         if(temp != NULL)
 46         {
 47             while (temp->left_child != NULL)
 48             {
 49                 temp = temp->left_child;
 50             }
 51             temp->left_child = root;
 52             root->right_child = temp;
 53         }
      }
 55 }
 56 
 57 /*************************************************
 58 Function:       // trans_algorithm
 59 Description:    // 封裝遞歸調(diào)用函數(shù)
 60 Input:          // root 二叉樹根節(jié)點
 61 Return:         // 無
 62 *************************************************/
 63 template<class T>
  void trans_algorithm(tree_node<T> *&root)
 65 {
 66     recursion(root);
 67     if(root != NULL)
 68     {
 69         while(root->left_child != NULL)
 70         {
 71             root = root->left_child;
 72         }
 73     }
 74 }
 75 
 76 /*************************************************
 77 Function:       // insert_node
 78 Description:    // 插入一個樹節(jié)點到一棵樹中
 79 Input:          // root：樹的根節(jié)點
 80                 // data: 樹節(jié)點值
 81 Return:         // 無
 82 *************************************************/
 83 template<class T>
 84 static void insert_node(tree_node<T> *root, T data)
 85 {
 86     tree_node<int> *new_node = new tree_node<int>;
 87     new_node->left_child = NULL;
 88     new_node->right_child = NULL;
      new_node->data = data;
 90     
 91     tree_node<int> *temp, *temp1;
 92     temp = root;
 93     while(temp != NULL)
 94     {
 95         temp1 = temp;
 96         if(temp->data > data)
 97         {                
 98             temp = temp->left_child;
 99         }
100         else
101         {
102             temp = temp->right_child;
103         }
104     }
105     if(temp1->data > data)
106     {
107         temp1->left_child = new_node;
108     }
109     else
110     {
111         temp1->right_child = new_node;
112     }
113 }
114 
115 void main()
116 {    
117     //構建一個排序二叉樹
118     tree_node<int> *root = new tree_node<int>;
119     tree_node<int> *temp, *temp1;
120     root->left_child = NULL;
121     root->right_child = NULL;
122     root->data = 10;    
123     insert_node(root, 6);
124     insert_node(root, 4);
125     insert_node(root, 8);
126     insert_node(root, 3);
127     insert_node(root, 5);
128     insert_node(root, 7);
129     insert_node(root, 9);
130     insert_node(root, 2);
131     insert_node(root, 13);
132     insert_node(root, 12);
133     insert_node(root, 17);
134     insert_node(root, 14);
135     insert_node(root, 16);
136     insert_node(root, 15);
137     insert_node(root, 1);
138     insert_node(root, 20);
139     
140     //調(diào)用轉換函數(shù)
141     trans_algorithm(root);
142     //刪除節(jié)點及節(jié)點分配的內(nèi)存空間
143     while(root != NULL)
144     {
145         cout << root->data << " ";
146         temp = root;
147         root = root->right_child;
148         delete temp;
149     }
150 }