二叉樹排序java

① java寫的關於二叉排序樹的刪除操作的問題

package ggg;

import java.math.BigDecimal;
import java.util.Scanner;
import java.util.Random;
import java.util.Stack;

/**
* 二叉排序樹（又稱二叉查找樹）
* （1）可以是一顆空樹
* （2）若左子樹不空，則左子樹上所有的結點的值均小於她的根節點的值
* （3）若右子樹不空，則右子樹上所有的結點的值均大於她的根節點的值
* （4）左、右子樹也分別為二叉排序樹
*
*
* 性能分析：
* 查找性能：
* 含有n個結點的二叉排序樹的平均查找長度和樹的形態有關，
* （最壞情況）當先後插入的關鍵字有序時，構成的二叉排序樹蛻變為單枝樹。查找性能為O(n)
* （最好情況）二叉排序樹的形態和折半查找的判定樹相同，其平均查找長度和log2(n)成正比
*
*
* 插入、刪除性能：
* 插入、刪除操作間復雜度都O(log(n))級的，
* 即經過O(log(n))時間搜索到了需插入刪除節點位置和刪除節點的位置
* 經O(1)級的時間直接插入和刪除
* 與順序表相比，比序順序表插入刪除O(n)(查找時間O(log(n))移動節點時間O(n))要快
* 與無序順序表插入時間O(1)，刪除時間O(n)相比，因為是有序的，所查找速度要快很多
*
*
*
* 作者：小菜鳥
* 創建時間：2014-08-17
*
*/

