求數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)查找結(jié)點(diǎn)及其父節(jié)點(diǎn)的代碼，謝謝！！！

#includeiostream

成都創(chuàng)新互聯(lián)公司專注于新市網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠(chéng)為您提供新市營(yíng)銷型網(wǎng)站建設(shè)，新市網(wǎng)站制作、新市網(wǎng)頁(yè)設(shè)計(jì)、新市網(wǎng)站官網(wǎng)定制、小程序開(kāi)發(fā)服務(wù)，打造新市網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供新市網(wǎng)站排名全網(wǎng)營(yíng)銷落地服務(wù)。

#includemap

using namespace std;

const int N=15e3+100;

struct node{

int v;//結(jié)點(diǎn)值

int l,r;//左右孩子的下標(biāo)

st()

{//初始化

l=r=-1;

}

}tree[4*N];//4倍空間,用來(lái)儲(chǔ)存二叉樹(shù)

mapint,intmp;//儲(chǔ)存數(shù)值在數(shù)組a中的下標(biāo)

int a[N];//基礎(chǔ)數(shù)組,數(shù)組tree在其基礎(chǔ)上建樹(shù)

int n=1;//1 5 8 0 0 0 6 0 0

void build_tree(int rt,int num)

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

if(a[num]==0)

{//a[num]==0,表示空結(jié)點(diǎn)

tree[rt].v=-1;

}

else

{

if(mp.count(a[num])==0)

mp[a[num]]=rt;//儲(chǔ)存a[num]在樹(shù)中的位置

tree[rt].v=a[num];//結(jié)點(diǎn)賦值

num++;

build_tree(2*rt,num);//左孩子

num++;

build_tree(2*rt+1,num);//右孩子

}

}

/*

1 5 8 0 0 0 6 0 0

3

8 1 6

*/

int main()

{

int x=1,m=0;

do

{

cina[n++];//儲(chǔ)存結(jié)點(diǎn)值

}

while(getchar()!='\n');//回車結(jié)束輸入

build_tree(1,x);//構(gòu)建二叉樹(shù)(結(jié)構(gòu)體數(shù)組模擬)

cinm;//查詢次數(shù)

for(int i=0;im;i++)

{

int num,y;

cinnum;//查詢值

y=mp[num];//mp[num]是num在tree數(shù)組中的位置,查詢效率O(log2n)

y/=2;//左右孩子的下標(biāo)除以2，就是父節(jié)點(diǎn)的下標(biāo)

if(y==0)

{//父節(jié)點(diǎn)下標(biāo)為0，既是根節(jié)點(diǎn)

cout0endl;

}

else

{//輸出父節(jié)點(diǎn)值

couttree[y].vendl;

}

}

return 0;

}

用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，出棧，再先序遍歷T的右子樹(shù)。

方法2：訪問(wèn)T-data后，將T-rchild入棧，遍歷左子樹(shù)；遍歷完左子樹(shù)返回時(shí)，棧頂元素應(yīng)為T-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，出棧，訪問(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;

}

}

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

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

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--根

返回

建立一個(gè)二叉樹(shù)，附帶查詢代碼，JAVA代碼

import java.util.ArrayList;

// 樹(shù)的一個(gè)節(jié)點(diǎn)

class TreeNode {

Object _value = null; // 他的值

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

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

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)建出一棵多叉樹(shù)

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

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

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

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

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

public Tree( Object[] values ){

// 創(chuàng)建根

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

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

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

//TreeNode nextParent = null;

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

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

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

// 如果null ,表示下一個(gè)節(jié)點(diǎn)的父親是當(dāng)前節(jié)點(diǎn)的父親的第一個(gè)孩子節(jié)點(diǎn)

if ( values[i] == null ){

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

currentChildIndex = 0;

continue;

}

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

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子樹(shù)所有的節(jié)點(diǎn)

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é)點(diǎn)也會(huì)打印null

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

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é)點(diǎn)

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

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

printSteps( child, currentDepth+1 );

}

}

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

public void printSteps(){

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

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

printSteps(_root, 1 );

}**/

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

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：二叉樹(shù)添加和查詢方法

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;

}

}

分享標(biāo)題：二叉樹(shù)查找代碼java 二叉樹(shù)的查詢方式
當(dāng)前路徑：http://chinadenli.net/article28/hihejp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計(jì)、網(wǎng)站制作、虛擬主機(jī)、網(wǎng)站內(nèi)鏈、網(wǎng)站建設(shè)、手機(jī)網(wǎng)站建設(shè)

廣告

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