java如何創(chuàng)建一顆二叉樹

計算機科學中，二叉樹是每個結(jié)點最多有兩個子樹的有序樹。通常子樹的根被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。

革吉網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)公司！從網(wǎng)頁設(shè)計、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、響應(yīng)式網(wǎng)站建設(shè)等網(wǎng)站項目制作，到程序開發(fā)，運營維護。創(chuàng)新互聯(lián)公司2013年開創(chuàng)至今到現(xiàn)在10年的時間，我們擁有了豐富的建站經(jīng)驗和運維經(jīng)驗，來保證我們的工作的順利進行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)公司。

二叉樹的每個結(jié)點至多只有二棵子樹(不存在度大于2的結(jié)點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的 i -1次方個結(jié)點；深度為k的二叉樹至多有2^(k) -1個結(jié)點；對任何一棵二叉樹T，如果其終端結(jié)點數(shù)(即葉子結(jié)點數(shù))為n0，度為2的結(jié)點數(shù)為n2，則n0 = n2 + 1。

樹是由一個或多個結(jié)點組成的有限集合，其中：

⒈必有一個特定的稱為根(ROOT)的結(jié)點；

二叉樹

⒉剩下的結(jié)點被分成n=0個互不相交的集合T1、T2、......Tn，而且， 這些集合的每一個又都是樹。樹T1、T2、......Tn被稱作根的子樹(Subtree)。

樹的遞歸定義如下：（1）至少有一個結(jié)點（稱為根）（2）其它是互不相交的子樹

1.樹的度——也即是寬度，簡單地說，就是結(jié)點的分支數(shù)。以組成該樹各結(jié)點中最大的度作為該樹的度，如上圖的樹，其度為2;樹中度為零的結(jié)點稱為葉結(jié)點或終端結(jié)點。樹中度不為零的結(jié)點稱為分枝結(jié)點或非終端結(jié)點。除根結(jié)點外的分枝結(jié)點統(tǒng)稱為內(nèi)部結(jié)點。

2.樹的深度——組成該樹各結(jié)點的最大層次。

3.森林——指若干棵互不相交的樹的集合，如上圖，去掉根結(jié)點A，其原來的二棵子樹T1、T2、T3的集合{T1,T2,T3}就為森林；

4.有序樹——指樹中同層結(jié)點從左到右有次序排列，它們之間的次序不能互換，這樣的樹稱為有序樹，否則稱為無序樹。

樹的表示

樹的表示方法有許多，常用的方法是用括號：先將根結(jié)點放入一對圓括號中，然后把它的子樹由左至右的順序放入括號中，而對子樹也采用同樣的方法處理；同層子樹與它的根結(jié)點用圓括號括起來，同層子樹之間用逗號隔開，最后用閉括號括起來。如右圖可寫成如下形式：

二叉樹

(a( b(d,e), c( f( ,g(h,i) ), )))

java構(gòu)建二叉樹算法

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

//*****本程序包括簡單的二叉樹類的實現(xiàn)和前序,中序,后序,層次遍歷二叉樹算法,*******//

//******以及確定二叉樹的高度,制定對象在樹中的所處層次以及將樹中的左右***********//

//******孩子節(jié)點對換位置,返回葉子節(jié)點個數(shù)刪除葉子節(jié)點,并輸出所刪除的葉子節(jié)點**//

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

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

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

public class BinTree {

public final static int MAX=40;

private Object data; //數(shù)據(jù)元數(shù)

private BinTree left,right; //指向左,右孩子結(jié)點的鏈

BinTree []elements = new BinTree[MAX];//層次遍歷時保存各個節(jié)點

int front;//層次遍歷時隊首

int rear;//層次遍歷時隊尾

public BinTree()

{

}

public BinTree(Object data)

{ //構(gòu)造有值結(jié)點

this.data = data;

left = right = null;

}

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

{ //構(gòu)造有值結(jié)點

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;}

}

}//返回樹的葉節(jié)點個數(shù)

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

}//結(jié)果返回樹的高度

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;

}

//如果對象不在樹中,結(jié)果返回-1;否則結(jié)果返回該對象在樹中所處的層次,規(guī)定根節(jié)點為第一層

public int level(Object object)

{

int levelInTree;

if(this == null)

return -1;

if(object == data)

return 1;//規(guī)定根節(jié)點為第一層

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;

}

