本文目錄一覽：
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);
}
}
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/305221.html