您的位置:

二叉排序树的java实现,java二叉树排序算法

本文目录一览:

java构建二叉树算法

//******************************************************************************************************//

//*****本程序包括简单的二叉树类的实现和前序,中序,后序,层次遍历二叉树算法,*******//

//******以及确定二叉树的高度,制定对象在树中的所处层次以及将树中的左右***********//

//******孩子节点对换位置,返回叶子节点个数删除叶子节点,并输出所删除的叶子节点**//

//*******************************CopyRight By phoenix*******************************************//

//************************************Jan 12,2008*************************************************//

//****************************************************************************************************//

public class BinTree {

public final static int MAX=40;

private Object data; //数据元数

private BinTree left,right; //指向左,右孩子结点的链

BinTree []elements = new BinTree[MAX];//层次遍历时保存各个节点

int front;//层次遍历时队首

int rear;//层次遍历时队尾

public BinTree()

{

}

public BinTree(Object data)

{ //构造有值结点

this.data = data;

left = right = null;

}

public BinTree(Object data,BinTree left,BinTree right)

{ //构造有值结点

this.data = data;

this.left = left;

this.right = right;

}

public String toString()

{

return data.toString();

}//前序遍历二叉树

public static void preOrder(BinTree parent){

if(parent == null)

return;

System.out.print(parent.data+" ");

preOrder(parent.left);

preOrder(parent.right);

}//中序遍历二叉树

public void inOrder(BinTree parent){

if(parent == null)

return;

inOrder(parent.left);

System.out.print(parent.data+" ");

inOrder(parent.right);

}//后序遍历二叉树

public void postOrder(BinTree parent){

if(parent == null)

return;

postOrder(parent.left);

postOrder(parent.right);

System.out.print(parent.data+" ");

}// 层次遍历二叉树

public void LayerOrder(BinTree parent)

{

elements[0]=parent;

front=0;rear=1;

while(frontrear)

{

try

{

if(elements[front].data!=null)

{

System.out.print(elements[front].data + " ");

if(elements[front].left!=null)

elements[rear++]=elements[front].left;

if(elements[front].right!=null)

elements[rear++]=elements[front].right;

front++;

}

}catch(Exception e){break;}

}

}//返回树的叶节点个数

public int leaves()

{

if(this == null)

return 0;

if(left == nullright == null)

return 1;

return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());

}//结果返回树的高度

public int height()

{

int heightOfTree;

if(this == null)

return -1;

int leftHeight = (left == null ? 0 : left.height());

int rightHeight = (right == null ? 0 : right.height());

heightOfTree = leftHeightrightHeight?rightHeight:leftHeight;

return 1 + heightOfTree;

}

//如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层

public int level(Object object)

{

int levelInTree;

if(this == null)

return -1;

if(object == data)

return 1;//规定根节点为第一层

int leftLevel = (left == null?-1:left.level(object));

int rightLevel = (right == null?-1:right.level(object));

if(leftLevel0rightLevel0)

return -1;

levelInTree = leftLevelrightLevel?rightLevel:leftLevel;

return 1+levelInTree;

}

//将树中的每个节点的孩子对换位置

public void reflect()

{

if(this == null)

return;

if(left != null)

left.reflect();

if(right != null)

right.reflect();

BinTree temp = left;

left = right;

right = temp;

}// 将树中的所有节点移走,并输出移走的节点

public void defoliate()

{

String innerNode = "";

if(this == null)

return;

//若本节点是叶节点,则将其移走

if(left==nullright == null)

{

System.out.print(this + " ");

data = null;

return;

}

//移走左子树若其存在

if(left!=null){

left.defoliate();

left = null;

}

//移走本节点,放在中间表示中跟移走...

innerNode += this + " ";

data = null;

//移走右子树若其存在

if(right!=null){

right.defoliate();

right = null;

}

}

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

BinTree e = new BinTree("E");

BinTree g = new BinTree("G");

BinTree h = new BinTree("H");

BinTree i = new BinTree("I");

BinTree d = new BinTree("D",null,g);

BinTree f = new BinTree("F",h,i);

BinTree b = new BinTree("B",d,e);

BinTree c = new BinTree("C",f,null);

BinTree tree = new BinTree("A",b,c);

System.out.println("前序遍历二叉树结果: ");

tree.preOrder(tree);

System.out.println();

