「java遍历树算法」java遍历结果集

本篇文章给大家谈谈java遍历树算法，以及java遍历结果集对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、java构建二叉树算法
• 2、(java)有一个100000个节点的树形结构，求所有节点数大于L=3小于R=5的路径的组合，有什么效率高的方法吗？
• 3、java实现二叉树层次遍历
• 4、求Java List 递归算法..

java构建二叉树算法

//******************************************************************************************************//

//*****本程序包括简单的二叉树类的实现和前序,中序,后序,层次遍历二叉树算法,*******//

//******以及确定二叉树的高度,制定对象在树中的所处层次以及将树中的左右***********//

//******孩子节点对换位置,返回叶子节点个数删除叶子节点,并输出所删除的叶子节点**//

//*******************************CopyRight By phoenix*******************************************//

//************************************Jan 12,2008*************************************************//

//****************************************************************************************************//

public class BinTree {

public final static int MAX=40;

private Object data; //数据元数

private BinTree left,right; //指向左,右孩子结点的链

BinTree []elements = new BinTree[MAX];//层次遍历时保存各个节点

int front;//层次遍历时队首

int rear;//层次遍历时队尾

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()

{

String innerNode = "";

if(this == null)

return;

//若本节点是叶节点，则将其移走

if(left==nullright == null)

{

System.out.print(this + " ");

data = null;

return;

}

//移走左子树若其存在

if(left!=null){

left.defoliate();

left = null;

}

//移走本节点，放在中间表示中跟移走...

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)有一个100000个节点的树形结构，求所有节点数大于L=3小于R=5的路径的组合，有什么效率高的方法吗？

如果采用非递归算法实现二叉树的前序遍历，需要借助于栈结构。其步骤如下：

如果根节点rt为空，则返回；否则，首先将根节点压入栈中，然后迭代执行以下步骤：

1. 弹出栈顶存放的节点n，访问该节点；

2. 依次将n的右子节点和左子节点压入栈中；

3. 如果栈不为空，则返回步骤1继续执行，否则结束迭代。

其中步骤1为节点访问操作；步骤2中先将右子节点压入栈中然后再将左子节点压入，这是因为在栈的弹出操作服从先入后出的准则，根节点访问结束后需要先访问的是左子节点，所以左子节点在右子节点之后压栈；步骤3是遍历过程终止的条件。

根据上述迭代步骤，图中二叉树的遍历步骤可以分解为如下步骤，对应如图所示。

1． 将n14压栈；

2． 弹出栈顶节点，此时为n14，访问节点n14；

3． 将n14的右子节点n13和左子节点n8依次压入栈中；

4． 弹出栈顶节点，此时为n8，访问节点n8；

5． 将n8的右子节点n7和左子节点n4依次压入栈中；

6． 弹出栈顶节点，此时为n4，访问节点n4；

7． 将n4的右子节点n3和左子节点n2依次压入栈中；

8． 弹出栈顶节点，此时为n2，访问节点n2；

9． n2的右子节点为空，则将n2的左子节点n1压入栈中；

10．弹出栈顶节点，此时为n1，访问节点n1；

11．n1的左子节点为空，则将n1的右子节点n0压入栈中；

12．弹出栈顶节点，此时为n0，访问节点n0；

13．n0为叶节点，则无子节点压栈；

14．弹出栈顶节点，此时为n3，访问节点n3；

15．n3为叶节点，则无子节点压栈；

16．弹出栈顶节点，此时为n7，访问节点n7；

17．将n7的右子节点n6和左子节点n5依次压栈；

18．弹出栈顶节点，此时为n5，访问节点n5；

19．n5为叶节点，无子节点压栈；

20．弹出栈顶节点，此时为n6，访问节点n6；

21．n6为叶节点，无子节点压栈；

22．弹出栈顶节点，此时为n13，访问节点n13；

23．将n13的右子节点n11和左子节点n12依次压栈；

24．弹出栈顶节点，此时为n12，访问节点n12；

25．n12为叶节点，无子节点压栈；

26．弹出栈顶节点，此时为n11，访问节点n11；

27．将n11的右子节点n10和左子节点n9依次压入栈中；

28．弹出栈顶节点，此时为n9，访问节点n9；

29．n9为叶节点，则无子节点压栈；

30．弹出栈顶节点，此时为n10，访问节点n10；

31．n10为叶节点，则无子节点压栈；

32．栈空，遍历过程结束。

图 二叉树前序遍历算法栈结构动态过程

迭代过称中利用了栈结构，图示的栈结构中栈的大小是固定的，事实上在实现时预先设定好栈的大小并不容易，所以在具体实现时，采用第XX章中讨论的链式栈，动态调整栈的大小。

中序遍历

第二种遍历算法称为中序遍历算法。与前序遍历算法相比，中序遍历算法首先访问节点的左子树，然后访问节点自身，最后访问节点的右子树。可见，节点自身是在访问左右子树中间访问的，顾称之为中序。图中的二叉树的中序遍历结果为：

java实现二叉树层次遍历

import java.util.ArrayList;

public class TreeNode {

private TreeNode leftNode;

private TreeNode rightNode;

private String nodeName;

public TreeNode getLeftNode() {

return leftNode;

}

public void setLeftNode(TreeNode leftNode) {

this.leftNode = leftNode;

}

public TreeNode getRightNode() {

return rightNode;

}

public void setRightNode(TreeNode rightNode) {

this.rightNode = rightNode;

}

public String getNodeName() {

return nodeName;

}

public void setNodeName(String nodeName) {

this.nodeName = nodeName;

}

public static int level=0;

public static void findNodeByLevel(ArrayListTreeNode nodes){

if(nodes==null||nodes.size()==0){

return ;

}

level++;

ArrayListTreeNode temp = new ArrayList();

for(TreeNode node:nodes){

System.out.println("第"+level+"层:"+node.getNodeName());

if(node.getLeftNode()!=null){

temp.add(node.getLeftNode());

}

if(node.getRightNode()!=null){

temp.add(node.getRightNode());

}

}

nodes.removeAll(nodes);

findNodeByLevel(temp);

}

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

TreeNode root = new TreeNode();

root.setNodeName("root");

TreeNode node1 = new TreeNode();

node1.setNodeName("node1");

TreeNode node3 = new TreeNode();

node3.setNodeName("node3");

TreeNode node7 = new TreeNode();

node7.setNodeName("node7");

TreeNode node8 = new TreeNode();

node8.setNodeName("node8");

TreeNode node4 = new TreeNode();

node4.setNodeName("node4");

TreeNode node2 = new TreeNode();

node2.setNodeName("node2");

TreeNode node5 = new TreeNode();

node5.setNodeName("node5");

TreeNode node6 = new TreeNode();

node6.setNodeName("node6");

root.setLeftNode(node1);

node1.setLeftNode(node3);

node3.setLeftNode(node7);

node3.setRightNode(node8);

node1.setRightNode(node4);

root.setRightNode(node2);

node2.setLeftNode(node5);

node2.setRightNode(node6);

ArrayListTreeNode nodes = new ArrayListTreeNode();

nodes.add(root);

findNodeByLevel(nodes);

}

}

求Java List 递归算法..

无需JAVA递归取！

从设计角度看，表结构设计已经有问题了！

即使是树状结构，为何表结构没有体现？这也构成了为何楼主需要想办法来应对非树状结构数据的树状显示问题。

先进一步来说，表加一个grade字段，来表明当前记录处于第几级。那么直接一个SQL就可以取出来：

select lpad(' ',a.grade,'-')||a.name from myList a

这样就可以按楼主需要的结构取出数据；

但还存在一个问题，就是顺序问题，这样取出的数据是无序的！

那么我们再进一步看，我在做这种数据结构的表设计时，往往会给每个结点增加两个字段，left/right，分别代表其在树中的左右值。

这样就可以在上面SQL后增加order by a.left以保证取出数据的顺序。

关于java遍历树算法和java遍历结果集的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。