二叉樹java,二叉樹java列印中根

本文目錄一覽：

• 1、java 由字元串構成的二叉樹
• 2、java實現二叉樹層次遍歷
• 3、java中把數組以二叉樹形式列印出來
• 4、java構建二叉樹演算法
• 5、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實現二叉樹層次遍歷

import java.util.ArrayList;

public class TreeNode {

private TreeNode leftNode;

private TreeNode rightNode;

private String nodeName;

public TreeNode getLeftNode() {

return leftNode;

}

public void setLeftNode(TreeNode leftNode) {

this.leftNode = leftNode;

}

public TreeNode getRightNode() {

return rightNode;

}

public void setRightNode(TreeNode rightNode) {

this.rightNode = rightNode;

}

public String getNodeName() {

return nodeName;

}

public void setNodeName(String nodeName) {

this.nodeName = nodeName;

}

public static int level=0;

public static void findNodeByLevel(ArrayListTreeNode nodes){

if(nodes==null||nodes.size()==0){

return ;

}

level++;

ArrayListTreeNode temp = new ArrayList();

for(TreeNode node:nodes){

System.out.println(“第”+level+”層:”+node.getNodeName());

if(node.getLeftNode()!=null){

temp.add(node.getLeftNode());

}

if(node.getRightNode()!=null){

temp.add(node.getRightNode());

}

}

nodes.removeAll(nodes);

findNodeByLevel(temp);

}

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

TreeNode root = new TreeNode();

root.setNodeName(“root”);

TreeNode node1 = new TreeNode();

node1.setNodeName(“node1”);

TreeNode node3 = new TreeNode();

node3.setNodeName(“node3”);

TreeNode node7 = new TreeNode();

node7.setNodeName(“node7”);

TreeNode node8 = new TreeNode();

node8.setNodeName(“node8”);

TreeNode node4 = new TreeNode();

node4.setNodeName(“node4”);

TreeNode node2 = new TreeNode();

node2.setNodeName(“node2”);

TreeNode node5 = new TreeNode();

node5.setNodeName(“node5”);

TreeNode node6 = new TreeNode();

node6.setNodeName(“node6”);

root.setLeftNode(node1);

node1.setLeftNode(node3);

node3.setLeftNode(node7);

node3.setRightNode(node8);

node1.setRightNode(node4);

root.setRightNode(node2);

node2.setLeftNode(node5);

node2.setRightNode(node6);

ArrayListTreeNode nodes = new ArrayListTreeNode();

nodes.add(root);

findNodeByLevel(nodes);

}

}

java中把數組以二叉樹形式列印出來

你說的意思應該是用數組的方式存儲二叉樹，這需要利用到完全二叉樹的性質，

,完全二叉樹通常採用數組而不是鏈表存儲,其存儲結構如下:

var

tree:array[1..n]of

longint;{n:integer;n=1}

對於tree[i]，有如下特點：

（1）若i為奇數且i1，那麼tree的左兄弟為tree[i-1]；

（2）若i為偶數且in，那麼tree的右兄弟為tree[i+1]；

（3）若i1，tree的雙親為tree[i

div

2]；

（4）若2*i=n，那麼tree的左孩子為tree[2*i]；若2*i+1=n，那麼tree的右孩子為tree[2*i+1]；

（5）若in

div

2,那麼tree[i]為葉子結點（對應於（3））；

（6）若i(n-1)

div

2.那麼tree[i]必有兩個孩子（對應於（4））。

（7）滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。

完全二叉樹第i層至多有2^（i-1）個節點，共i層的完全二叉樹最多有2^i-1個節點。

代碼簡單，網上很多，不懂也可以問我

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

}

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)

),

)))