二叉排序樹的基本思想是將序列中的數(shù)讀入一個二叉樹,在讀入時遵循一定的規(guī)則:比如,如果二叉樹的一個節(jié)點有左子節(jié)點,那么左子節(jié)點一定比父節(jié)點的值?。蝗绻粋€節(jié)點有右子節(jié)點,那么右子節(jié)點一定比父節(jié)點的值大。在二叉排序樹制造完成后,通過采用中序遍歷的方法讀取二叉樹節(jié)點的值到序列中,就可以得到一個升序序列。
讀取二叉排序樹的操作為:
1,如果節(jié)點非空:
1.1,如果節(jié)點的左子節(jié)點非空,將左子節(jié)點設(shè)為操作節(jié)點,返回1;
1.2,如果節(jié)點左子節(jié)點為空,取節(jié)點數(shù)據(jù)到序列中;
1.2.1,如果節(jié)點右子節(jié)點非空,并且節(jié)點的父節(jié)點非空,令當前節(jié)點的右子節(jié)點為父節(jié)點的子節(jié)點;如果父節(jié)點為空,令右子節(jié)點為操作節(jié)點;
1.2.2,如果右子節(jié)點為空,并且父節(jié)點非空,令父節(jié)點的左子節(jié)點為空,令父節(jié)點為操作節(jié)點,釋放當前節(jié)點;,
2,如果節(jié)點為空,輸出序列。
C++代碼實現(xiàn)
#include#includeusing?namespace?std; templatevoid?BinaryTreeSort(vector&vec); int?main() { int?att[]?=?{?10,?4,?23,?46,?20,?5,?3,?88,?8,?44,?53,?25,?86,?32,?16,?11?}; vectorvec(&att[0],?&att[sizeof(att)?/?sizeof(int)]); BinaryTreeSort(vec); return?0; } templatevoid?BinaryTreeSort(vector&vec) { int?VSize?=?vec.size(); if?(VSize?data?=?vec[0]; headNode->father?=?NULL; headNode->left?=?NULL; headNode->right?=?NULL; for?(int?vIdx?=?1;?vIdx?<?VSize;?vIdx++) { SortNode?*locNode?=?new?SortNode(); locNode->data?=?vec[vIdx]; locNode->father?=?NULL; locNode->left?=?NULL; locNode->right?=?NULL; SortNode?*tmpNode?=?headNode; while?(NULL?!=?tmpNode) { if?(locNode->data?<?tmpNode->data) { if?(NULL?==?tmpNode->left) { locNode->father?=?tmpNode; tmpNode->left?=?locNode; tmpNode?=?NULL; } else { tmpNode?=?tmpNode->left; } } else { if?(NULL?==?tmpNode->right) { locNode->father?=?tmpNode; tmpNode->right?=?locNode; tmpNode?=?NULL; } else { tmpNode?=?tmpNode->right; } } } } SortNode?*tmpNode?=?headNode; int?vIdx?=?0; while?(NULL?!=?tmpNode) { if?(NULL?==?tmpNode->left) { vec[vIdx++]?=?tmpNode->data;???//?if?left?child?is?null,?get?this?node?data if?(NULL?!=?tmpNode->right)????//?if?right?child?is?not?null,?set?right?child?as?father's?child { if?(NULL?!=?tmpNode->father) { if?(tmpNode?==?tmpNode->father->left) tmpNode->father->left?=?tmpNode->right; else?if?(tmpNode?==?tmpNode->father->right) tmpNode->father->right?=?tmpNode->right; } tmpNode->right->father?=?tmpNode->father; SortNode?*childNode?=?tmpNode->right; delete?tmpNode; tmpNode?=?childNode; } else { SortNode?*FartherNode?=?tmpNode->father; if?(NULL?!=?FartherNode) FartherNode->left?=?NULL; tmpNode->father?=?NULL; delete?tmpNode; tmpNode?=?FartherNode; } } else { tmpNode?=?tmpNode->left; } } vIdx?=?0; for?(;?vIdx?<?VSize;?vIdx++) { cout?<<?"index?"?<<?vIdx?<<?"?value?=?"?<<?vec[vIdx]?<<?endl; } return; }