「java非二叉树」java实现二叉树非递归遍历
本篇文章给大家谈谈java非二叉树，以及java实现二叉树非递归遍历对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
- 1、java中 遍历树的方法？一个非二叉树
- 2、用java怎么构造一个二叉树呢？
- 3、java 用递归创建二叉树，非递归遍历二叉树输出节点
- 4、用JAVA语言实现二叉树的层次遍历的非递归算法及查找算法。
- 5、java 构建二叉树
- 6、java如何创建一颗二叉树
java中 遍历树的方法？一个非二叉树
可以，查找所有的节点看看没有父节点就行了。存在父节点的就不是根，而不存在父节点就是根节点。
用java怎么构造一个二叉树呢？
java构造二叉树，可以通过链表来构造，如下代码：
public class BinTree {
public final static int MAX=40;
BinTree []elements = new BinTree[MAX];//层次遍历时保存各个节点
int front;//层次遍历时队首
int rear;//层次遍历时队尾
private Object data; //数据元数
private BinTree left,right; //指向左,右孩子结点的链
public BinTree()
{
}
public BinTree(Object data)
{ //构造有值结点
this.data = data;
left = right = null;
}
public BinTree(Object data,BinTree left,BinTree right)
{ //构造有值结点
this.data = data;
this.left = left;
this.right = right;
}
public String toString()
{
return data.toString();
}
//前序遍历二叉树
public static void preOrder(BinTree parent){
if(parent == null)
return;
System.out.print(parent.data+" ");
preOrder(parent.left);
preOrder(parent.right);
}
//中序遍历二叉树
public void inOrder(BinTree parent){
if(parent == null)
return;
inOrder(parent.left);
System.out.print(parent.data+" ");
inOrder(parent.right);
}
//后序遍历二叉树
public void postOrder(BinTree parent){
if(parent == null)
return;
postOrder(parent.left);
postOrder(parent.right);
System.out.print(parent.data+" ");
}
// 层次遍历二叉树
public void LayerOrder(BinTree parent)
{
elements[0]=parent;
front=0;rear=1;
while(frontrear)
{
try
{
if(elements[front].data!=null)
{
System.out.print(elements[front].data + " ");
if(elements[front].left!=null)
elements[rear++]=elements[front].left;
if(elements[front].right!=null)
elements[rear++]=elements[front].right;
front++;
}
}catch(Exception e){break;}
}
}
//返回树的叶节点个数
public int leaves()
{
if(this == null)
return 0;
if(left == nullright == null)
return 1;
return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());
}
//结果返回树的高度
public int height()
{
int heightOfTree;
if(this == null)
return -1;
int leftHeight = (left == null ? 0 : left.height());
int rightHeight = (right == null ? 0 : right.height());
heightOfTree = leftHeightrightHeight?rightHeight:leftHeight;
return 1 + heightOfTree;
}
//如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层
public int level(Object object)
{
int levelInTree;
if(this == null)
return -1;
if(object == data)
return 1;//规定根节点为第一层
int leftLevel = (left == null?-1:left.level(object));
int rightLevel = (right == null?-1:right.level(object));
if(leftLevel0rightLevel0)
return -1;
levelInTree = leftLevelrightLevel?rightLevel:leftLevel;
return 1+levelInTree;
}
//将树中的每个节点的孩子对换位置
public void reflect()
{
if(this == null)
return;
if(left != null)
left.reflect();
if(right != null)
right.reflect();
BinTree temp = left;
left = right;
right = temp;
}
// 将树中的所有节点移走,并输出移走的节点
public void defoliate()
{
if(this == null)
return;
//若本节点是叶节点，则将其移走
if(left==nullright == null)
{
System.out.print(this + " ");
data = null;
return;
}
//移走左子树若其存在
if(left!=null){
left.defoliate();
left = null;
}
//移走本节点，放在中间表示中跟移走...
String innerNode += this + " ";
data = null;
//移走右子树若其存在
if(right!=null){
right.defoliate();
right = null;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinTree e = new BinTree("E");
BinTree g = new BinTree("G");
BinTree h = new BinTree("H");
BinTree i = new BinTree("I");
BinTree d = new BinTree("D",null,g);
BinTree f = new BinTree("F",h,i);
BinTree b = new BinTree("B",d,e);
BinTree c = new BinTree("C",f,null);
BinTree tree = new BinTree("A",b,c);
System.out.println("前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍历二叉树结果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍历二叉树结果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的层次: "+tree.level("F"));
System.out.println("这棵二叉树的高度: "+tree.height());
System.out.println("--------------------------------------");
tree.reflect();
System.out.println("交换每个节点的孩子节点后......");
System.out.println("前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍历二叉树结果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍历二叉树结果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的层次: "+tree.level("F"));
System.out.println("这棵二叉树的高度: "+tree.height());
}
java 用递归创建二叉树，非递归遍历二叉树输出节点
我自己用递归写了下，不知道能不能给你帮助：
测试类：
package tree;
import java.util.*;
public class Test {
public static void main(String[] args){
ListTree trees=new ArrayListTree();
int id=1;
Tree tree1=new Tree(0,id++,"张三丰");
Tree tree2=new Tree(tree1.getId(),id++,"武当宋大侠宋远桥");
Tree tree3=new Tree(tree1.getId(),id++,"武当俞二侠俞莲舟");
Tree tree4=new Tree(tree1.getId(),id++,"武当俞三侠俞岱岩");
Tree tree5=new Tree(tree1.getId(),id++,"武当张四侠张松溪");
Tree tree6=new Tree(tree1.getId(),id++,"武当张五侠张翠山");
Tree tree7=new Tree(tree1.getId(),id++,"武当殷六侠殷梨亭");
Tree tree8=new Tree(tree1.getId(),id++,"武当莫七侠莫声谷");
Tree tree9=new Tree(tree6.getId(),id++,"明教张无忌");
Tree tree13=new Tree(tree2.getId(),id++,"叛徒宋青书");
Tree tree10=new Tree(0,id++,"任我行");
Tree tree11=new Tree(tree10.getId(),id++,"令狐冲");
Tree tree12=new Tree(tree10.getId(),id++,"任盈盈");
trees.add(tree1);
trees.add(tree2);
trees.add(tree3);
trees.add(tree4);
trees.add(tree5);
trees.add(tree6);
trees.add(tree7);
trees.add(tree8);
trees.add(tree9);
trees.add(tree10);
trees.add(tree11);
trees.add(tree12);
trees.add(tree13);
for(int i=0;itrees.size();i++){
Tree tree=trees.get(i);
if(tree.getParentId()==0){
tree.showChildTree(trees);
}
}
}
}
树类：
package tree;
import java.util.List;
public class Tree {
private int parentId;
private int id;
private String showStr;
private String Spaces="";
public Tree() {
// TODO Auto-generated constructor stub
}
public Tree(int parentId,int id,String showStr){
this.parentId=parentId;
this.id=id;
this.showStr=showStr;
}
public void showChildTree(ListTree trees){
if(parentId!=0){
trees.get(id-1).setSpaces(trees.get(parentId-1).getSpaces()+" ");
}
System.out.println(trees.get(id-1).getSpaces()+showStr);
for(int i=0;itrees.size();i++){
Tree tree=trees.get(i);
if(tree.getParentId()==id){
tree.showChildTree(trees);
}
}
}
public int getParentId() {
return parentId;
}
public void setParentId(int parentId) {
this.parentId = parentId;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getShowStr() {
return showStr;
}
public void setShowStr(String showStr) {
this.showStr = showStr;
}
public String getSpaces() {
return Spaces;
}
public void setSpaces(String spaces) {
Spaces = spaces;
}
}
效果图：
张三丰
武当宋大侠宋远桥
叛徒宋青书
武当俞二侠俞莲舟
武当俞三侠俞岱岩
武当张四侠张松溪
武当张五侠张翠山
明教张无忌
武当殷六侠殷梨亭
武当莫七侠莫声谷
任我行
令狐冲
任盈盈
用JAVA语言实现二叉树的层次遍历的非递归算法及查找算法。
分块查找
typedef struct
{ int key;
int link;
}SD;
typedef struct
{ int key;
float info;
}JD;
int blocksrch(JD r[],SD nd[],int b,int k,int n)
{ int i=1,j;
while((knd[i].key)(i=b) i++;
if(ib) { printf("\nNot found");
return(0);
}
j=nd[i].link;
while((jn)(k!=r[j].key)(r[j].key=nd[i].key))
j++;
if(k!=r[j].key) { j=0; printf("\nNot found"); }
return(j);
}
哈希查找算法实现
#define M 100
int h(int k)
{ return(k%97);
}
int slbxxcz(int t[],int k)
{ int i,j=0;
i=h(k);
while((jM)(t[(i+j)%M]!=k)(t[(i+j}%M]!=0))
j++;
i=(i+j)%M;
if(t[i]==k) return(i);
else return(-1);
}
int slbxxcr(int t[],int k)
{ int i,j=0;
i=h(k);
while((jM)(t[(i+j)%M]!=k)(t[(i+j}%M]0))
j++;
if(j==M) return(0);
i=(i+j)%M;
if(t[i]=0)
{ t[i]=k; return(1); }
if(t[i]==k) return(1);
}
int slbxxsc(int t[],int k)
{ int i,j=0;
i=h(k);
while((jM)(t[(i+j)%M]!=k)(t[(i+j}%M]!=0))
j++;
i=(i+j)%M;
if(t[i]==k)
{ t[i]=-1; return(1); }
return(0);
}
顺序查找
#define M 500
typedef struct
{ int key;
float info;
}JD;
int seqsrch(JD r[],int n,int k)
{ int i=n;
r[0].key=k;
while(r[i].key!=k)
i--;
return(i);
}
折半查找
int binsrch(JD r[],int n,int k)
{ int low,high,mid,found;
low=1; high=n; found=0;
while((low=high)(found==0))
{ mid=(low+high)/2;
if(kr[mid].key) low=mid+1;
else if(k==r[mid].key) found=1;
else high=mid-1;
}
if(found==1)
return(mid);
else
return(0);
}
虽然都是C++写的，万变不离其中，JAVA我现在 刚学习，就不献丑了
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;iinput.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如何创建一颗二叉树
计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。
树是由一个或多个结点组成的有限集合，其中：
⒈必有一个特定的称为根(ROOT)的结点；
二叉树
⒉剩下的结点被分成n=0个互不相交的集合T1、T2、......Tn，而且， 这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。
树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树
1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为2;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。
2.树的深度——组成该树各结点的最大层次。
3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林；
4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。
树的表示
树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如右图可写成如下形式：
二叉树
(a( b(d,e), c( f( ,g(h,i) ), )))
关于java非二叉树和java实现二叉树非递归遍历的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。