## 2010年10月10日 星期日

### [ 資料結構 小學堂 ] 樹狀結構導論 : 二元樹的儲存方式

* BTreeInLS.h 代碼 :

1. #include
2.
3. using namespace std;
4.
5. class BTreeInLSNode  {
6. public:
7.     int data; // 節點資料
8.     class BTreeInLSNode *left, *right; // 節點左指標及右指標
9.     BTreeInLSNode(){
10.         data = -1;
11.         left = NULL;
12.         right = NULL;
13.     }
14. };
15.
16. typedef class BTreeInLSNode btmNode;
17. typedef btmNode *btmNodePoint;
18.
19. class BTreeInLS{
20.     btmNodePoint rootNode;
21.     int level;
22. public:
23.     BTreeInLS(){
24.         rootNode = NULL;
25.         level = 0;
26.     }
28.     virtual void showData();
29.     virtual int getLevel();
30. protected:
31.     virtual void _showNode(int level, int curLeve,  btmNodePoint np);
32. };
* BTreeInLS.cpp 代碼 :

1. #include "BTreeInLS.h"
2.
5.     if(rootNode == NULL) {
6.         rootNode = new BTreeInLSNode;
7.         rootNode->data = v;
8.         rootNode->left = NULL;
9.         rootNode->right = NULL;
10.         level = 1;
11.     } else {
12.         btmNodePoint tmpPoint = rootNode;
13.         btmNodePoint prevPoint;
14.         int tmpLevel = 1;
15.         int direction = -1//0 is left, 1 is right
16.         while(true) {
17.             if(tmpPoint == NULL) {
18.                 tmpPoint = new BTreeInLSNode;
19.                 tmpPoint->data = v;
20.                 tmpPoint->left = NULL;
21.                 tmpPoint->right = NULL;
22.                 if(tmpLevel>level)
23.                     level = tmpLevel; //紀錄目前最高Level
24.                 if(direction==0) {
25.                     prevPoint->left = tmpPoint;
26.                 } else {
27.                     prevPoint->right = tmpPoint;
28.                 }
29.                 break;
30.             } else if(tmpPoint->data < v) { // 往右子樹移動
31.                 prevPoint = tmpPoint;
32.                 tmpPoint = tmpPoint->right;
33.                 tmpLevel++;
34.                 direction = 1;
35.             } else {  // 往左子樹移動
36.                 prevPoint = tmpPoint;
37.                 tmpPoint = tmpPoint->left;
38.                 tmpLevel++;
39.                 direction = 0;
40.             }
41.         }
42.     }
43. }
44.
45.
46. void BTreeInLS::showData(){
47.     for(int i=1; i<=level; i++) {
48.         this->_showNode(i, 1, rootNode);
49.         cout << endl;
50.     }
51. }
52.
53. void BTreeInLS::_showNode(int level, int curLevel, btmNodePoint np) {
54.     if(level == curLevel) {
55.         if(np!=NULL) {
56.             cout << "[" << np->data << "] ";
57.         } else {
58.             cout << "[0] " ;
59.         }
60.     } else if(level> curLevel && np!= NULL) {
61.         this->_showNode(level, curLevel+1, np->left);
62.         this->_showNode(level, curLevel+1, np->right);
63.     }
64. }
65.
66. int BTreeInLS::getLevel(){
67.     return level;
68. }
* 呼叫演算法代碼 :

1. void ch06_01(bool b) {
2.     if(b) {
3.         int data[] = {0,6,3,5,9,7,8,4,2}; // 原始陣列
4.         int bdata[16] = {0}; //存放二元樹陣列
5.         BTreeInLS bTree;
6.         cout << "原始陣列內容:" << endl;
7.         for(int i=1; i<9; i++)
8.             cout << "[" << data[i] << "] ";
9.         cout << endl;
10.         // 把原始陣列放進二元樹陣列
11.         for(int i=1; i<9; i++) {
13.             int level = 1;
14.             for(;bdata[level]>0;) {
15.                 if(data[i] > bdata[level]) //如果陣列的值大於樹根, 往右子樹比較
16.                     level = level*2 + 1;
17.                 else // 如果陣列的值小於等於樹根, 往左子樹比較
18.                     level = level*2;
19.             }
20.             bdata[level] = data[i];
21.         }
22.         cout << "二元樹內容(陣列) :" << endl;
23.         for(int i=1; i<16; i++)
24.             cout << "[" << bdata[i] << "] " ;
25.         cout << endl;
26.         cout << "二元樹內容(鏈結串列):" << endl;
27.         bTree.showData();
28.     }
29. }

[6] [3] [5] [9] [7] [8] [4] [2]

[6] [3] [9] [2] [5] [7] [0] [0] [0] [4] [0] [0] [8] [0] [0]

[6]
[3] [9]
[2] [5] [7] [0]
[0] [0] [4] [0] [0] [8]

* [ 資料結構 小學堂 ] 樹狀結構導論 : 樹
[ 資料結構 小學堂 ] 樹狀結構導論 : 二元樹的儲存方式 - Java version

### [ Python 文章收集 ] List Comprehensions and Generator Expressions

Source From  Here   Preface   Do you know the difference between the following syntax?  view plain copy to clipboard print ? [x  for ...