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

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

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

CBTType TreeFindNode(CBTType treeNode,String data){

CBTType ptr;

if(treeNode==null){//輸入根節(jié)點為空時

return null;

}else{

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

return treeNode;

}else{

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

return ptr;

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

return ptr;

}else{

return null;

}

}

}

}

從左子樹查找，為什么可以用TreeFindNode表示呢？因為，左子樹也可以按照先序遍歷的順序查找的，所以當然可以用TreeFindNode表示，如果你想左子樹用中序遍歷查找，那么就不可以用TreeFindNode表示。

上述例子的查找過程：

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

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

4--根

5--根

返回

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

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

public?class?BinTree?{

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

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

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

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

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

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

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

{

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é)點，放在中間表示中跟移走...

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("前序遍歷二叉樹結(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 構(gòu)建二叉樹

首先我想問為什么要用LinkedList 來建立二叉樹呢? LinkedList 是線性表,

樹是樹形的, 似乎不太合適。

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

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

String input = "ABCDE F G";

節(jié)點編號從0到8. 層次遍歷的話:

對于節(jié)點i.

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

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

如果你要將帶有節(jié)點信息的樹存到LinkedList里面, 先建立一個節(jié)點類:

class Node{

public char cValue;

public Node leftChild;

public Node rightChild;

public Node(v){

this.cValue = v;

}

}

然后遍歷input,建立各個節(jié)點對象.

LinkedList tree = new LinkedList();

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

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

然后為各個節(jié)點設(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 就存儲了整個二叉樹. 而第0個元素就是樹根，思路大體是這樣吧。

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

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

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

那么，碰巧要找的數(shù)字位于99999那個地方，那查找的速度將很慢，因為要從第1個依次往

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

了）可以很好地解決這個問題，但二叉樹的遍歷（前序，中序，后序）效率要比數(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語言實現(xiàn)二叉樹的層次遍歷的非遞歸算法及查找算法。

先序非遞歸算法

【思路】

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

對于非遞歸算法，引入棧模擬遞歸工作棧，初始時棧為空。

問題：如何用棧來保存信息，使得在先序遍歷過左子樹后，能利用棧頂信息獲取T的右子樹的根指針？

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

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

【算法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);

}

}

}

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

中序非遞歸算法

【思路】

T是要遍歷樹的根指針，中序遍歷要求在遍歷完左子樹后，訪問根，再遍歷右子樹。

問題：如何用棧來保存信息，使得在中序遍歷過左子樹后，能利用棧頂信息獲取T指針？

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

【算法】

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;

}

}

}

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

后序非遞歸算法

【思路】

T是要遍歷樹的根指針，后序遍歷要求在遍歷完左右子樹后，再訪問根。需要判斷根結(jié)點的左右子樹是否均遍歷過。

可采用標記法，結(jié)點入棧時，配一個標志tag一同入棧(0：遍歷左子樹前的現(xiàn)場保護，1：遍歷右子樹前的現(xiàn)場保護)。

首先將T和tag(為0)入棧，遍歷左子樹；返回后，修改棧頂tag為1，遍歷右子樹；最后訪問根結(jié)點。 [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è)置棧頂標記

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

T = T-rchild;

}else break;

}

}

分享名稱：二叉樹尋路Java代碼 二叉樹實現(xiàn) java代碼
網(wǎng)頁網(wǎng)址：http://jinyejixie.com/article44/dodogee.html

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

廣告

聲明：本網(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)