二叉树相关算法java

① java二叉树递归算法原理

“node.left!=null从根节点开始递归到9，跳出循环输出9，接着判断9的右节点为null；”
你这就话本身就有问题，输出9时，那么node是多少呢，是12，接着是判断12的右节点，而不是9的右节点。
根节点是相对的，
你把9看成左节点，那么12就是根节点，
按照中序遍历规则，左中右，那么输出9就到12有什么奇怪呢，
你把9看成根节点，它也是叶节点，没有左右节点，那么输出9就到12有什么奇怪呢。
你递归不懂就应该看谭浩强的递归分析，而不是来看二叉树。

② 二叉树的java实现与几种遍历

二叉树的定义

二叉树(binary tree)是结点的有限集合，这个集合或者空，或者由一个根及两个互不相交的称为这个根的左子树或右子树构成.

从定义可以看出，二叉树包括：1.空树 2.只有一个根节点 3.只有左子树 4.只有右子树 5.左右子树都存在 有且仅有这5种表现形式

二叉树的遍历分为三种：前序遍历 中序遍历 后序遍历

• 前序遍历：按照“根左右”,先遍历根节点，再遍历左子树 ，再遍历右子树

• 中序遍历：按照“左根右“,先遍历左子树，再遍历根节点，最后遍历右子树

• 后续遍历：按照“左右根”，先遍历左子树，再遍历右子树，最后遍历根节点

其中前，后，中指的是每次遍历时候的根节点被遍历的顺序

具体实现看下图：

③ 用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构建二叉树算法

下面是你第一个问题的解法，是构建了树以后又把后序输出的程序。以前写的，可以把输出后序的部分删除，还有检验先序中序的输入是否合法的代码也可以不要。/*****TreeNode.java*********/public class TreeNode {
char elem;
TreeNode left;
TreeNode right;
}/*******PlantTree.java*********/import java.io.*;
public class PlantTree {
TreeNode root;
public static void main(String[] args) {
PlantTree seed=new PlantTree();
String preorder=null;
String inorder=null;
try {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Please input the preorder");
preorder=br.readLine();
System.out.println("Please input the inorder");
inorder=br.readLine();
} catch (Exception e) {
// TODO: handle exception
}

if(preorder!=null&&seed.checkTree(preorder,inorder)) {

seed.root=new TreeNode();
seed.root.elem=preorder.charAt(0);
seed.makeTree(preorder,inorder,seed.root);
System.out.println("The tree has been planted,the postorder is:");
seed.printPostorder(seed.root);
}
}

void makeTree(String preorder,String inorder,TreeNode root) {
int i=inorder.lastIndexOf(root.elem);

if(i!=0) {//有左子树
String leftPre=preorder.substring(1, i+1);
String leftIn=inorder.substring(0,i);
TreeNode leftNode=new TreeNode();
leftNode.elem=leftPre.charAt(0);
root.left=leftNode;
makeTree(leftPre,leftIn,leftNode);
}
if(i!=inorder.length()-1) {//有右子树
String rightPre=preorder.substring(i+1,preorder.length());
String rightIn=inorder.substring(i+1,inorder.length());
TreeNode rightNode=new TreeNode();
rightNode.elem=rightPre.charAt(0);
root.right=rightNode;
makeTree(rightPre,rightIn,rightNode);
}

}
void printPostorder(TreeNode root) {
if(root.left!=null)
printPostorder(root.left);
if(root.right!=null)
printPostorder(root.right);
System.out.print(root.elem);

}
boolean checkTree(String a,String b) {
for(int i=0;i<a.length();i++) {
if(i!=a.lastIndexOf(a.charAt(i))) {
System.out.println("There are same element in the tree");
return false;
}
if(!b.contains(""+a.charAt(i))) {
System.out.println("Invalid input");
return false;
}

}
if(a.length()==b.length())
return true;
return false;
}
}

⑤ Java数据结构与算法有哪些

《Java数据结构和算法》（第2版）介绍了计算机编程中使用的数据结构和算法，对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章，分别讲述了基本概念、数组、简单排序、堆和队列、链表、递归、进阶排序、二叉树、红黑树、哈希表及图形等知识。附录中则提供了运行专题Applet和例程、相关书籍和问题解答。《Java数据结构和算法》（第2版）提供了学完一门编程语言后进一步需要知道的知识。本书所涵盖的内容通常作为大学或学院中计算机系二年级的课程，在学生掌握了编程的基础后才开始本书的学习。