System.out.println("中序遍历二叉树结果: ");

tree.inOrder(tree);

System.out.println();

System.out.println("后序遍历二叉树结果: ");

tree.postOrder(tree);

System.out.println();

System.out.println("层次遍历二叉树结果: ");

tree.LayerOrder(tree);

System.out.println();

System.out.println("F所在的层次: "+tree.level("F"));

System.out.println("这棵二叉树的高度: "+tree.height());

System.out.println("--------------------------------------");

tree.reflect();

System.out.println("交换每个节点的孩子节点后......");

System.out.println("前序遍历二叉树结果: ");

tree.preOrder(tree);

System.out.println();

System.out.println("中序遍历二叉树结果: ");

tree.inOrder(tree);

System.out.println();

System.out.println("后序遍历二叉树结果: ");

tree.postOrder(tree);

System.out.println();

System.out.println("层次遍历二叉树结果: ");

tree.LayerOrder(tree);

System.out.println();

System.out.println("F所在的层次: "+tree.level("F"));

System.out.println("这棵二叉树的高度: "+tree.height());

}

二叉排序树(BST) Java实现

public class NodeE {

int key; // data used as key value

E data; // other data

NodeE leftChild; // this node's left child

NodeE rightChild; // this node's right child

public Node(int key, E o) {

this.key = key;

this.data = o;

}

public void displayNode() {

System.out.printf("%d, %s\n", key, data.toString());

}

}

===============================================================

package net.acoder.adt.tree;

public class TreeE {

private NodeE root;

public Tree(NodeE root) {

if (root == null) {

throw new NullPointerException("root can't be null");

}

this.root = root;

}

public Tree(int key, E o) {

this(new NodeE(key, o));

}

public NodeE getRoot() {

return root;

}

/**

* find a node by its key

*

* @param key

* @return

*/

public NodeE find(int key) {

NodeE current = root;

while (current.key != key) {

if (key current.key) {

current = root.leftChild;

} else {

current = root.rightChild;

}

if (current == null) {

return null;

}

}

return current;

}

/**

* insert a node to this tree

*

* @param key

* @param o

*/

public void insert(int key, E o) {

NodeE aNode = new NodeE(key, o);

if (root == null) {

this.root = aNode;

return;

}

NodeE current = root;

NodeE parent = root;

while (true) {

parent = current;

if (key parent.key) {

current = parent.leftChild;

if (current == null) {

parent.leftChild = aNode;

return;

}

} else {

current = parent.rightChild;

if (current == null) {

parent.rightChild = aNode;

return;

}

}

}

}

public boolean delete(int key) {

NodeE current = root;

NodeE parent = root;

boolean isLeftChild = true;

// search for node

while (current.key != key) {

parent = current;

if (key current.key) {

isLeftChild = true;

current = current.leftChild;

} else {

isLeftChild = false;

current = current.rightChild;

}

if (current == null) {

return false;

}

}

// if no children, simply delete it

if (current.leftChild == null current.rightChild == null) {

if (current == parent) {

root = null;

} else if (isLeftChild == true) {

parent.leftChild = null;

} else if (isLeftChild == false) {

parent.rightChild = null;

}

return true;

}

// if no left children, replace with right subtree

if (current.leftChild == null) {

if (current == root) {

root = current.rightChild;

} else if (isLeftChild) {

parent.leftChild = current.rightChild;

} else if (!isLeftChild) {

parent.leftChild = current.rightChild;

}

return true;

}

// if no right children, replace with left subtree

if (current.rightChild == null) {

if (current == root) {

root = current.leftChild;

} else if (isLeftChild) {

parent.leftChild = current.leftChild;

} else if (!isLeftChild) {

parent.leftChild = current.leftChild;

}

return true;

}

// get successor of node to delete

NodeE successor = getSuccessor(current);

if (current == root) {

current = successor;

} else if (isLeftChild) {

parent.leftChild = successor;

} else {

parent.rightChild = successor;

}

successor.leftChild = current.leftChild;

return true;

}

private NodeE getSuccessor(NodeE delNode) {

NodeE successorParent = delNode;

NodeE successor = delNode;

NodeE current = delNode.rightChild;

while (current != null) {

successorParent = successor;

successor = current;

current = current.leftChild;

}

if (successor != delNode.rightChild) {

successorParent.leftChild = successor.rightChild;

successor.rightChild = delNode.rightChild;

}

return successor;

}

public void inOrder(NodeE aNode) {

if (aNode != null) {

inOrder(aNode.leftChild);

aNode.displayNode();

inOrder(aNode.rightChild);

}

}

public void preOrder(NodeE aNode) {

if (aNode != null) {

aNode.displayNode();

inOrder(aNode.leftChild);

inOrder(aNode.rightChild);

}

}

public void backOrder(NodeE aNode) {

if (aNode != null) {

inOrder(aNode.leftChild);

inOrder(aNode.rightChild);

aNode.displayNode();

}

}

public NodeE minimum() {

NodeE current = this.root;

NodeE result = null;

while (current != null) {

result = current;

current = current.leftChild;

}

return result;

}

public NodeE maximum() {

NodeE current = this.root;

NodeE result = null;

while (current != null) {

result = current;

current = current.rightChild;

}

return result;

}

}

