二叉樹排序？你可能沒(méi)聽過(guò)但又很好奇。

先來(lái)了解一下二叉樹

? 接下來(lái)我們才開始講解二叉樹排序

方法如下：

當(dāng)然，如果要掛的那邊有了節(jié)點(diǎn)，那么與那邊子樹的根節(jié)點(diǎn)比較，一直到子樹的根節(jié)點(diǎn)為空節(jié)點(diǎn)，再根據(jù)情況掛點(diǎn)。

那么，他好用不？

最好時(shí)間復(fù)雜度：O(n)

平均時(shí)間復(fù)雜度：O(nlog2n)

最差時(shí)間復(fù)雜度：O(n2)

空間復(fù)雜度：O(n)

與快速排序的效率差不多，可以用！

源碼如下：

1 class BinaryTree{?

2 ? ? class Node{ ? ? ? ? ?//聲明一個(gè)節(jié)點(diǎn)類?

3 ? ? ? ? private Comparable data; ?//節(jié)點(diǎn)的數(shù)據(jù)類型為Comparable?

4 ? ? ? ? private Node left; ? //保存左子樹?

5 ? ? ? ? private Node right; ?//保存右子樹?

6 ? ? ? ? public Node(Comparable data){ ? //構(gòu)造函數(shù)?

7 ? ? ? ? ? ? this.data = data;?

8 ?? ? ? ?}?

9 ? ? ? ? public void addNode(Node newNode){

10 ? ? ? ? ? ? //確定是放在左子樹還是右子樹

11 ? ? ? ? ? ? if(newNode.data.compareTo(this.data)<0){ ?//新節(jié)點(diǎn)值小于當(dāng)前節(jié)點(diǎn)

12 ? ? ? ? ? ? ? ? if(this.left == null){

13 ? ? ? ? ? ? ? ? ? ? this.left = newNode; ?//左子樹為空的話，新節(jié)點(diǎn)設(shè)為左子樹

14 ? ? ? ? ? ? ? ? }else{

15 ? ? ? ? ? ? ? ? ? ? this.left.addNode(newNode); //否則繼續(xù)向下判斷

16 ?? ? ? ? ? ? ? ?}

17 ? ? ? ? ? ? }else{ ?//新節(jié)點(diǎn)的值大于或等于當(dāng)前節(jié)點(diǎn)

18 ? ? ? ? ? ? ? ? if(this.right == null){

19 ? ? ? ? ? ? ? ? ? ? this.right = newNode;

20 ? ? ? ? ? ? ? ? }else{

21 ? ? ? ? ? ? ? ? ? ? this.right.addNode(newNode);

22 ?? ? ? ? ? ? ? ?}

23 ?? ? ? ? ? ?}

24 ?? ? ? ?}

25 ? ? ? ??

26 ? ? ? ? public void printNode(){ ?//采用中序遍歷

27 ? ? ? ? ? ? if(this.left != null){ ? //如果不為空先輸出左子樹

28 ? ? ? ? ? ? ? ? this.left.printNode();

29 ?? ? ? ? ? ?}

30 ? ? ? ? ? ? System.out.print(this.data+"\t"); ?//輸出當(dāng)前根節(jié)點(diǎn)

31 ? ? ? ? ? ? if(this.right != null){ ?//輸出右子樹

32 ? ? ? ? ? ? ? ? this.right.printNode(); ??

33 ?? ? ? ? ? ?}

34 ?? ? ? ?}

35 ?? ?}

36 ? ? private Node root; ? ?//表示根元素

37 ? ??

38 ? ? public void add(Comparable data){ ? ?//向二叉樹中插入元素

39 ? ? ? ? Node newNode = new Node(data);

40 ? ? ? ? if(root == null){ ? //沒(méi)有根節(jié)點(diǎn)

41 ? ? ? ? ? ? root = newNode;

42 ? ? ? ? }else{

43 ? ? ? ? ? ? root.addNode(newNode); //判斷放在左子樹還是右子樹

44 ?? ? ? ?}

45 ?? ?}

46 ? ??

47 ? ? public void print(){

48 ? ? ? ? root.printNode(); ? //根據(jù)根節(jié)點(diǎn)輸出

49 ?? ?}

50 }

51?

52 public class TestBinaryTreeSort {

53 ? ? public static void main(String args[]){

54 ? ? ? ? BinaryTree bt = new BinaryTree();

55 ? ? ? ? bt.add(3);

56 ? ? ? ? bt.add(5);

57 ? ? ? ? bt.add(4);

58 ? ? ? ? bt.add(8);

59 ? ? ? ? bt.add(7);

60 ? ? ? ? bt.add(8);

61 ? ? ? ? bt.add(1);

62 ?? ? ? ?bt.print();

63 ?? ?}

64 }