「循环二叉树java」循环前序遍历二叉树
今天给各位分享循环二叉树java的知识，其中也会对循环前序遍历二叉树进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
用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实现二叉树遍历程序 多少分都行 啊
在JAVA中实现二叉树，程序如下（转载）
//********************************************************************
//filename: BinaryTreeTest.java
//purpose: test a binarytree with java
//date: 2002/12/18
//author: flyfan
//ver: 0.1
//********************************************************************
public class BinaryTreeTest
{
public static void main(String args[])
{
BinaryTreeTest b=new BinaryTreeTest();
int data[]={12,11,34,45,67,89,56,43,22,98};
BinaryTree root =new BinaryTree(data[0]);
System.out.print("二叉树的中的数据： ");
for(int i=1;i{
root.insertTree(root,data[i]);
System.out.print(data[i-1]+";");
}
System.out.println(data[data.length-1]);
int key=Integer.parseInt(args[0]);
if(b.searchkey(root,key))
{
System.out.println("找到了:"+key);
}
else
{
System.out.println("没有找到："+key);
}
}
public boolean searchkey(BinaryTree root, int key)
{
boolean bl=false;
if(root==null)
{
bl=false;
return bl;
}
else if(root.data==key)
{
bl=true;
return bl;
}
else if(key=root.data)
{
return searchkey(root.rightpoiter,key);
}
return searchkey(root.leftpoiter,key);
}
}
class BinaryTree
{
int data;
BinaryTree leftpoiter;
BinaryTree rightpoiter;
BinaryTree(int data)
{
this.data=data;
leftpoiter=null;
rightpoiter=null;
}
public void insertTree(BinaryTree root, int data)
{
if(data=root.data)
{
if(root.rightpoiter==null)
{
root.rightpoiter=new BinaryTree(data);
}
else
{
insertTree(root.rightpoiter,data);
}
}
else
{
if(root.leftpoiter==null)
{
root.leftpoiter=new BinaryTree(data);
}
else
{
insertTree(root.leftpoiter,data);
}
}
}
}
//end
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和循环前序遍历二叉树的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。