1. 將一組無序的整型數據排序生成一顆排序二叉樹，使得對這顆二叉樹進行中序遍歷可以得到遞增有序序列。
#include <stdio.h>
#include <stdlib.h>
typedef struct BT{
int data;
BT *L_child;
BT *R_child;
}BT;
int add_sort(BT *fa,int num)//插入排山沒缺序
{
if(fa->data>=num)//輸入小於等於根結點，排在左子樹
{
if(fa->L_child==NULL)//左子樹為逗辯空，新建左察猜子樹
{
fa->L_child=new BT;
fa->L_child->data=num;
fa->L_child->L_child=NULL;
fa->L_child->R_child=NULL;
}
else add_sort(fa->L_child,num);//遍歷左子樹 ，搜尋空位
}
else if(fa->R_child==NULL)//輸入大於根結點，右子樹為空，新建
{
fa->R_child=new BT;
fa->R_child->data=num;
fa->R_child->L_child=NULL;
fa->R_child->R_child=NULL;
}
else add_sort(fa->R_child,num);//遍歷右子樹，搜尋空位
}
void BT_printf(BT *fa)//中序遍歷
{
if(fa->L_child)BT_printf(fa->L_child);
printf("%d ",fa->data);
if(fa->R_child)BT_printf(fa->R_child);
}
int main()
{
BT fa;//新建根結點
int i,j;
scanf("%d",&fa.data);
fa.L_child=NULL;
fa.R_child=NULL;
for(i=1;i<10;i++)
{
scanf("%d",&j);
add_sort(&fa,j);//插入新結點
}
BT_printf(&fa);
system("pause");
return 0;
}
這個問題本質上就是個數據結構的問題，所謂排序和查找效率依賴的是演算法和數據結構的配合，你現在定下了鏈表（沒有具體說明的話，這里應該指的是單向鏈敬謹表吧）、數組和二叉樹，這幾個之中，那排序和查找的數據就看用什麼演算法和相應的數據結構配合了~~~
排序演算法中，快速排序是最快的，比較適合用鏈表來處理，但是鏈表的查找是比較慢的（雙向鏈表的話可以加快查找速度）。
數組排序會比較慢，不返稿帶是演算法的問題漏蘆，而是數組的調整因為需要位移，但是數組一旦排號順序後，查找是很快的——折半查找。
二叉數較為平局，排序可以採用堆排序，查找可以建二叉排序樹來找（用B+或B-樹的話可以更快）。
個人看法，不一定對，歡迎拍磚，具體代碼知道演算法了就自己上網找吧。
3. 二叉樹排序演算法實現 急！急！急！
//二叉排序樹（升序），橋陪辯平均性能O(nlogn)
//從根節點開始，小於節點的數放在左子樹，大於等於節點的數放在右子樹
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int a[100],b[100];//定義兩個數字，a是亂序的，b是排序的結果
int bshu=0;
struct Node
{
Node *father,*left,*right; //三個指針，父親，左兒子，右兒子
int value; //每個節點都有一個值
};
Node *root; //定義二叉排序樹的根結點，通常是第一個數字
void add(int value,Node *p) //通過遞歸對樹進行深度優先搜索，確認指定的數字的位置
{
if(p->left==NULL && value<p->value) //如果值比p節點小且p節點沒有左兒子
{
Node *x=new Node; //定義一個新節點
x->father=p;x->left=NULL;x->right=NULL; //這個新節點的父親是p節點
x->value=value;
p->left=x; //p節點的左兒子為這個新節點
return; //遞歸上升，該數字的位置已確認亂帶
}
if(p->right==NULL && value>=p->value) //如果數字大於等於p節點且p節點沒有右兒子
{
Node *x=new Node; //定義一個新節點
x->father=p;x->left=NULL;x->right=NULL; //這個新節點的父親是p節點
x->value=value;
p->right=x; //p節點的右兒子為這個新節點
return; //遞歸上升，該數字的位置已確認
}
//如果p節點不能最終確定該數字的位置
if(value<p->value) //如果該數字小於p節點
{
add(value,p->left); //在p節點的左子樹中尋找位置，查詢p節點的左兒子（遞歸）
return; //最終總會確定該數字的位置，該數字不可能出現在p節點的右子樹，直接遞歸上升
}
if(value>=p->value) //如果該數字大於等於p節點
{
add(value,p->right); //在p節點的右子樹中尋找位置，查詢p節點的右兒子（遞歸）
return; //和上一個retrun相同的作用，此處也可省略return
}
}
void print(Node *p) //通過遞歸對樹進行中序遍歷，左、根、右的順序
{
if(p->left!=NULL) //如果p的左子樹不為空
print(p->敏缺left); //訪問左兒子（遞歸）
b[bshu]=p->value; //訪問完畢後把p節點加入結果數組
bshu++; //數組的元素個數加1
if(p->right!=NULL) //如果p的右子樹不為空
print(p->right); //訪問右兒子（遞歸）
//對該節點所引出的樹的遍歷結束，遞歸上升至p的父節點。
}
int main()
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
bshu=0; //初始化
for(int i=0;i<20;i++)
{
a[i]=rand()%100;
cout<<a[i]<<" "; //生成隨機數並列印原始無序序列
}
cout<<endl;
system("pause");
root=new Node; //為根節點分配內存
root->father=NULL;root->left=NULL;root->right=NULL; //根節點沒有父親，左兒子和右兒子暫
//時為空
root->value=a[0]; //根節點的值是第一個數
for(int i=1;i<20;i++) //把數字一個個加入二叉排序樹
add(a[i],root);
print(root); //在對二叉排序樹中的數字進行中序遍歷，完成排序
for(int i=0;i<bshu;i++)
cout<<b[i]<<" "; //列印排序後的升序數列
cout<<endl;
system("pause");
return 0; //main函數結束
}
//與快速排序一樣，二叉排序樹對有序序列的排序性能較差，為O(n2)，因為有序的數列無法構
//成理想平衡樹，導致一邊走到底的現象
4. java如何創建一顆二叉樹
計算機科學中，二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。
二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的 i -1次方個結點；深度為k的二叉樹至多有2^(k) -1個結點；對任何一棵二叉樹T，如果其終端結點數(即葉子結點數)為n0，度為2的結點數為n2，則n0 = n2 + 1。
樹是由一個或多個結點組成的有限集合，其中：
⒈必有一個特定的稱為根(ROOT)的結點；
二叉樹
⒉剩下的結點被分成n>=0個互不相交的集合T1、T2、......Tn，而且， 這些集合的每一個又都是樹。樹T1、T2、......Tn被稱作根的子樹(Subtree)。
樹的遞歸定義如下：（1）至少有一個結點（稱為根）（2）其它是互不相交的子樹
1.樹的度——也即是寬度，簡單地說，就是結點的分支數。以組成該樹各結點中最大的度作為該樹的度，如上圖的樹，其度為2;樹中度為零的結點稱為葉結點或終端結點。樹中度不為零的結點稱為分枝結點或非終端結點。除根結點外的分枝結點統稱為內部結點。
2.樹的深度——組成該樹各結點的最大層次。
3.森林——指若干棵互不相交的樹的集合，如上圖，去掉根結點A，其原來的二棵子樹T1、T2、T3的集合{T1,T2,T3}就為森林；
4.有序樹——指樹中同層結點從左到右有次序排列，它們之間的次序不能互換，這樣的樹稱為有序樹，否則稱為無序樹。
樹的表示
樹的表示方法有許多，常用的方法是用括弧：先將根結點放入一對圓括弧中，然後把它的子樹由左至右的順序放入括弧中，而對子樹也採用同樣的方法處理；同層子樹與它的根結點用圓括弧括起來，同層子樹之間用逗號隔開，最後用閉括弧括起來。如右圖可寫成如下形式：
二叉樹
(a( b(d,e), c( f( ,g(h,i) ), )))
5. 結合二叉樹的快速排序演算法分析
對 3，9，1，6，5，4，8，2，10，7 進行從小到和悄遲大的快速排序
對於第一次遍歷，如下圖所示：
對應的二叉樹結果是：
那麼經過後幾次遍歷比較可以得到如下二叉樹：
這運灶時我們可以計算一下我們的快速排序演算法進行了多少次比較:
，即每個節點到根結點的距離之和。
由上例可知，快排可視為一個二叉樹構建的過程，那麼這個二叉樹構建的速度就決定了我們快排的效率。可以確定的是，對於同樣的數據元素在不同的原始排列條件下，構建的二叉樹越矮，則排序效率越高。
通過這一理論，我們可以更具體的分析其不同情況下的時間復雜度：
完全二叉樹滿足如下公式：
對於深度為h的完全二叉樹，若為滿二叉樹，比較次數為：
這里的葉子數量m與深度h的關系：
那麼葉子到根的距離d為：
即， ，
由於 為整數，即可認為 ，
而對於完全二叉樹來說，葉子數 ，與內點（帶有葉子節點的頂點）數 的關系為 ，則頂點數
那麼由上述公式可得：
即， ，時間復雜度為： 。
那麼若節點數為n，則：
，即時間復雜度為： 。
由於分割標準的選取概率完全相同，那麼可以得到平均比較次數為：
由於這里的 ，以及
由 ，以及 ，得：
令 ，得：
令 ，得：
令 ，得：
整理得：
由 ，故
則：喚李
即，
綜合來看，快排的時間復雜度最理想狀態與最糟糕狀態分別為 、 ，但是對於一般隨機情況而言時間復雜度仍為 。
6. java構建二叉樹演算法
下面是你第一個問題的解法，是構建了樹以後又把後序輸出的程序。以前寫的，可以把輸出後序的部分刪除，還有檢驗先序中序的輸入是否合法的代碼也可以不要。/*****TreeNode.java*********/public class TreeNode {
char elem;
TreeNode left;
TreeNode right;
}/*******PlantTree.java*********/import java.io.*;
public class PlantTree {
TreeNode root;
public static void main(String[] args) {
PlantTree seed=new PlantTree();
String preorder=null;
String inorder=null;
try {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Please input the preorder");
preorder=br.readLine();
System.out.println("Please input the inorder");
inorder=br.readLine();
} catch (Exception e) {
// TODO: handle exception
}
if(preorder!=null&&seed.checkTree(preorder,inorder)) {
seed.root=new TreeNode();
seed.root.elem=preorder.charAt(0);
seed.makeTree(preorder,inorder,seed.root);
System.out.println("The tree has been planted,the postorder is:");
seed.printPostorder(seed.root);
}
}
void makeTree(String preorder,String inorder,TreeNode root) {
int i=inorder.lastIndexOf(root.elem);
if(i!=0) {//有左子樹
String leftPre=preorder.substring(1, i+1);
String leftIn=inorder.substring(0,i);
TreeNode leftNode=new TreeNode();
leftNode.elem=leftPre.charAt(0);
root.left=leftNode;
makeTree(leftPre,leftIn,leftNode);
}
if(i!=inorder.length()-1) {//有右子樹
String rightPre=preorder.substring(i+1,preorder.length());
String rightIn=inorder.substring(i+1,inorder.length());
TreeNode rightNode=new TreeNode();
rightNode.elem=rightPre.charAt(0);
root.right=rightNode;
makeTree(rightPre,rightIn,rightNode);
}
}
void printPostorder(TreeNode root) {
if(root.left!=null)
printPostorder(root.left);
if(root.right!=null)
printPostorder(root.right);
System.out.print(root.elem);
}
boolean checkTree(String a,String b) {
for(int i=0;i<a.length();i++) {
if(i!=a.lastIndexOf(a.charAt(i))) {
System.out.println("There are same element in the tree");
return false;
}
if(!b.contains(""+a.charAt(i))) {
System.out.println("Invalid input");
return false;
}
}
if(a.length()==b.length())
return true;
return false;
}
}
7. java排序演算法有多少種
演算法和語言無關吧，語言只是把具體的演算法實現出來而已。據我了解的排序演算法11-13種。排序演算法嘛 主要就是個思想而已。不同的演算法時間復雜度不一樣，空間復雜度也不一樣，當然執行的效率也不一樣。當然採用哪種演算法還取決於你要實現什麼樣的功能。就好比說：要同時盡快的找出最大最小，或者盡快的找出最值的位置等等。冒泡排序（bubble sort） — O(n2)
雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n); 需要 O(k) 額外 記憶體
計數排序 (counting sort) — O(n+k); 需要 O(n+k) 額外 記憶體
歸並排序 （merge sort）— O(n log n); 需要 O(n) 額外記憶體
原地歸並排序 — O(n2)
二叉樹排序 （Binary tree sort） — O(n log n); 需要 O(n) 額外記憶體
鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外記憶體
基數排序 （radix sort）— O(n·k); 需要 O(n) 額外記憶體
Gnome sort — O(n2)
Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外記憶體不穩定
選擇排序 （selection sort）— O(n2)
希爾排序 （shell sort）— O(n log n) 如果使用最佳的現在版本
Comb sort — O(n log n)
堆排序 （heapsort）— O(n log n)
Smoothsort — O(n log n)
快速排序 （quicksort）— O(n log n) 期望時間, O(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序
等。
8. java十大演算法
演算法一：快速排序演算法
快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他Ο(n log n) 演算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來。
快速排序使用分治法（Divide and conquer）策略來把一個串列（list）分為兩個子串列（sub-lists）。
演算法步驟：
1 從數列中挑出一個元素，稱為 "基準"（pivot），
2 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作。
3 遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。
遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個演算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。
演算法二：堆排序演算法
堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。
堆排序的平均時間復雜度為Ο(nlogn) 。
演算法步驟：
創建一個堆H[0..n-1]
把堆首（最大值）和堆尾互換
3. 把堆的尺寸縮小1，並調用shift_down(0),目的是把新的數組頂端數據調整到相應位置
4. 重復步驟2，直到堆的尺寸為1
演算法三：歸並排序
歸並排序（Merge sort，台灣譯作：合並排序）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
演算法步驟：
1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列
2. 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置
4. 重復步驟3直到某一指針達到序列尾
5. 將另一序列剩下的所有元素
9. 二叉樹和堆排序到底有什麼關系啊請形象點描述，最好有圖啦！
堆排序是一種選擇排序。是不穩定的排序隱敬埋灶螞方法。時間復雜度為O(nlog2n)。特點是在排序過程中，將排序數組看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親節點和稿腔孩子節點之間的內在關系，在當前無序區中選擇關鍵字最大(或最小)的記錄。
其基本思想是
1、將要排序的數組創建為一個大根堆。大根堆的堆頂元素就是這個堆中最大的元素。
2、將大根堆的堆頂元素和無序區最後一個元素交換，並將無序區最後一個位置例入有序區，然後將新的無序區調整為大根堆。
3、重復操作，無序區在遞減，有序區在遞增。
初始時，整個數組為無序區，第一次交換後無序區減一，有序區增一。
每一次交換，都是大根堆的堆頂元素插入有序區，所以有序區保持是有序的。
P.S.
大根堆和小根堆
堆：是一顆完全二叉樹。
大根堆：所有節點的子節點比其自身小的堆
小根堆：所有節點的子節點比其自身大的堆
10. java 如何對對象進行排序
糾正幾點錯誤：
首先TreeSet就是一個二叉樹排序容器，由用戶定義對象比較規則，然後介面回調進行排序，也就是說當對象在add到容器後實際上已經按照你定義的排序規則排序完畢了，所以你也沒有必要再單獨寫一個排序方塵亂法。
如果你想單獨寫一個排序演算法，傳送TreeSet()這樣已經排序完畢的容器當然是多此一舉的。 你可以用List保存你的對象，這樣容器保存的就是原始的對象集合(按add()的先後順序排序)，這樣才能真正發揮排序方法的功能.
其次，你的冒泡排序演算法是按照價格從小到大的，而你add對象的時候就是從小到大的，所以一直沒有滿足if(iArr[j].price > iArr[j+1].price) { 這個條件，可以把>號改成<號，或者打亂add的順粗好序，這樣就能看派凳檔出效果。
另外從容器內取元素應該用循環，而不應該寫死。你應該知道，所以程序我也沒修改~
下面的程序在原作上面稍微修改了一下，自己可以比較一下區別
package cn.com.csuinfo.Mycollec;
import java.util.ArrayList;
import java.util.List;
public class TestMySort {
public void BubbleSort(List<Car> list) {
Car c1;
Car c2;
Car c3;
Car c4;
c1 = list.get(0);// 將set中的元素一個個取出來，再存入Car數組中
c2 = list.get(1);
c3 = list.get(2);
c4 = list.get(3);
Car[] iArr = { c1, c2, c3, c4 }; // 數組中存放了Car類型的四個對象
Car tmp = null;
int len = list.size();
for (int i = 0; i < len - 1; i++) {// 對數組中的對象按屬性值price的大小進行排序
for (int j = 0; j < len - 1 - i; j++) {
if (iArr[j].price < iArr[j + 1].price) {
tmp = iArr[j];
iArr[j] = iArr[j + 1];
iArr[j + 1] = tmp;
System.out.println("change");// 測試之注意！：程序沒執行到此來？？？
}
}
}
for (Car car : iArr) {
System.out.println(car);
}
}
public static void main(String[] args) {
List<Car> list = new ArrayList<Car>();
Car car1 = new Car("Ford", 164000);
Car car2 = new Car("Honda", 286000);
Car car3 = new Car("Toyota", 410000);
Car car4 = new Car("Benz", 850000);
list.add(car1);
list.add(car2);
list.add(car3);
list.add(car4);
System.out.println("***********************「");
new TestMySort().BubbleSort(list);
}
}