⑥ 求java实现二叉树启遍历的算法

public
class
TreeNode1
{
//二叉树的结点类
public
String
data;
//数据元数
public
TreeNode1
left,right;
//指向左,右孩子结点的链
public
TreeNode1(){
this("?");
}
public
TreeNode1(String
d){
//构造有值结点
data
=
d;
left
=
right
=
null;
}
public
void
preorder(TreeNode1
p){
//先根次序遍历二叉树
if(p!=null){
System.out.print(p.data+"
");
preorder(p.left);
preorder(p.right);
}
}
public
void
inorder(TreeNode1
p){
//中根次序遍历二叉树
if(p!=null){
inorder(p.left);
System.out.print(p.data+"
");
inorder(p.right);
}
}
public
void
postorder(TreeNode1
p){
//后根次序遍历二叉树
if(p!=null){
postorder(p.left);
postorder(p.right);
System.out.print(p.data+"
");
}
}
}

⑦ 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
12345if(depleft>depright){ return depleft+1;}else{ return depright+1;}
只有left大于right的时候采取left
+1，相等是取right

⑧ java编程 二叉树

要遍历此二叉树，先要建立一个二叉树，用C语言编写如下：（暂时可以不用理解，参考一下）
/* Note:Your choice is C IDE */
#include "stdio.h"
#define size sizeof(struct list)
struct list
{
int data;
struct list *lchild,*rchild;
};
struct list *q[20];
/*create the tree*/
struct list * create()
{
int num,front=1,rear=0;
struct list *root='\0',*s;
printf("Input the tree node(-1=over,0=null node):");//节点为空则用0表示，-1则结束创建树，这里创建时是输入数字，要输入字母把类型改一下即可
scanf("%d",&num);
printf("\n");
while(num!=-1)
{
s='\0';
if(num!=0)
{
s=(struct list *)malloc(size);
s->data=num;
s->lchild='\0';
s->rchild='\0';

}
rear++;
q[rear]=s;
if(rear==1) root=s;
else
{
if(s&&q[front])
{
if(rear%2==0) q[front]->lchild=s;
else q[front]->rchild=s;
}
if(rear%2==1) front++;
}
printf("input the next tree node:");
scanf("%d",&num);
}
printf("create tree succeeded!\n");
return root;
}
建好树后你就可以遍历了
中序遍历：
inorder(struct list *in)
{
if(in)
{
inorder(in->lchild);
printf("%d ",in->data);
inorder(in->rchild);
}
}
前序后序都差不多
遍历的函数就像留下说的，在定义节点时可以这样写
class Node
{
int data; //数据，可以改成别的数据类型

Node leftChild,rightChlid;//定义左孩子右孩子，类型就是这个类
}
然后C语言中的“->”这些东西直接写成“.”就行了，创建新节点就直接new一个Node可以了，其实都差不多，只是一些语法小有区别

⑨ 用java怎么构造一个二叉树

定义一个结点类：
public class Node {
private int value;
private Node leftNode;
private Node rightNode;

public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}

}

初始化结点树：
public void initNodeTree()
{
int nodeNumber;
HashMap<String, Integer> map = new HashMap<String, Integer>();
Node nodeTree = new Node();

Scanner reader = new Scanner(System.in);

nodeNumber = reader.nextInt();
for(int i = 0; i < nodeNumber; i++) {
int value = reader.nextInt();
String str = reader.next();
map.put(str, value);
}

if (map.containsKey("#")) {
int value = map.get("#");
nodeTree.setValue(value);
setChildNode(map, value, nodeTree);
}

preTraversal(nodeTree);
}

private void setChildNode(HashMap<String, Integer> map, int nodeValue, Node parentNode) {
int value = 0;
if (map.containsKey("L" + nodeValue)) {
value = map.get("L" + nodeValue);
Node leftNode = new Node();
leftNode.setValue(value);
parentNode.setLeftNode(leftNode);

setChildNode(map, value, leftNode);
}

if (map.containsKey("R" + nodeValue)) {
value = map.get("R" + nodeValue);
Node rightNode = new Node();
rightNode.setValue(value);
parentNode.setRightNode(rightNode);

setChildNode(map, value, rightNode);
}
}

前序遍历该结点树：
public void preTraversal(Node nodeTree) {
if (nodeTree != null) {
System.out.print(nodeTree.getValue() + "\t");
preTraversal(nodeTree.getLeftNode());
preTraversal(nodeTree.getRightNode());
}
}

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