【剣指offer面接問題27】二叉検索ツリーと双方向チェーンテーブル

ツリーを入力し、ツリーをソートされた双方向チェーンテーブルに変換します.
C++:

 1 #include <iostream>

 2 using namespace std;

 3 

 4 struct TreeNode

 5 {

 6     int val;

 7     TreeNode *left;

 8     TreeNode *right;

 9     TreeNode(int x = 0):val(x), left(NULL), right(NULL){}

10 };

11 

12 void ConvertNode(TreeNode *pNode, TreeNode **pLastNode)

13 {

14     if(pNode == 0)

15         return ;

16 

17     if(pNode->left != 0)

18         ConvertNode(pNode->left, pLastNode);

19 

20     pNode->left = (*pLastNode);

21     if((*pLastNode) != 0)

22         (*pLastNode)->right = pNode;

23     (*pLastNode) = pNode;

24 

25     if(pNode->right != 0)

26         ConvertNode(pNode->right, pLastNode);

27 }

28 

29 int main()

30 {

31     TreeNode *root = new TreeNode(10);

32     TreeNode *node6 = new TreeNode(6);

33     TreeNode *node14 = new TreeNode(14);

34     TreeNode *node4 = new TreeNode(4);

35     TreeNode *node8 = new TreeNode(8);

36     TreeNode *node12 = new TreeNode(12);

37     TreeNode *node16 = new TreeNode(16);

38 

39     root->left = node6;

40     root->right = node14;

41     node6->left = node4;

42     node6->right = node8;

43     node14->left = node12;

44     node14->right = node16;

45 

46     TreeNode *pLastNode = NULL;

47     ConvertNode(root, &pLastNode);

48 

49     while(pLastNode != 0)

50     {

51         cout<<pLastNode->val<<" ";

52         pLastNode = pLastNode->left;

53     }

54 }