java數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)查找結(jié)點(diǎn)操作，遞歸調(diào)用求詳細(xì)講解

這是先序遍歷樹(shù)的代碼，什么是先序遍歷呢，一種按照根-左子樹(shù)-右子樹(shù)的順序遍歷樹(shù)就是先序遍歷。

我們注重客戶(hù)提出的每個(gè)要求，我們充分考慮每一個(gè)細(xì)節(jié)，我們積極的做好成都做網(wǎng)站、網(wǎng)站制作服務(wù)，我們努力開(kāi)拓更好的視野，通過(guò)不懈的努力，創(chuàng)新互聯(lián)贏得了業(yè)內(nèi)的良好聲譽(yù)，這一切，也不斷的激勵(lì)著我們更好的服務(wù)客戶(hù)。 主要業(yè)務(wù)：網(wǎng)站建設(shè),網(wǎng)站制作,網(wǎng)站設(shè)計(jì),微信小程序開(kāi)發(fā),網(wǎng)站開(kāi)發(fā),技術(shù)開(kāi)發(fā)實(shí)力，DIV+CSS，PHP及ASP，ASP.Net，SQL數(shù)據(jù)庫(kù)的技術(shù)開(kāi)發(fā)工程師。

CBTType TreeFindNode(CBTType treeNode,String data){

CBTType ptr;

if(treeNode==null){//輸入根節(jié)點(diǎn)為空時(shí)

return null;

}else{

if(treeNode.data.equals(data)){//根節(jié)點(diǎn)等于要查找的數(shù)據(jù)時(shí)

return treeNode;

}else{

if((ptr=TreeFindNode(treeNode.left,data))!=null){//從左子樹(shù)查找，為什么可以用TreeFindNode表示呢？

return ptr;

}else if((ptr=TreeFindNode(treeNode.right,data))!=null){//從右子樹(shù)查找

return ptr;

}else{

return null;

}

}

}

}

從左子樹(shù)查找，為什么可以用TreeFindNode表示呢？因?yàn)椋笞訕?shù)也可以按照先序遍歷的順序查找的，所以當(dāng)然可以用TreeFindNode表示，如果你想左子樹(shù)用中序遍歷查找，那么就不可以用TreeFindNode表示。

上述例子的查找過(guò)程：

1 --根（2，4，5）--左（3，6，7）--右

2--根（4）--左（5）--右

4--根

5--根

返回

用java怎么構(gòu)造一個(gè)二叉樹(shù)呢？

java構(gòu)造二叉樹(shù)，可以通過(guò)鏈表來(lái)構(gòu)造，如下代碼：

public?class?BinTree?{

public?final?static?int?MAX=40;

BinTree?[]elements?=?new?BinTree[MAX];//層次遍歷時(shí)保存各個(gè)節(jié)點(diǎn)

int?front;//層次遍歷時(shí)隊(duì)首

int?rear;//層次遍歷時(shí)隊(duì)尾

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

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

public?BinTree()

{

}

public?BinTree(Object?data)

{?//構(gòu)造有值結(jié)點(diǎn)

this.data?=?data;

left?=?right?=?null;

}

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

{?//構(gòu)造有值結(jié)點(diǎn)

this.data?=?data;

this.left?=?left;

this.right?=?right;

}

public?String?toString()

{

return?data.toString();

}

//前序遍歷二叉樹(shù)

public?static?void?preOrder(BinTree?parent){?

if(parent?==?null)

return;

System.out.print(parent.data+"?");

preOrder(parent.left);

preOrder(parent.right);

}

//中序遍歷二叉樹(shù)

public?void?inOrder(BinTree?parent){

if(parent?==?null)

return;

inOrder(parent.left);

System.out.print(parent.data+"?");

inOrder(parent.right);

}

//后序遍歷二叉樹(shù)

public?void?postOrder(BinTree?parent){

if(parent?==?null)

return;

postOrder(parent.left);

postOrder(parent.right);

System.out.print(parent.data+"?");

}

//?層次遍歷二叉樹(shù)?

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

}

}

//返回樹(shù)的葉節(jié)點(diǎn)個(gè)數(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é)果返回樹(shù)的高度

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;

}

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

public?int?level(Object?object)

{

int?levelInTree;

if(this?==?null)

return?-1;

if(object?==?data)

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

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;

}

//將樹(shù)中的每個(gè)節(jié)點(diǎn)的孩子對(duì)換位置

public?void?reflect()

