「二叉树中序遍历java」二叉树中序遍历Java
本篇文章给大家谈谈二叉树中序遍历java，以及二叉树中序遍历Java对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
- 1、写一个java层次遍历二叉树,简单点就可以,我要的是代码,不是纯文字说明
- 2、用JAVA语言实现二叉树的层次遍历的非递归算法及查找算法。
- 3、求一个java遍历比较完整树的方法
- 4、java二叉树中序遍历 的递归算法没有看懂。。search(data.getLeft());之后不就回到最左边的一个
写一个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 copy 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语言实现二叉树的层次遍历的非递归算法及查找算法。
先序非递归算法
【思路】
假设：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遍历比较完整树的方法
//用中序遍历一个二叉树
class BinaryTree
{
class Node
{
private int data; //保存数据内容
private Node left; //左子树
private Node right;//右子树
public Node(int data){
this.data = data;
}
public void addNode(Node newNode){ //addNode方法用来添加数据
if(newNode.data = this.data){
if(this.left == null){ //左子树为空
this.left = newNode;
}else{
this.left.addNode(newNode);//继续向下判断
}
}
if(newNode.data this.data){
if(this.right == null){ //右子树为空
this.right = newNode;
}else{
this.right.addNode(newNode);//继续向下判断
}
}
} //addNode方法结束
public void printNode(){ //采用中序遍历（左-根-右)
if(this.left != null){
this.left.printNode();
}
System.out.println(this.data); //找到根内容
if(this.right != null){
this.right.printNode();
}
}
} //Node类结束
private Node root; //根节点
public void add(int data){
Node newNode = new Node(data);
if(this.root == null){
this.root = newNode;
}else{
this.root.addNode(newNode);
}
}
public void print(){
this.root.printNode();
}
}
public class Demo
{
public static void main(String args[]){
BinaryTree bt = new BinaryTree();
bt.add(3);
bt.add(4);
bt.add(0);
bt.add(1);
bt.print();
}
}
java二叉树中序遍历 的递归算法没有看懂。。search(data.getLeft());之后不就回到最左边的一个
最左边的节点是没有左子树和右子树的。
if(data.getLeft()!=null){ // 这里getLetf()为null
search(data.getLeft());
}
System.out.print(data.getObj()+","); //只有这句是执行的！
if(data.getRight()!=null){ // 这里getRight()为null
search(data.getRight());
}
然后就会退到上一个节点的遍历函数了。
关于二叉树中序遍历java和二叉树中序遍历Java的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
发布于：2022-11-26，除非注明，否则均为原创文章，转载请注明出处。