public class BinarySortTree {

private Node root = null;

/**查找二叉排序樹中是否有key值*/
public boolean searchBST(int key){
Node current = root;
while(current != null){
if(key == current.getValue())
return true;
else if(key < current.getValue())
current = current.getLeft();
else
current = current.getRight();
}
return false;
}

/**向二叉排序樹中插入結點*/
public void insertBST(int key){
Node p = root;
/**記錄查找結點的前一個結點*/
Node prev = null;
/**一直查找下去，直到到達滿足條件的結點位置*/
while(p != null){
prev = p;
if(key < p.getValue())
p = p.getLeft();
else if(key > p.getValue())
p = p.getRight();
else
return;
}
/**prve是要安放結點的父節點，根據結點值得大小，放在相應的位置*/
if(root == null)
root = new Node(key);
else if(key < prev.getValue())
prev.setLeft(new Node(key));
else prev.setRight(new Node(key));
}

/**
* 刪除二叉排序樹中的結點
* 分為三種情況：（刪除結點為*p ，其父結點為*f）
* （1）要刪除的*p結點是葉子結點，只需要修改它的雙親結點的指針為空
* （2）若*p只有左子樹或者只有右子樹，直接讓左子樹/右子樹代替*p
* （3）若*p既有左子樹，又有右子樹
* 用p左子樹中最大的那個值（即最右端S）代替P，刪除s，重接其左子樹
* */
public void deleteBST(int key){
deleteBST(root, key);
}
private boolean deleteBST(Node node, int key) {
if(node == null) return false;
else{
if(key == node.getValue()){
return delete(node);
}
else if(key < node.getValue()){
return deleteBST(node.getLeft(), key);
}
else{
return deleteBST(node.getRight(), key);
}
}
}

private boolean delete(Node node) {
Node temp = null;
/**右子樹空，只需要重接它的左子樹
* 如果是葉子結點，在這里也把葉子結點刪除了
* */
if(node.getRight() == null){
temp = node;
node = node.getLeft();
}
/**左子樹空， 重接它的右子樹*/
else if(node.getLeft() == null){
temp = node;
node = node.getRight();
}
/**左右子樹均不為空*/
else{
temp = node;
Node s = node;
/**轉向左子樹，然後向右走到「盡頭」*/
s = s.getLeft();
while(s.getRight() != null){
temp = s;
s = s.getRight();
}
node.setValue(s.getValue());
if(temp != node){
temp.setRight(s.getLeft());
}
else{
temp.setLeft(s.getLeft());
}
}
return true;
}

/**中序非遞歸遍歷二叉樹
* 獲得有序序列
* */
public void nrInOrderTraverse(){
Stack<Node> stack = new Stack<Node>();
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 static void main(String[] args){
BinarySortTree bst = new BinarySortTree();
/**構建的二叉樹沒有相同元素*/
int[] num = {4,7,2,1,10,6,9,3,8,11,2, 0, -2};
for(int i = 0; i < num.length; i++){
bst.insertBST(num[i]);
}
bst.nrInOrderTraverse();
System.out.println(bst.searchBST(10));
bst.deleteBST(2);
bst.nrInOrderTraverse();
}

/**二叉樹的結點定義*/
public class Node{
private int value;
private Node left;
private Node right;

public Node(){
}
public Node(Node left, Node right, int value){
this.left = left;
this.right = right;
this.value = value;
}
public Node(int value){
this(null, null, value);
}

public Node getLeft(){
return this.left;
}
public void setLeft(Node left){
this.left = left;
}
public Node getRight(){
return this.right;
}
public void setRight(Node right){
this.right = right;
}
public int getValue(){
return this.value;
}
public void setValue(int value){
this.value = value;
}
}

}

② 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實現與幾種遍歷

二叉樹的定義

二叉樹(binary tree)是結點的有限集合，這個集合或者空，或者由一個根及兩個互不相交的稱為這個根的左子樹或右子樹構成.

從定義可以看出，二叉樹包括：1.空樹 2.只有一個根節點 3.只有左子樹 4.只有右子樹 5.左右子樹都存在 有且僅有這5種表現形式

二叉樹的遍歷分為三種：前序遍歷 中序遍歷 後序遍歷

• 前序遍歷：按照「根左右」,先遍歷根節點，再遍歷左子樹 ，再遍歷右子樹

• 中序遍歷：按照「左根右「,先遍歷左子樹，再遍歷根節點，最後遍歷右子樹

• 後續遍歷：按照「左右根」，先遍歷左子樹，再遍歷右子樹，最後遍歷根節點

其中前，後，中指的是每次遍歷時候的根節點被遍歷的順序

具體實現看下圖：

④ 怎樣使用java對二叉樹進行層次遍歷

publicclassBinaryTree{

intdata;//根節點數據
BinaryTreeleft;//左子樹
BinaryTreeright;//右子樹

publicBinaryTree(intdata)//實例化二叉樹類
{
this.data=data;
left=null;
right=null;
}

publicvoidinsert(BinaryTreeroot,intdata){//向二叉樹中插入子節點
if(data>root.data)//二叉樹的左節點都比根節點小
{
if(root.right==null){
root.right=newBinaryTree(data);
}else{
this.insert(root.right,data);
}
}else{//二叉樹的右節點都比根節點大
if(root.left==null){
root.left=newBinaryTree(data);
}else{
this.insert(root.left,data);
}
}
}
}
當建立好二叉樹類後可以創建二叉樹實例，並實現二叉樹的先根遍歷，中根遍歷，後根遍歷，代碼如下：
packagepackage2;
publicclassBinaryTreePreorder{

publicstaticvoidpreOrder(BinaryTreeroot){//先根遍歷
if(root!=null){
System.out.print(root.data+"-");
preOrder(root.left);
preOrder(root.right);
}
}

publicstaticvoidinOrder(BinaryTreeroot){//中根遍歷

if(root!=null){
inOrder(root.left);
System.out.print(root.data+"--");
inOrder(root.right);
}
}

publicstaticvoidpostOrder(BinaryTreeroot){//後根遍歷

if(root!=null){
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data+"---");
}
}

publicstaticvoidmain(String[]str){
int[]array={12,76,35,22,16,48,90,46,9,40};
BinaryTreeroot=newBinaryTree(array[0]);//創建二叉樹
for(inti=1;i<array.length;i++){
root.insert(root,array[i]);//向二叉樹中插入數據
}
System.out.println("先根遍歷：");
preOrder(root);
System.out.println();
System.out.println("中根遍歷：");
inOrder(root);
System.out.println();
System.out.println("後根遍歷：");
postOrder(root);

⑤ JAVA如何將英文字母進行二叉樹排序

如果僅限於java，而且是實際應用，java里有一個叫做TreeSet的東西，是個有序的樹結構。Sring類型的英文字元可在裡面自排序。

如果是考試，應該是靠你如何實現一個類似於TreeSet的東西

⑥ 用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(value>this.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;i<data.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;i<data.length;i++)
{
root.store(data[i]);
}
root.find(data[19]);
root.preList();
System.out.println();
root.middleList();
System.out.println();
root.afterList();
}
}

