二叉树查找代码java 二叉树的查询方式

求数据结构二叉树查找结点及其父节点的代码，谢谢！！！

#includeiostream

成都创新互联公司专注于新市网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供新市营销型网站建设，新市网站制作、新市网页设计、新市网站官网定制、小程序开发服务，打造新市网络公司原创品牌,更为您提供新市网站排名全网营销落地服务。

#includemap

using namespace std;

const int N=15e3+100;

struct node{

int v;//结点值

int l,r;//左右孩子的下标

st()

{//初始化

l=r=-1;

}

}tree[4*N];//4倍空间,用来储存二叉树

mapint,intmp;//储存数值在数组a中的下标

int a[N];//基础数组,数组tree在其基础上建树

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

void build_tree(int rt,int num)

{//构建二叉树

if(a[num]==0)

{//a[num]==0,表示空结点

tree[rt].v=-1;

}

else

{

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

mp[a[num]]=rt;//储存a[num]在树中的位置

tree[rt].v=a[num];//结点赋值

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++];//储存结点值

}

while(getchar()!='\n');//回车结束输入

build_tree(1,x);//构建二叉树(结构体数组模拟)

cinm;//查询次数

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

{

int num,y;

cinnum;//查询值

y=mp[num];//mp[num]是num在tree数组中的位置,查询效率O(log2n)

y/=2;//左右孩子的下标除以2，就是父节点的下标

if(y==0)

{//父节点下标为0，既是根节点

cout0endl;

}

else

{//输出父节点值

couttree[y].vendl;

}

}

return 0;

}

用JAVA语言实现二叉树的层次遍历的非递归算法及查找算法。

先序非递归算法

【思路】

假设：T是要遍历树的根指针，若T != NULL

对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。

问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？

方法1：访问T-data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。

方法2：访问T-data后，将T-rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为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);

}

}

}

进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。

中序非递归算法

【思路】

T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。

问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？

方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为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;

}

}

}

进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。

后序非递归算法

【思路】

T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。

可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。

首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。 [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); // 设置栈顶标记

T = GetTopPointer(S); // 取栈顶保存的指针

T = T-rchild;

}else break;

}

}

java数据结构二叉树查找结点操作，递归调用求详细讲解

这是先序遍历树的代码，什么是先序遍历呢，一种按照根-左子树-右子树的顺序遍历树就是先序遍历。

CBTType TreeFindNode(CBTType treeNode,String data){

CBTType ptr;

if(treeNode==null){//输入根节点为空时

return null;

}else{

if(treeNode.data.equals(data)){//根节点等于要查找的数据时

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代码

import java.util.ArrayList;

// 树的一个节点

class TreeNode {

Object _value = null; // 他的值

TreeNode _parent = null; // 他的父节点，根节点没有PARENT

ArrayList _childList = new ArrayList(); // 他的孩子节点

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 {

// 给出宽度优先遍历的值数组，构建出一棵多叉树

// null 值表示一个层次的结束

// "|" 表示一个层次中一个父亲节点的孩子输入结束

// 如：给定下面的值数组：

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

// 则构建出一个根节点，带有两个孩子("left","right")的树

public Tree( Object[] values ){

// 创建根

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

// 创建下面的子节点

TreeNode currentParent = _root; // 用于待创建节点的父亲

//TreeNode nextParent = null;

int currentChildIndex = 0; // 表示 currentParent 是他的父亲的第几个儿子

//TreeNode lastNode = null; // 最后一个创建出来的TreeNode，用于找到他的父亲

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

// 如果null ,表示下一个节点的父亲是当前节点的父亲的第一个孩子节点

if ( values[i] == null ){

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

currentChildIndex = 0;

continue;

}

// 表示一个父节点的所有孩子输入完毕

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;

}

/**

// 按宽度优先遍历，打印出parent子树所有的节点

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);// 为了避免叶子节点也会打印null

//打印 parent 同层的节点的孩子

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

}

}

// 递归调用，打印所有节点

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

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

printSteps( child, currentDepth+1 );

}

}

// 按宽度优先遍历，打印出parent子树所有的节点

public void printSteps(){

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

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

printSteps(_root, 1 );

}**/

// 将给定的值做为 parent 的孩子，构建节点

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;

// 添加数据

public void add(int data) {

// 递归调用

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

}

}

// 查询数据

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;

}

}