java二叉树查找

‘壹’ 写一个java层次遍历二叉树,简单点就可以,我要的是代码,不是纯文字说明

public class BinaryNode {
Object element;
BinaryNode left;
BinaryNode right;

}

import java.util.*;

public class Queue {

protected LinkedList list;

// Postcondition: this Queue object has been initialized.
public Queue() {

list = new LinkedList();

} // default constructor

// Postcondition: the number of elements in this Queue object has been
// returned.
public int size() {

return list.size();

} // method size

// Postcondition: true has been returned if this Queue object has no
// elements. Otherwise, false has been returned.
public boolean isEmpty() {

return list.isEmpty();

} // method isEmpty

// Postconditon: A of element has been inserted at the back of this
// Queue object. The averageTime (n) is constant and
// worstTime (n) is O (n).
public void enqueue(Object element) {

list.addLast(element);

} // method enqueue

// Precondition: this Queue object is not empty. Otherwise,
// NoSuchElementException will be thrown.
// Postcondition: The element that was at the front of this Queue object -
// just before this method was called -- has been removed
// from this Queue object and returned.
public Object dequeue() {

return list.removeFirst();

} // method dequeue

// Precondition: this Queue object is not empty. Otherwise,
// NoSuchElementException will be thrown.
// Postcondition: the element at index 0 in this Queue object has been
// returned.
public Object front() {

return list.getFirst();

} // method front

} // Queue class

import java.io.IOException;

public class BinaryTree {
BinaryNode root;

public BinaryTree() {
super();
// TODO 自动生成构造函数存根
root=this.createPre();
}

public BinaryNode createPre()
//按照先序遍历的输入方法，建立二叉树
{
BinaryNode t=null;
char ch;
try {
ch = (char)System.in.read();

if(ch==' ')
t=null;
else
{
t=new BinaryNode();
t.element=(Object)ch;
t.left=createPre();
t.right=createPre();
}
} catch (IOException e) {
// TODO 自动生成 catch 块
e.printStackTrace();
}
return t;
}

public void inOrder()
{
this.inOrder(root);
}

public void inOrder(BinaryNode t)
//中序遍历二叉树
{
if(t!=null)
{
inOrder(t.left);
System.out.print(t.element);
inOrder(t.right);
}
}

public void postOrder()
{
this.postOrder(root);
}

public void postOrder(BinaryNode t)
//后序遍历二叉树
{
if(t!=null)
{
postOrder(t.left);
System.out.print(t.element);
postOrder(t.right);
}
}

public void preOrder()
{
this.preOrder(root);
}
public void preOrder(BinaryNode t)
//前序遍历二叉树
{
if(t!=null)
{
System.out.print(t.element);
preOrder(t.left);
preOrder(t.right);
}
}

public void breadthFirst()
{
Queue treeQueue=new Queue();
BinaryNode p;
if(root!=null)
treeQueue.enqueue(root);
while(!treeQueue.isEmpty())
{
System.out.print(((BinaryNode)(treeQueue.front())).element);
p=(BinaryNode)treeQueue.dequeue();
if(p.left!=null)
treeQueue.enqueue(p.left);
if(p.right!=null)
treeQueue.enqueue(p.right);
}
}
}

public class BinaryTreeTest {

/**
* @param args
*/
public static void main(String[] args) {
// TODO 自动生成方法存根
BinaryTree tree = new BinaryTree();

System.out.println("先序遍历：");
tree.preOrder();
System.out.println();

System.out.println("中序遍历：");
tree.inOrder();
System.out.println();

System.out.println("后序遍历：");
tree.postOrder();
System.out.println();

System.out.println("层次遍历：");
tree.breadthFirst();
System.out.println();
}

}

‘贰’ 如何用Java的方式设计一个后序线索二叉树的方法

在Java中，你可以定义一哪激弊个类来表示后序线索二叉树，其中包含有头节点、尾节点和当前节点指针。你可以使用递归或迭代方法遍历整棵树，并创建线索，即存储前驱和后继节点的指针。当访问到叶子节点时，需要将尾节点的指针指向它，尾节点铅隐的指李族针则指向头节点
// 定

‘叁’ 用java怎么构造一个二叉树呢

二叉树的相关操作，包括创建，中序、先序、后序（递归和非递归），其中重点的是java在先序创建二叉树和后序非递归遍历的的实现。
package com.algorithm.tree;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