//將樹中的每個節(jié)點的孩子對換位置

public void reflect()

{

if(this == null)

return;

if(left != null)

left.reflect();

if(right != null)

right.reflect();

BinTree temp = left;

left = right;

right = temp;

}// 將樹中的所有節(jié)點移走,并輸出移走的節(jié)點

public void defoliate()

{

String innerNode = "";

if(this == null)

return;

//若本節(jié)點是葉節(jié)點，則將其移走

if(left==nullright == null)

{

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

data = null;

return;

}

//移走左子樹若其存在

if(left!=null){

left.defoliate();

left = null;

}

//移走本節(jié)點，放在中間表示中跟移走...

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("前序遍歷二叉樹結(jié)果: ");

tree.preOrder(tree);

System.out.println();

System.out.println("中序遍歷二叉樹結(jié)果: ");

tree.inOrder(tree);

System.out.println();

System.out.println("后序遍歷二叉樹結(jié)果: ");

tree.postOrder(tree);

System.out.println();

System.out.println("層次遍歷二叉樹結(jié)果: ");

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("交換每個節(jié)點的孩子節(jié)點后......");

System.out.println("前序遍歷二叉樹結(jié)果: ");

tree.preOrder(tree);

System.out.println();

System.out.println("中序遍歷二叉樹結(jié)果: ");

tree.inOrder(tree);

System.out.println();

System.out.println("后序遍歷二叉樹結(jié)果: ");

tree.postOrder(tree);

System.out.println();

System.out.println("層次遍歷二叉樹結(jié)果: ");

tree.LayerOrder(tree);

System.out.println();

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

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

}

建立一個二叉樹，附帶查詢代碼，JAVA代碼

import java.util.ArrayList;

// 樹的一個節(jié)點

class TreeNode {

Object _value = null; // 他的值

TreeNode _parent = null; // 他的父節(jié)點，根節(jié)點沒有PARENT

ArrayList _childList = new ArrayList(); // 他的孩子節(jié)點

public TreeNode( Object value, TreeNode parent ){

this._parent = parent;

this._value = value;

}

public TreeNode getParent(){

return _parent;

}

public String toString() {

return _value.toString();

}

}

public class Tree {

// 給出寬度優(yōu)先遍歷的值數(shù)組，構(gòu)建出一棵多叉樹

// null 值表示一個層次的結(jié)束

// "|" 表示一個層次中一個父親節(jié)點的孩子輸入結(jié)束

// 如：給定下面的值數(shù)組：

// { "root", null, "left", "right", null }

// 則構(gòu)建出一個根節(jié)點，帶有兩個孩子("left","right")的樹

public Tree( Object[] values ){

// 創(chuàng)建根

_root = new TreeNode( values[0], null );

// 創(chuàng)建下面的子節(jié)點

TreeNode currentParent = _root; // 用于待創(chuàng)建節(jié)點的父親

//TreeNode nextParent = null;

int currentChildIndex = 0; // 表示 currentParent 是他的父親的第幾個兒子

//TreeNode lastNode = null; // 最后一個創(chuàng)建出來的TreeNode，用于找到他的父親

for ( int i = 2; i values.length; i++ ){

// 如果null ,表示下一個節(jié)點的父親是當前節(jié)點的父親的第一個孩子節(jié)點

if ( values[i] == null ){

currentParent = (TreeNode)currentParent._childList.get(0);

currentChildIndex = 0;

continue;

}

// 表示一個父節(jié)點的所有孩子輸入完畢

if ( values[i].equals("|") ){

if ( currentChildIndex+1 currentParent._childList.size() ){

currentChildIndex++;

currentParent = (TreeNode)currentParent._parent._childList.get(currentChildIndex);

}

continue;

}

TreeNode child = createChildNode( currentParent, values[i] );

}

}

TreeNode _root = null;

public TreeNode getRoot(){

return _root;

}

/**

// 按寬度優(yōu)先遍歷，打印出parent子樹所有的節(jié)點

private void printSteps( TreeNode parent, int currentDepth ){

for ( int i = 0; i parent._childList.size(); i++ ){

TreeNode child = (TreeNode)parent._childList.get(i);

System.out.println(currentDepth+":"+child);

}

if ( parent._childList.size() != 0 ) System.out.println(""+null);// 為了避免葉子節(jié)點也會打印null

//打印 parent 同層的節(jié)點的孩子

if ( parent._parent != null ){ // 不是root

int i = 1;

while ( i parent._parent._childList.size() ){// parent 的父親還有孩子

TreeNode current = (TreeNode)parent._parent._childList.get(i);

printSteps( current, currentDepth );

i++;

}

}

// 遞歸調(diào)用，打印所有節(jié)點

for ( int i = 0; i parent._childList.size(); i++ ){

TreeNode child = (TreeNode)parent._childList.get(i);

printSteps( child, currentDepth+1 );

}

}

// 按寬度優(yōu)先遍歷，打印出parent子樹所有的節(jié)點

public void printSteps(){

System.out.println(""+_root);

System.out.println(""+null);

printSteps(_root, 1 );

}**/

// 將給定的值做為 parent 的孩子，構(gòu)建節(jié)點

private TreeNode createChildNode( TreeNode parent, Object value ){

TreeNode child = new TreeNode( value , parent );

parent._childList.add( child );

return child;

}

public static void main(String[] args) {

Tree tree = new Tree( new Object[]{ "root", null,

"left", "right", null,

"l1","l2","l3", "|", "r1","r2",null } );

//tree.printSteps();

System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(0) );

System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(1) );