以前的代码, 记得没写完, 好像就是BST

用java怎么构造一个二叉树呢?

java构造二叉树,可以通过链表来构造,如下代码:

public class BinTree {

public final static int MAX=40;

BinTree []elements = new BinTree[MAX];//层次遍历时保存各个节点

    int front;//层次遍历时队首

    int rear;//层次遍历时队尾

private Object data; //数据元数

private BinTree left,right; //指向左,右孩子结点的链

public BinTree()

{

}

public BinTree(Object data)

{ //构造有值结点

   this.data = data;

   left = right = null;

}

public BinTree(Object data,BinTree left,BinTree right)

{ //构造有值结点

   this.data = data;

   this.left = left;

   this.right = right;

}

public String toString()

{

   return data.toString();

}

//前序遍历二叉树

public static void preOrder(BinTree parent){ 

     if(parent == null)

      return;

     System.out.print(parent.data+" ");

     preOrder(parent.left);

     preOrder(parent.right);

}

//中序遍历二叉树

public void inOrder(BinTree parent){

   if(parent == null)

      return;

   inOrder(parent.left);

   System.out.print(parent.data+" ");

     inOrder(parent.right);

}

//后序遍历二叉树

public void postOrder(BinTree parent){

   if(parent == null)

    return;

   postOrder(parent.left);

   postOrder(parent.right);

   System.out.print(parent.data+" ");

}

// 层次遍历二叉树 

public void LayerOrder(BinTree parent)

     elements[0]=parent;

     front=0;rear=1;

   while(frontrear)

   {

    try

    {

        if(elements[front].data!=null)

        {

           System.out.print(elements[front].data + " ");

           if(elements[front].left!=null)

          elements[rear++]=elements[front].left;

           if(elements[front].right!=null)

          elements[rear++]=elements[front].right;

           front++;

        }

    }catch(Exception e){break;}

   }

}

//返回树的叶节点个数

public int leaves()

{

   if(this == null)

    return 0;

   if(left == nullright == null)

    return 1;

   return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());

}

//结果返回树的高度

public int height()

{

   int heightOfTree;

   if(this == null)

    return -1;

   int leftHeight = (left == null ? 0 : left.height());

   int rightHeight = (right == null ? 0 : right.height());

   heightOfTree = leftHeightrightHeight?rightHeight:leftHeight;

   return 1 + heightOfTree;

}

//如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层

public int level(Object object)

{

   int levelInTree;

   if(this == null)

    return -1;

   if(object == data)

    return 1;//规定根节点为第一层

   int leftLevel = (left == null?-1:left.level(object));

   int rightLevel = (right == null?-1:right.level(object));

   if(leftLevel0rightLevel0)

    return -1;

   levelInTree = leftLevelrightLevel?rightLevel:leftLevel;

   return 1+levelInTree;

  

}

//将树中的每个节点的孩子对换位置

public void reflect()

{

   if(this == null)

    return;

   if(left != null)

    left.reflect();

   if(right != null)

    right.reflect();

   BinTree temp = left;

   left = right;

   right = temp;

}

// 将树中的所有节点移走,并输出移走的节点

public void defoliate()

{

   if(this == null)

    return;

   //若本节点是叶节点,则将其移走

   if(left==nullright == null)

   {

    System.out.print(this + " ");

    data = null;

    return;

   }

   //移走左子树若其存在

   if(left!=null){

    left.defoliate();

    left = null;

   }

   //移走本节点,放在中间表示中跟移走...

   String innerNode += this + " ";

   data = null;

   //移走右子树若其存在

   if(right!=null){

    right.defoliate();

    right = null;

   }

}

   /**

* @param args

*/

