您的位置:

二叉树java,二叉树java实现

本文目录一览:

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如何创建一颗二叉树

计算机科学中,二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”(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)

),

)))

用java实现二叉树

我有很多个(假设10万个)数据要保存起来,以后还需要从保存的这些数据中检索是否存在某

个数据,(我想说出二叉树的好处,该怎么说呢?那就是说别人的缺点),假如存在数组中,

那么,碰巧要找的数字位于99999那个地方,那查找的速度将很慢,因为要从第1个依次往

后取,取出来后进行比较。平衡二叉树(构建平衡二叉树需要先排序,我们这里就不作考虑

了)可以很好地解决这个问题,但二叉树的遍历(前序,中序,后序)效率要比数组低很多,

public class Node {

public int value;

public Node left;

public Node right;

public void store(intvalue)

right.value=value;

}

else

{

right.store(value);

}

}

}

public boolean find(intvalue)

{

System.out.println("happen" +this.value);

if(value ==this.value)

{

return true;

}

else if(valuethis.value)

{

if(right ==null)returnfalse;

return right.find(value);

}else

{

if(left ==null)returnfalse;

return left.find(value);

}

}

public void preList()

{

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

if(left!=null)left.preList();

if(right!=null) right.preList();

}

public void middleList()

{

if(left!=null)left.preList();

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

if(right!=null)right.preList();

}

public void afterList()

{

if(left!=null)left.preList();

if(right!=null)right.preList();

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

}

public static voidmain(String [] args)

{

int [] data =new int[20];

for(inti=0;idata.length;i++)

{

data[i] = (int)(Math.random()*100)+ 1;

System.out.print(data[i] +",");

}

System.out.println();

Node root = new Node();

root.value = data[0];

for(inti=1;idata.length;i++)

{

root.store(data[i]);

}

root.find(data[19]);

root.preList();

System.out.println();

root.middleList();

System.out.println();

root.afterList();

}

}

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

二叉树的相关操作,包括创建,中序、先序、后序(递归和非递归),其中重点的是java在先序创建二叉树和后序非递归遍历的的实现。

package com.algorithm.tree;

import java.io.File;

import java.io.FileNotFoundException;

import java.util.Queue;

import java.util.Scanner;

import java.util.Stack;

import java.util.concurrent.LinkedBlockingQueue;

public class Tree {

private Node root;

public Tree() {

}

public Tree(Node root) {

this.root = root;

}

//创建二叉树

public void buildTree() {

Scanner scn = null;

try {

scn = new Scanner(new File("input.txt"));

} catch (FileNotFoundException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

root = createTree(root,scn);

}

//先序遍历创建二叉树

private Node createTree(Node node,Scanner scn) {

String temp = scn.next();

if (temp.trim().equals("#")) {

return null;

} else {

node = new Node((T)temp);

node.setLeft(createTree(node.getLeft(), scn));

node.setRight(createTree(node.getRight(), scn));

return node;

}

}

//中序遍历(递归)

public void inOrderTraverse() {

inOrderTraverse(root);

}

public void inOrderTraverse(Node node) {

if (node != null) {

inOrderTraverse(node.getLeft());

System.out.println(node.getValue());

inOrderTraverse(node.getRight());

}

}

//中序遍历(非递归)

public void nrInOrderTraverse() {

StackNode stack = new StackNode();

Node node = root;

while (node != null || !stack.isEmpty()) {

while (node != null) {

stack.push(node);

node = node.getLeft();

}

node = stack.pop();

System.out.println(node.getValue());

node = node.getRight();

}

}

//先序遍历(递归)

public void preOrderTraverse() {

preOrderTraverse(root);

}

public void preOrderTraverse(Node node) {

if (node != null) {

System.out.println(node.getValue());

preOrderTraverse(node.getLeft());

preOrderTraverse(node.getRight());

}

}

//先序遍历(非递归)

public void nrPreOrderTraverse() {

StackNode stack = new StackNode();

Node node = root;

while (node != null || !stack.isEmpty()) {

while (node != null) {

System.out.println(node.getValue());

stack.push(node);

node = node.getLeft();

}

node = stack.pop();

node = node.getRight();

}

}

//后序遍历(递归)

public void postOrderTraverse() {

postOrderTraverse(root);

}

public void postOrderTraverse(Node node) {

if (node != null) {

postOrderTraverse(node.getLeft());

postOrderTraverse(node.getRight());

System.out.println(node.getValue());

}

}

//后续遍历(非递归)

public void nrPostOrderTraverse() {

StackNode stack = new StackNode();

Node node = root;

Node preNode = null;//表示最近一次访问的节点

while (node != null || !stack.isEmpty()) {

while (node != null) {

stack.push(node);

node = node.getLeft();

}

node = stack.peek();

if (node.getRight() == null || node.getRight() == preNode) {

System.out.println(node.getValue());

node = stack.pop();

preNode = node;

node = null;

} else {

node = node.getRight();

}

}

}

//按层次遍历

public void levelTraverse() {

levelTraverse(root);

}

public void levelTraverse(Node node) {

QueueNode queue = new LinkedBlockingQueueNode();

queue.add(node);

while (!queue.isEmpty()) {

Node temp = queue.poll();

if (temp != null) {

System.out.println(temp.getValue());

queue.add(temp.getLeft());

queue.add(temp.getRight());

}

}

}

}

//树的节点

class Node {

private Node left;

private Node right;

private T value;

public Node() {

}

public Node(Node left,Node right,T value) {

this.left = left;

this.right = right;

this.value = value;

}

public Node(T value) {

this(null,null,value);

}

public Node getLeft() {

return left;

}

public void setLeft(Node left) {

this.left = left;

}

public Node getRight() {

return right;

}

public void setRight(Node right) {

this.right = right;

}

public T getValue() {

return value;

}

public void setValue(T value) {

this.value = value;

}

}

测试代码:

package com.algorithm.tree;

public class TreeTest {

/**

* @param args

*/

public static void main(String[] args) {

Tree tree = new Tree();

tree.buildTree();

System.out.println("中序遍历");

tree.inOrderTraverse();

tree.nrInOrderTraverse();

System.out.println("后续遍历");

//tree.nrPostOrderTraverse();

tree.postOrderTraverse();

tree.nrPostOrderTraverse();

System.out.println("先序遍历");

tree.preOrderTraverse();

tree.nrPreOrderTraverse();

//

}

}

用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构建二叉树算法

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

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

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

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

//*******************************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());

}