System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(2) );

System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(0) );

System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(1) );

}

}

java：二叉樹添加和查詢方法

package arrays.myArray;

public class BinaryTree {

private Node root;

// 添加數(shù)據(jù)

public void add(int data) {

// 遞歸調(diào)用

if (null == root)

root = new Node(data, null, null);

else

addTree(root, data);

}

private void addTree(Node rootNode, int data) {

// 添加到左邊

if (rootNode.data data) {

if (rootNode.left == null)

rootNode.left = new Node(data, null, null);

else

addTree(rootNode.left, data);

} else {

// 添加到右邊

if (rootNode.right == null)

rootNode.right = new Node(data, null, null);

else

addTree(rootNode.right, data);

}

}

// 查詢數(shù)據(jù)

public void show() {

showTree(root);

}

private void showTree(Node node) {

if (node.left != null) {

showTree(node.left);

}

System.out.println(node.data);

if (node.right != null) {

showTree(node.right);

}

}

}

class Node {

int data;

Node left;

Node right;

public Node(int data, Node left, Node right) {

this.data = data;

this.left = left;

this.right = right;

}

}

用JAVA寫二叉樹

/**

* [Tree2.java] Create on 2008-10-20 下午03:03:24

* Copyright (c) 2008 by iTrusChina.

*/

/**

* @author WangXuanmin

* @version 0.10

*/

public class Tree2Bef {

private StringBuffer bef=new StringBuffer();

//傳入中序遍歷和后序遍歷,返回前序遍歷字串

public String getBef(String mid, String beh) {

//若節(jié)點存在則向bef中添加該節(jié)點,繼續(xù)查詢該節(jié)點的左子樹和右子樹

if (root(mid, beh) != -1) {

int rootindex=root(mid, beh);

char root=mid.charAt(rootindex);

bef.append(root);

System.out.println(bef.toString());

String mleft, mright;

mleft = mid.substring(0,rootindex);

mright = mid.substring(rootindex+1);

getBef(mleft,beh);

getBef(mright,beh);

}

//所有節(jié)點查詢完畢,返回前序遍歷值

return bef.toString();

}

//從中序遍歷中根據(jù)后序遍歷查找節(jié)點索引值index

private int root(String mid, String beh) {

char[] midc = mid.toCharArray();

char[] behc = beh.toCharArray();

for (int i = behc.length-1; i -1; i--) {

for (int j = 0; j midc.length; j++) {

if (behc[i] == midc[j])

return j;

}

}

return -1;

}

public static void main(String[] args) {

Tree2Bef tree=new Tree2Bef();

String mid="84925163A7B";

String bef="894526AB731";

System.out.println(tree.getBef(mid,bef));

}

}

樹結(jié)構(gòu)如圖:

1

|-------|

2 3

|---| |---|

4 5 6 7

|-| |-|

8 9 A B

當前題目：java二叉樹部分代碼,JAVA 二叉樹
網(wǎng)站鏈接：http://chinadenli.net/article48/hesghp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制網(wǎng)站、手機網(wǎng)站建設(shè)、品牌網(wǎng)站建設(shè)、小程序開發(fā)、定制開發(fā)、Google

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)