public static void main(String[] args) {

   // TODO Auto-generated method stub

   BinTree e = new BinTree("E");

   BinTree g = new BinTree("G");

   BinTree h = new BinTree("H");

   BinTree i = new BinTree("I");

   BinTree d = new BinTree("D",null,g);

  

   BinTree f = new BinTree("F",h,i);

   BinTree b = new BinTree("B",d,e);

   BinTree c = new BinTree("C",f,null);

   BinTree tree = new BinTree("A",b,c);

  

        System.out.println("前序遍历二叉树结果: ");

        tree.preOrder(tree);

        System.out.println();

        System.out.println("中序遍历二叉树结果: ");

        tree.inOrder(tree);

        System.out.println();

        System.out.println("后序遍历二叉树结果: ");

        tree.postOrder(tree);

        System.out.println();

      System.out.println("层次遍历二叉树结果: ");

     tree.LayerOrder(tree);

     System.out.println();

        System.out.println("F所在的层次: "+tree.level("F"));

        System.out.println("这棵二叉树的高度: "+tree.height());

         System.out.println("--------------------------------------");

         tree.reflect();

          System.out.println("交换每个节点的孩子节点后......");

          System.out.println("前序遍历二叉树结果: ");

        tree.preOrder(tree);

        System.out.println();

        System.out.println("中序遍历二叉树结果: ");

        tree.inOrder(tree);

        System.out.println();

        System.out.println("后序遍历二叉树结果: ");

        tree.postOrder(tree);

        System.out.println();

      System.out.println("层次遍历二叉树结果: ");

     tree.LayerOrder(tree);

     System.out.println();

        System.out.println("F所在的层次: "+tree.level("F"));

        System.out.println("这棵二叉树的高度: "+tree.height());

}

二叉排序树的插入与查找 求Java大神帮忙

//二叉树结构类    Btree.java

public class Btree {

private int data;

private Btree left;

private Btree right;

public void setData(int data) {

this.data = data;

}

public int getData() {

return data;

}

public void setLeft(Btree btree) {

this.left = btree;

}

public void setRight(Btree btree) {

this.right = btree;

}

public Btree getLeft() {

return left;

}

public Btree getRight() {

return right;

}

public Btree() {

super();

}

}

//工具类,二叉树创建,查找,遍历,排序。都在这了 Tools.java

public class Tools {

public Btree create(int data) {

Btree btree = new Btree();

btree.setData(data);

return btree;

}

public void add(Btree btree, int data) {

if (data  btree.getData()) {

if (btree.getLeft() != null) {

btree = btree.getLeft();

add(btree, data);

} else {

btree.setLeft(create(data));

}

} else {

if (btree.getRight() != null) {

btree = btree.getRight();

add(btree, data);

} else {

btree.setRight(create(data));

}

}

}

//中序遍历

public void midSerch(Btree btree) {

if (btree.getLeft() != null)

midSerch(btree.getLeft());

System.out.print(btree.getData()+" ");

if (btree.getRight() != null)

midSerch(btree.getRight());

}

//二叉树查找

public void find(Btree btree ,int data){

if(btree.getData()data)

{

if(btree.getLeft()==null)

{

System.out.println("没有这种结果,搜索完毕");

return;

}else

find(btree.getLeft(),data);

}else if(btree.getData()==data)

{

System.out.println("查找成功,查找到的数据是"+data);

return;

}else

{

if(btree.getRight()==null){

System.out.println("没有这种结果,搜索完毕");

return;

}

else

find(btree.getRight(),data);

}

}

}

//主类,与注释的自己看  MidSerchBtree.java

public class MidSerchBtree {

public static void main(String args[]) {

Tools tools = new Tools();

int datas[] = { 6, 4, 3, 7, 8, 9, 2, 1, 5,8,9,12,23,45,3,7,5 };

Btree btree = tools.create(datas[0]);

for (int i = 1; i  datas.length; i++) {//第一个初始化插入作为根节点了

tools.add(btree, datas[i]);

}

tools.midSerch(btree);//中根遍历     小的插入左边,大的在右边,所以,中序遍历一遍就是排序

tools.find(btree, 56);

}

}