利用二叉排序树进行排序

利用二叉排序树进行排序

 1、二叉排序树简要概述

  二叉排序树:BST:(BinarySort(Search)Tree),对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。
注意:如果有相同的值,可以将该节点放在左子节点或右子节点。

 2、二叉排序树图示

对于数据(7,3,10,12,5,1,9),对应的二叉排序树为:

《利用二叉排序树进行排序》

 3、二叉排序树进行排序基本思路

(1)先将要排序的数构建成一个二叉排序树。
(2)对该二叉排序树进行中序遍历即可得到按升序排列的数。

 4、java代码实现

public class test { 
    public static void main(String[] args) { 
        int arr[] = new int[]{ 7, 3, 10, 12, 5, 1, 9};
        BinarySortTree tree = new BinarySortTree();
        //循环的添加结点到二叉排序树
        for (int i = 0; i < arr.length; i++) { 
            tree.add(new Node(arr[i]));
        }
        //中序遍历二叉排序树
        System.out.println("中序遍历二叉排序树:");
        tree.infixOrder();
    }
}

//结点
class Node { 
    int value;
    Node left;
    Node right;

    public Node(int value) { 
        this.value = value;
    }

    public void add(Node node) { 
        if (node == null) { 
            return;
        }
        if (node.value < this.value) { 
            if (this.left == null) { 
                this.left = node;
            } else { 
                this.left.add(node);
            }
        } else { 
            if (this.right == null) { 
                this.right = node;
            } else { 
                this.right.add(node);
            }
        }
    }

    public void infixOrder() { 
        if (this.left != null) { 
            this.left.infixOrder();
        }
        System.out.print(this.toString());
        if (this.right != null) { 
            this.right.infixOrder();
        }
    }

    public String toString() { 
        return value + " ";
    }
}

//二叉排序树
class BinarySortTree { 
    private Node root;

    public void add(Node node) { 
        if (root == null) { 
            root = node;
        } else { 
            root.add(node);
        }
    }

    public void infixOrder() { 
        if (root != null) { 
            root.infixOrder();
        } else { 
            System.out.println("二叉排序树为空!");
        }
    }
}

结果如下:

《利用二叉排序树进行排序》 楠哥——-一心想为IT行业添砖加瓦,却总是面向cv编程的程序员。

  谢谢阅读,无误点赞,有误还望评论区指正。

    原文作者:楠哥学IT
    原文地址: https://blog.csdn.net/ITCSDN_/article/details/108294608
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