⑦ java二叉排序樹，已有代碼，如何調通輸出

你好，很高興回答你的問題。

目前已經有了二叉樹以及二叉樹節點的類。

需要一個main方法，在其中創建節點（通過節點類的構造方法），構建樹（通過樹的構造方法以及insert方法）。可以執行查詢的方法以及展示的方法。

如果有幫助到你，請點擊採納。

⑧ java二叉樹的順序表實現

做了很多年的程序員，覺得什麼樹的設計並不是非常實用。二叉樹有順序存儲，當一個insert大量同時順序自增插入的時候，樹就會失去平衡。樹的一方為了不讓塌陷，會增大樹的高度。性能會非常不好。以上是題外話。分析需求在寫代碼。
import java.util.List;

import java.util.LinkedList;

public class Bintrees {
private int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
private static List<Node> nodeList = null;

private static class Node {
Node leftChild;
Node rightChild;
int data;

Node(int newData) {
leftChild = null;
rightChild = null;
data = newData;
}
}

// 創建二叉樹
public void createBintree() {
nodeList = new LinkedList<Node>();

// 將數組的值轉換為node
for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {
nodeList.add(new Node(array[nodeIndex]));
}

// 對除最後一個父節點按照父節點和孩子節點的數字關系建立二叉樹
for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {
nodeList.get(parentIndex).leftChild = nodeList.get(parentIndex * 2 + 1);
nodeList.get(parentIndex).rightChild = nodeList.get(parentIndex * 2 + 2);
}

// 最後一個父節點
int lastParentIndex = array.length / 2 - 1;

// 左孩子
nodeList.get(lastParentIndex).leftChild = nodeList.get(lastParentIndex * 2 + 1);

// 如果為奇數，建立右孩子
if (array.length % 2 == 1) {
nodeList.get(lastParentIndex).rightChild = nodeList.get(lastParentIndex * 2 + 2);
}
}

// 前序遍歷
public static void preOrderTraverse(Node node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);
}

// 中序遍歷
public static void inOrderTraverse(Node node) {
if (node == null) {
return;
}

inOrderTraverse(node.leftChild);
System.out.print(node.data + " ");
inOrderTraverse(node.rightChild);
}

// 後序遍歷
public static void postOrderTraverse(Node node) {
if (node == null) {
return;
}

postOrderTraverse(node.leftChild);
postOrderTraverse(node.rightChild);
System.out.print(node.data + " ");
}

public static void main(String[] args) {
Bintrees binTree = new Bintrees();
binTree.createBintree();
Node root = nodeList.get(0);

System.out.println("前序遍歷：");
preOrderTraverse(root);
System.out.println();

System.out.println("中序遍歷：");
inOrderTraverse(root);
System.out.println();

System.out.println("後序遍歷：");
postOrderTraverse(root);
}
}

⑨ 如何用java實現二叉樹

import java.util.List;
import java.util.LinkedList;