{

if(this?==?null)

return;

if(left?!=?null)

left.reflect();

if(right?!=?null)

right.reflect();

BinTree?temp?=?left;

left?=?right;

right?=?temp;

}

//?將樹(shù)中的所有節(jié)點(diǎn)移走,并輸出移走的節(jié)點(diǎn)

public?void?defoliate()

{

if(this?==?null)

return;

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

if(left==nullright?==?null)

{

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

data?=?null;

return;

}

//移走左子樹(shù)若其存在

if(left!=null){

left.defoliate();

left?=?null;

}

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

String?innerNode?+=?this?+?"?";

data?=?null;

//移走右子樹(shù)若其存在

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

tree.preOrder(tree);

System.out.println();

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

tree.inOrder(tree);

System.out.println();

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

tree.postOrder(tree);

System.out.println();

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

tree.LayerOrder(tree);

System.out.println();

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

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

System.out.println("--------------------------------------");

tree.reflect();

System.out.println("交換每個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn)后......");

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

tree.preOrder(tree);

System.out.println();

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

tree.inOrder(tree);

System.out.println();

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

tree.postOrder(tree);

System.out.println();

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

tree.LayerOrder(tree);

System.out.println();

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

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

}

java 構(gòu)建二叉樹(shù)

首先我想問(wèn)為什么要用LinkedList 來(lái)建立二叉樹(shù)呢? LinkedList 是線性表,

樹(shù)是樹(shù)形的, 似乎不太合適。

其實(shí)也可以用數(shù)組完成，而且效率更高.

關(guān)鍵是我覺(jué)得你這個(gè)輸入本身就是一個(gè)二叉樹(shù)啊，

String input = "ABCDE F G";

節(jié)點(diǎn)編號(hào)從0到8. 層次遍歷的話(huà):

對(duì)于節(jié)點(diǎn)i.

leftChild = input.charAt(2*i+1); //做子樹(shù)

rightChild = input.charAt(2*i+2);//右子樹(shù)

如果你要將帶有節(jié)點(diǎn)信息的樹(shù)存到LinkedList里面, 先建立一個(gè)節(jié)點(diǎn)類(lèi):

class Node{

public char cValue;

public Node leftChild;

public Node rightChild;

public Node(v){

this.cValue = v;

}

}

然后遍歷input,建立各個(gè)節(jié)點(diǎn)對(duì)象.

LinkedList tree = new LinkedList();

for(int i=0;i input.length;i++)

LinkedList.add(new Node(input.charAt(i)));

然后為各個(gè)節(jié)點(diǎn)設(shè)置左右子樹(shù):

for(int i=0;iinput.length;i++){

((Node)tree.get(i)).leftChild = (Node)tree.get(2*i+1);

((Node)tree.get(i)).rightChild = (Node)tree.get(2*i+2);

}

這樣LinkedList 就存儲(chǔ)了整個(gè)二叉樹(shù). 而第0個(gè)元素就是樹(shù)根，思路大體是這樣吧。

用java實(shí)現(xiàn)二叉樹(shù)

我有很多個(gè)(假設(shè)10萬(wàn)個(gè))數(shù)據(jù)要保存起來(lái)，以后還需要從保存的這些數(shù)據(jù)中檢索是否存在某

個(gè)數(shù)據(jù)，（我想說(shuō)出二叉樹(shù)的好處，該怎么說(shuō)呢？那就是說(shuō)別人的缺點(diǎn)），假如存在數(shù)組中，

那么，碰巧要找的數(shù)字位于99999那個(gè)地方，那查找的速度將很慢，因?yàn)橐獜牡?個(gè)依次往

后取，取出來(lái)后進(jìn)行比較。平衡二叉樹(shù)（構(gòu)建平衡二叉樹(shù)需要先排序，我們這里就不作考慮

了）可以很好地解決這個(gè)問(wèn)題，但二叉樹(shù)的遍歷（前序，中序，后序）效率要比數(shù)組低很多，

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語(yǔ)言實(shí)現(xiàn)二叉樹(shù)的層次遍歷的非遞歸算法及查找算法。

先序非遞歸算法

【思路】

假設(shè)：T是要遍歷樹(shù)的根指針，若T != NULL

對(duì)于非遞歸算法，引入棧模擬遞歸工作棧，初始時(shí)棧為空。

問(wèn)題：如何用棧來(lái)保存信息，使得在先序遍歷過(guò)左子樹(shù)后，能利用棧頂信息獲取T的右子樹(shù)的根指針？

