2019獨角獸企業(yè)重金招聘Python工程師標準>>>

背景

接上面五篇文章
算法踩坑-快速排序
算法踩坑2-插入排序
算法踩坑3-堆排序
算法踩坑4-冒泡排序
算法踩坑5-歸并排序

來繼續(xù)聊聊最近我寫的一些算法的小例程，這次要聊的是使用二叉搜索樹實現(xiàn)的排序，是一個時間復雜度O(N)的算法。

主要從以下幾方面來說的：

• 二叉搜索樹排序思想
• 二叉搜索樹排序實現(xiàn)

二叉搜索樹排序思想

二叉搜索樹的排序能夠達到時間復雜度O(N)的前提是序列的數(shù)據(jù)結構需要是二叉搜索樹，二叉搜索樹的結構是每個非葉子節(jié)點最多有2個孩子節(jié)點，并且對于任一個節(jié)點，左孩子節(jié)點的關鍵字小于父父節(jié)點的關鍵字，右孩子節(jié)點的關鍵字大于父節(jié)點的關鍵字，因此使用中序遍歷的方式（左子樹->父節(jié)點->右子樹）可以得到一個從小到大的有序序列。
因為只要遍歷一遍二叉搜索樹就能得到排序的序列，所有時間復雜度為O(N)。

二叉搜索樹排序實現(xiàn)

二叉搜索樹的插入

二叉搜索樹核心的地方就在于節(jié)點的插入，使用遞歸的方式插入新的節(jié)點，需要注意的地方在于新的節(jié)點的插入需要返回改節(jié)點的指針，然后把某個節(jié)點的左孩子指針或者是右孩子的指針指向新創(chuàng)建的節(jié)點。
Tree_Insert

SearchTree Tree_Insert(ElementType Element, SearchTree T) {if (NULL == T) {T = malloc(sizeof(struct TreeNode));T->Element = Element;T->Count = 1;// 左右子樹置為空T->Left = T->Right = NULL;} else if (Element < T->Element) {T->Left = Tree_Insert(Element, T->Left);} else if (Element > T->Element) {T->Right = Tree_Insert(Element, T->Right);} else {T->Count ++;}// 返回最終插入的位置return T; }

二叉搜索樹的中序遍歷

二叉搜索樹的節(jié)點中保存Count信息用于處理重復數(shù)據(jù)的個數(shù)信息，這種做法用于節(jié)點的關鍵字的數(shù)據(jù)是簡單的數(shù)據(jù)類型，而不是某個復雜數(shù)據(jù)類型的其中某個關鍵字，如果用于排序的關鍵字是某個復雜數(shù)據(jù)類型的某個關鍵字，需要使用額外的空間來保存源數(shù)據(jù)的數(shù)據(jù)信息。

// Left->Middle->Right 中序遍歷 void Tree_LMR_Travel(SearchTree T) {if (NULL == T) {return;}if(NULL != T->Left) Tree_LMR_Travel(T->Left);int i;for (i= 0; i<T->Count; i++) {printf("%d ", T->Element);}if(NULL != T->Right) Tree_LMR_Travel(T->Right); }

One More Thing

噢！我是算法，點我

轉載于:https://my.oschina.net/FEEDFACF/blog/1570424

總結

以上是生活随笔為你收集整理的算法踩坑6-二叉搜索树排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。