public class Bintrees {
private int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
private static List<Node> nodeList = null;

private static class Node {
Node leftChild;
Node rightChild;
int data;

Node(int newData) {
leftChild = null;
rightChild = null;
data = newData;
}
}

// 創建二叉樹
public void createBintree() {
nodeList = new LinkedList<Node>();

// 將數組的值轉換為node
for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {
nodeList.add(new Node(array[nodeIndex]));
}

// 對除最後一個父節點按照父節點和孩子節點的數字關系建立二叉樹
for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {
nodeList.get(parentIndex).leftChild = nodeList.get(parentIndex * 2 + 1);
nodeList.get(parentIndex).rightChild = nodeList.get(parentIndex * 2 + 2);
}

// 最後一個父節點
int lastParentIndex = array.length / 2 - 1;

// 左孩子
nodeList.get(lastParentIndex).leftChild = nodeList.get(lastParentIndex * 2 + 1);

// 如果為奇數，建立右孩子
if (array.length % 2 == 1) {
nodeList.get(lastParentIndex).rightChild = nodeList.get(lastParentIndex * 2 + 2);
}
}

// 前序遍歷
public static void preOrderTraverse(Node node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);
}

// 中序遍歷
public static void inOrderTraverse(Node node) {
if (node == null) {
return;
}

inOrderTraverse(node.leftChild);
System.out.print(node.data + " ");
inOrderTraverse(node.rightChild);
}

// 後序遍歷
public static void postOrderTraverse(Node node) {
if (node == null) {
return;
}

postOrderTraverse(node.leftChild);
postOrderTraverse(node.rightChild);
System.out.print(node.data + " ");
}

public static void main(String[] args) {
Bintrees binTree = new Bintrees();
binTree.createBintree();
Node root = nodeList.get(0);

System.out.println("前序遍歷：");
preOrderTraverse(root);
System.out.println();

System.out.println("中序遍歷：");
inOrderTraverse(root);
System.out.println();

System.out.println("後序遍歷：");
postOrderTraverse(root);
}
}

輸出結果：
前序遍歷：
1 2 4 8 9 5 3 6 7
中序遍歷：
8 4 9 2 5 1 6 3 7
後序遍歷：
8 9 4 5 2 6 7 3 1

⑩ 二叉排序樹的插入與查找 求Java大神幫忙

//二叉樹結構類Btree.java
publicclassBtree{
privateintdata;
privateBtreeleft;
privateBtreeright;
publicvoidsetData(intdata){
this.data=data;
}
publicintgetData(){
returndata;
}
publicvoidsetLeft(Btreebtree){
this.left=btree;
}
publicvoidsetRight(Btreebtree){
this.right=btree;
}
publicBtreegetLeft(){
returnleft;
}
publicBtreegetRight(){
returnright;
}
publicBtree(){
super();
}
}
//工具類，二叉樹創建，查找，遍歷，排序。都在這了Tools.java
publicclassTools{
publicBtreecreate(intdata){
Btreebtree=newBtree();
btree.setData(data);
returnbtree;
}
publicvoidadd(Btreebtree,intdata){
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));
}
}
}
//中序遍歷
publicvoidmidSerch(Btreebtree){
if(btree.getLeft()!=null)
midSerch(btree.getLeft());
System.out.print(btree.getData()+"");
if(btree.getRight()!=null)
midSerch(btree.getRight());
}
//二叉樹查找
publicvoidfind(Btreebtree,intdata){
if(btree.getData()>data)
{
if(btree.getLeft()==null)
{
System.out.println("沒有這種結果，搜索完畢");
return;
}else
find(btree.getLeft(),data);
}elseif(btree.getData()==data)
{
System.out.println("查找成功，查找到的數據是"+data);
return;
}else
{
if(btree.getRight()==null){
System.out.println("沒有這種結果，搜索完畢");
return;
}
else
find(btree.getRight(),data);
}
}
}
//主類，與注釋的自己看MidSerchBtree.java
publicclassMidSerchBtree{
publicstaticvoidmain(Stringargs[]){
Toolstools=newTools();
intdatas[]={6,4,3,7,8,9,2,1,5,8,9,12,23,45,3,7,5};
Btreebtree=tools.create(datas[0]);
for(inti=1;i<datas.length;i++){//第一個初始化插入作為根節點了
tools.add(btree,datas[i]);
}
tools.midSerch(btree);//中根遍歷小的插入左邊，大的在右邊，所以，中序遍歷一遍就是排序
tools.find(btree,56);
}
}