方法1：訪問(wèn)T-data后，將T入棧，遍歷左子樹(shù)；遍歷完左子樹(shù)返回時(shí)，棧頂元素應(yīng)為T(mén)，出棧，再先序遍歷T的右子樹(shù)。

方法2：訪問(wèn)T-data后，將T-rchild入棧，遍歷左子樹(shù)；遍歷完左子樹(shù)返回時(shí)，棧頂元素應(yīng)為T(mén)-rchild，出棧，遍歷以該指針為根的子樹(shù)。

【算法1】

void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{ // 基于方法一

InitStack(S);

while ( T!=NULL || !StackEmpty(S)){

while ( T != NULL ){

Visit(T-data) ;

Push(S,T);

T = T-lchild;

}

if( !StackEmpty(S) ){

Pop(S,T);

T = T-rchild;

}

}

}

【算法2】

void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{ // 基于方法二

InitStack(S);

while ( T!=NULL || !StackEmpty(S) ){

while ( T != NULL ){

Visit(T-data);

Push(S, T-rchild);

T = T-lchild;

}

if ( !StackEmpty(S) ){

Pop(S,T);

}

}

}

進(jìn)一步考慮：對(duì)于處理流程中的循環(huán)體的直到型、當(dāng)型+直到型的實(shí)現(xiàn)。

中序非遞歸算法

【思路】

T是要遍歷樹(shù)的根指針，中序遍歷要求在遍歷完左子樹(shù)后，訪問(wèn)根，再遍歷右子樹(shù)。

問(wèn)題：如何用棧來(lái)保存信息，使得在中序遍歷過(guò)左子樹(shù)后，能利用棧頂信息獲取T指針？

方法：先將T入棧，遍歷左子樹(shù)；遍歷完左子樹(shù)返回時(shí)，棧頂元素應(yīng)為T(mén)，出棧，訪問(wèn)T-data，再中序遍歷T的右子樹(shù)。

【算法】

void InOrder(BiTree T, Status ( *Visit ) (ElemType e))

{

InitStack(S);

while ( T!=NULL || !StackEmpty(S) ){

while ( T != NULL ){

Push(S,T);

T = T-lchild;

}

if( !StackEmpty(S) ){

Pop(S, T);

Visit(T-data);

T = T-rchild;

}

}

}

進(jìn)一步考慮：對(duì)于處理流程中的循環(huán)體的直到型、當(dāng)型+直到型的實(shí)現(xiàn)。

后序非遞歸算法

【思路】

T是要遍歷樹(shù)的根指針，后序遍歷要求在遍歷完左右子樹(shù)后，再訪問(wèn)根。需要判斷根結(jié)點(diǎn)的左右子樹(shù)是否均遍歷過(guò)。

可采用標(biāo)記法，結(jié)點(diǎn)入棧時(shí)，配一個(gè)標(biāo)志tag一同入棧(0：遍歷左子樹(shù)前的現(xiàn)場(chǎng)保護(hù)，1：遍歷右子樹(shù)前的現(xiàn)場(chǎng)保護(hù))。

首先將T和tag(為0)入棧，遍歷左子樹(shù)；返回后，修改棧頂tag為1，遍歷右子樹(shù)；最后訪問(wèn)根結(jié)點(diǎn)。 [Page]

typedef struct stackElement{

Bitree data;

char tag;

}stackElemType;

【算法】

void PostOrder(BiTree T, Status ( *Visit ) (ElemType e))

{

InitStack(S);

while ( T!=NULL || !StackEmpty(S) ){

while ( T != NULL ){

Push(S,T,0);

T = T-lchild;

}

while ( !StackEmpty(S) GetTopTag(S)==1){

Pop(S, T);

Visit(T-data);

}

if ( !StackEmpty(S) ){

SetTopTag(S, 1); // 設(shè)置棧頂標(biāo)記

T = GetTopPointer(S); // 取棧頂保存的指針

T = T-rchild;

}else break;

}

}

分享名稱(chēng)：二叉樹(shù)尋路Java代碼 二叉樹(shù)實(shí)現(xiàn) java代碼
網(wǎng)頁(yè)網(wǎng)址：http://chinadenli.net/article44/dodogee.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、定制開(kāi)發(fā)、Google、搜索引擎優(yōu)化、網(wǎng)站內(nèi)鏈、虛擬主機(jī)

廣告

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