public class Tree<T> {

private Node<T> root;

public Tree() {
}

public Tree(Node<T> root) {
this.root = root;
}

//创建二叉树
public void buildTree() {

Scanner scn = null;
try {
scn = new Scanner(new File("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
root = createTree(root,scn);
}
//先序遍历创建二叉树
private Node<T> createTree(Node<T> node,Scanner scn) {

String temp = scn.next();

if (temp.trim().equals("#")) {
return null;
} else {
node = new Node<T>((T)temp);
node.setLeft(createTree(node.getLeft(), scn));
node.setRight(createTree(node.getRight(), scn));
return node;
}

}

//中序遍历(递归)
public void inOrderTraverse() {
inOrderTraverse(root);
}

public void inOrderTraverse(Node<T> node) {
if (node != null) {
inOrderTraverse(node.getLeft());
System.out.println(node.getValue());
inOrderTraverse(node.getRight());
}
}

//中序遍历(非递归)
public void nrInOrderTraverse() {

Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
node = stack.pop();
System.out.println(node.getValue());
node = node.getRight();

}

}
//先序遍历(递归)
public void preOrderTraverse() {
preOrderTraverse(root);
}

public void preOrderTraverse(Node<T> node) {
if (node != null) {
System.out.println(node.getValue());
preOrderTraverse(node.getLeft());
preOrderTraverse(node.getRight());
}
}

//先序遍历（非递归）
public void nrPreOrderTraverse() {

Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;

while (node != null || !stack.isEmpty()) {

while (node != null) {
System.out.println(node.getValue());
stack.push(node);
node = node.getLeft();
}
node = stack.pop();
node = node.getRight();
}

}

//后序遍历(递归)
public void postOrderTraverse() {
postOrderTraverse(root);
}

public void postOrderTraverse(Node<T> node) {
if (node != null) {
postOrderTraverse(node.getLeft());
postOrderTraverse(node.getRight());
System.out.println(node.getValue());
}
}

//后续遍历(非递归)
public void nrPostOrderTraverse() {

Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
Node<T> preNode = null;//表示最近一次访问的节点

while (node != null || !stack.isEmpty()) {

while (node != null) {
stack.push(node);
node = node.getLeft();
}

node = stack.peek();

if (node.getRight() == null || node.getRight() == preNode) {
System.out.println(node.getValue());
node = stack.pop();
preNode = node;
node = null;
} else {
node = node.getRight();
}

}

}

//按层次遍历
public void levelTraverse() {
levelTraverse(root);
}

public void levelTraverse(Node<T> node) {

Queue<Node<T>> queue = new LinkedBlockingQueue<Node<T>>();
queue.add(node);
while (!queue.isEmpty()) {

Node<T> temp = queue.poll();
if (temp != null) {
System.out.println(temp.getValue());
queue.add(temp.getLeft());
queue.add(temp.getRight());
}

}

}

}

//树的节点

class Node<T> {

private Node<T> left;
private Node<T> right;
private T value;

public Node() {
}
public Node(Node<T> left,Node<T> right,T value) {
this.left = left;
this.right = right;
this.value = value;
}

public Node(T value) {
this(null,null,value);
}
public Node<T> getLeft() {
return left;
}
public void setLeft(Node<T> left) {
this.left = left;
}
public Node<T> getRight() {
return right;
}
public void setRight(Node<T> right) {
this.right = right;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}

}
测试代码：
package com.algorithm.tree;

public class TreeTest {

/**
* @param args
*/
public static void main(String[] args) {
Tree<Integer> tree = new Tree<Integer>();
tree.buildTree();
System.out.println("中序遍历");
tree.inOrderTraverse();
tree.nrInOrderTraverse();
System.out.println("后续遍历");
//tree.nrPostOrderTraverse();
tree.postOrderTraverse();
tree.nrPostOrderTraverse();
System.out.println("先序遍历");
tree.preOrderTraverse();
tree.nrPreOrderTraverse();

//
}

}

‘肆’ java 构建二叉树

首先我想问为什么要用LinkedList 来建立二叉树呢? LinkedList 是线性表,
树是树形的, 似乎不太合适。

其实也可以用数组完成，而且效率更高.
关键是我觉得你这个输入本身就是一个二叉树啊，
String input = "ABCDE F G";
节点编号从0到8. 层次遍历的话:
对于节点i.
leftChild = input.charAt(2*i+1); //做子树
rightChild = input.charAt(2*i+2);//右子树

如果你要将带有节点信息的树存到LinkedList里面, 先建立一个节点类:
class Node{
public char cValue;
public Node leftChild;
public Node rightChild;
public Node(v){
this.cValue = v;
}
}

然后遍历input,建立各个节点对象.
LinkedList tree = new LinkedList();
for(int i=0;i< input.length;i++)
LinkedList.add(new Node(input.charAt(i)));

然后为各个节点设置左右子树:
for(int i=0;i<input.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实现二叉树的问题

/**
* 二叉树测试二叉树顺序存储在treeLine中，递归前序创建二叉树。另外还有能
* 够前序、中序、后序、按层遍历二叉树的方法以及一个返回遍历结果asString的
* 方法。
*/

public class BitTree {
public static Node2 root;
public static String asString;

//事先存入的数组,符号#表示二叉树结束。
public static final char[] treeLine = {'a','b','c','d','e','f','g',' ',' ','j',' ',' ','i','#'};

//用于标志二叉树节点在数组中的存储位置，以便在创建二叉树时能够找到节点对应的数据。
static int index;

//构造函数
public BitTree() {
System.out.print("测试二叉树的顺序表示为：");
System.out.println(treeLine);
this.index = 0;
root = this.setup(root);
}

//创建二叉树的递归程序
private Node2 setup(Node2 current) {
if (index >= treeLine.length) return current;
if (treeLine[index] == '#') return current;
if (treeLine[index] == ' ') return current;
current = new Node2(treeLine[index]);
index = index * 2 + 1;
current.left = setup(current.left);
index ++;
current.right = setup(current.right);
index = index / 2 - 1;
return current;
}

//二叉树是否为空。
public boolean isEmpty() {
if (root == null) return true;
return false;
}

//返回遍历二叉树所得到的字符串。
public String toString(int type) {
if (type == 0) {
asString = "前序遍历：\t";
this.front(root);
}
if (type == 1) {
asString = "中序遍历：\t";
this.middle(root);
}
if (type == 2) {
asString = "后序遍历：\t";
this.rear(root);
}
if (type == 3) {
asString = "按层遍历：\t";
this.level(root);
}
return asString;
}

//前序遍历二叉树的循环算法，每到一个结点先输出，再压栈，然后访问它的左子树，
//出栈，访问其右子树，然后该次循环结束。
private void front(Node2 current) {
StackL stack = new StackL((Object)current);
do {
if (current == null) {
current = (Node2)stack.pop();
current = current.right;
} else {
asString += current.ch;
current = current.left;
}
if (!(current == null)) stack.push((Object)current);
} while (!(stack.isEmpty()));
}

//中序遍历二叉树
private void middle(Node2 current) {
if (current == null) return;
middle(current.left);
asString += current.ch;
middle(current.right);
}

//后序遍历二叉树的递归算法
private void rear(Node2 current) {
if (current == null) return;
rear(current.left);
rear(current.right);
asString += current.ch;
}

}

/**
* 二叉树所使用的节点类。包括一个值域两个链域
*/

public class Node2 {
char ch;
Node2 left;
Node2 right;

//构造函数
public Node2(char c) {
this.ch = c;
this.left = null;
this.right = null;
}

//设置节点的值
public void setChar(char c) {
this.ch = c;
}

//返回节点的值
public char getChar() {
return ch;
}

//设置节点的左孩子
public void setLeft(Node2 left) {
this.left = left;
}

//设置节点的右孩子
public void setRight (Node2 right) {
this.right = right;
}

//如果是叶节点返回true
public boolean isLeaf() {
if ((this.left == null) && (this.right == null)) return true;
return false;
}
}

一个作业题，里面有你要的东西。
主函数自己写吧。当然其它地方也有要改的。

‘陆’ 如何用java实现二叉树

import java.util.List;
import java.util.LinkedList;

public class Bintrees {
private int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
private static List<Node> nodeList = null;

private static class Node {
Node leftChild;
Node rightChild;
int data;

Node(int newData) {
leftChild = null;
rightChild = null;
data = newData;
}
}

// 创建二叉树
public void createBintree() {
nodeList = new LinkedList<Node>();

// 将数组的值转换为node
for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {
nodeList.add(new Node(array[nodeIndex]));
}

// 对除最后一个父节点按照父节点和孩子节点的数字关系建立二叉树
for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {
nodeList.get(parentIndex).leftChild = nodeList.get(parentIndex * 2 + 1);
nodeList.get(parentIndex).rightChild = nodeList.get(parentIndex * 2 + 2);
}

// 最后一个父节点
int lastParentIndex = array.length / 2 - 1;

// 左孩子
nodeList.get(lastParentIndex).leftChild = nodeList.get(lastParentIndex * 2 + 1);

// 如果为奇数，建立右孩子
if (array.length % 2 == 1) {
nodeList.get(lastParentIndex).rightChild = nodeList.get(lastParentIndex * 2 + 2);
}
}

// 前序遍历
public static void preOrderTraverse(Node node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);
}

// 中序遍历
public static void inOrderTraverse(Node node) {
if (node == null) {
return;
}

inOrderTraverse(node.leftChild);
System.out.print(node.data + " ");
inOrderTraverse(node.rightChild);
}

// 后序遍历
public static void postOrderTraverse(Node node) {
if (node == null) {
return;
}

postOrderTraverse(node.leftChild);
postOrderTraverse(node.rightChild);
System.out.print(node.data + " ");
}

public static void main(String[] args) {
Bintrees binTree = new Bintrees();
binTree.createBintree();
Node root = nodeList.get(0);

System.out.println("前序遍历：");
preOrderTraverse(root);
System.out.println();

System.out.println("中序遍历：");
inOrderTraverse(root);
System.out.println();

System.out.println("后序遍历：");
postOrderTraverse(root);
}
}

输出结果：
前序遍历：
1 2 4 8 9 5 3 6 7
中序遍历：
8 4 9 2 5 1 6 3 7
后序遍历：
8 9 4 5 2 6 7 3 1

‘柒’ java如何求二叉树中任意两个节点的最大距离

两个节点的距离的定义是这两个节点间边的个数，
比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，
优化时间空间复杂度。
代码：
void MaxDistance(Tree* root,int &deep,int & maxdis)
{
if(root)
{
deep=0;
maxdis=0;
}
int l_deep,l_maxdis;
int r_deep,r_maxdis;
if(root->left!=null)
MaxDistance(root->left,l_deep,l_maxdis);
if(root->right!=null)
MaxDistance(root->right,r_deep,r_maxdis);
deep=(l_deep>r_deep?l_deep:r_deep)+1;
maxdis=l_maxdis>r_maxdis?l_maxdis:r_maxdis;
maxdis=(l_deep+r_deep)>maxdis?l_deep+r_deep:maxdis;
}
}

‘捌’ Java数据结构二叉树深度递归调用算法求内部算法过程详解

二叉树
1
2 3
4 5 6 7
这个二叉树的深度是3，树的深度是最大结点所在的层，这里是3.

应该计算所有结点层数，选择最大的那个。

根据上面的二叉树代码，递归过程是：

f(1)=f(2)+1 > f(3) +1 ? f(2) + 1 : f(3) +1

f(2) 跟f(3)计算类似上面，要计算左右结点，然后取大者

所以计算顺序是f(4.left) = 0, f(4.right) = 0

f(4) = f(4.right) + 1 = 1

然后计算f(5.left) = 0,f(5.right) = 0

f(5) = f(5.right) + 1 =1

f(2) = f(5) + 1 =2

f(1.left) 计算完毕，计算f(1.right) f(3) 跟计算f(2)的过程一样。

得到f(3) = f(7) +1 = 2

f(1) = f(3) + 1 =3

if(depleft>depright){
returndepleft+1;
}else{
returndepright+1;
}

只有left大于right的时候采取left +1，相等是取right

‘玖’ 我想要找一份关于java数据结构二叉树的实例详解（所有基本操作，包括二叉树的高度和节点总数）

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数
//基于先序遍历算法创建二叉树
//要求输入先序序列，其中加入虚结点"#"以示空指针的位置
BinTree CreatBinTree(void){
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //读入#，返回空指针
else{
T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点
T->data=ch;
T->lchild=CreatBinTree(); //构造左子树
T->rchild=CreatBinTree(); //构造右子树
return(T);
}
}
//先序遍历
void Preorder(BinTree T){
if(T){
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
//中序遍历
void Inorder(BinTree T){
if(T){
Inorder(T->lchild); //中序遍历左子树
printf("%c",T->data); //访问结点
Inorder(T->rchild); //中序遍历右子树
}
}
//后序遍历
void Postorder(BinTree T){
if(T){
Postorder(T->lchild); //后序遍历左子树
Postorder(T->rchild); //后序遍历右子树
printf("%c",T->data); //访问结点
}
}
//采用后序遍历求二叉树的深度、结点数及叶子数的递归算法
int TreeDepth(BinTree T){
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。
return(max+1);
}
else return(0);
}
//主函数
void main(){
BinTree root;
int i,depth;
printf("\n");
printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列，
// 用#代表虚结点，如ABD###CE##F##
root=CreatBinTree(); //创建二叉树，返回根结点
do{ //从菜单中选择遍历方式，输入序号。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //输入菜单序号（0-4）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历
break;
case 4: depth=TreeDepth(root); //求树的深度及叶子数
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5: printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历
break;
default: exit(1);
}
printf("\n");
}while(i!=0);
}
//按层遍历
Levelorder( BinTNode *root){
BinTNode * q[Max]; //定义BinTNode类型的队列 用于存放节点 队列长最大为20个元素
int front=0,rear=0; //初始化队列为空
BinTNode *p; //临时节点指针
if(root!=NULL){ //将根节点进队
rear=(rear+1)%Max;
q[rear]=root;
}
while(front!=rear){
front=(front+1)%Max;
p=q[front]; //删除队首的元素 让两个节点（左右节点）孤立
printf("%c",p->data); //输出队列首元素的值
if(p->left!=null){ //如果存在左孩子节点，则左孩子节点进入队列
rear=(rear+1)%Max;
q[rear]=p->left;
}
if(p->right!=null){ //如果存在右孩子节点，则右孩子节点进入队列
rear=(rear+1)%Max;
q[rear]=p->right;
}
}
}