アルゴリズムの問題-ツリーを双方向チェーンテーブルに変換
6219 ワード
何海濤ブログ:ツリーがソートされる双方向チェーンテーブル
考え方:再帰.ルートが空の場合、直接戻ります. 左サブツリーを先に変換し、変換に成功すると、左サブツリーを変換したチェーンテーブルの最後のノードとルートが接続される. 右サブツリーを再変換し、変換後のチェーンテーブルの最初のノードとルートを接続します. は、最後にチェーンヘッダ/テールノードに戻る.
考え方:再帰.
1 struct TreeNode
2 {
3 int val;
4 TreeNode *left, *right;
5 };
6
7 TreeNode *BTree2List(TreeNode *root, bool asRight)
8 {
9 if(root == NULL)
10 return NULL;
11
12 TreeNode *pLeft = NULL;
13 TreeNode *pRight = NULL;
14
15 //
16 if(root->left != NULL)
17 pLeft = BTree2List(root->left, false);
18
19 // ，
20 if(pLeft != NULL)
21 {
22 pLeft->right = root;
23 root->left = pLeft;
24 }
25
26 //
27 if(root->right != NULL)
28 pRight = BTree2List(root->right, true);
29
30 // ，
31 if(pRight != NULL)
32 {
33 pRight->left = root;
34 root->right = pRight;
35 }
36
37 // ， ；
38 TreeNode *pRet = root;
39
40 if(asRight)
41 {
42 while(pRet->left != NULL)
43 pRet = pRet->left;
44 }
45 else
46 {
47 while(pRet->right != NULL)
48 pRet = pRet->right;
49 }
50
51 return pRet;
52 }
53
54 TreeNode *TreeToList(TreeNode *root)
55 {
56 return BTree2List(root, true);
57 }