「java树算法」java树算法题

博主：adminadmin 2022-11-28 05:10:07 57

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

本文目录一览：

如何用Java实现树形结构啊？

package tree;

import java.util.LinkedList;

import java.util.List;

/**

* 功能：把一个数组的值存入二叉树中，然后进行3种方式的遍历

*

* 参考资料0:数据结构(C语言版)严蔚敏

*

* 参考资料1：

*

* 参考资料2：

*

* @author ocaicai@yeah.net @date: 2011-5-17

*

*/

public class BinTreeTraverse2 {

private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

private static ListNode nodeList = null;

/**

* 内部类：节点

*

* @author ocaicai@yeah.net @date: 2011-5-17

*

*/

private static class Node {

Node leftChild;

Node rightChild;

int data;

Node(int newData) {

leftChild = null;

rightChild = null;

data = newData;

}

}

public void createBinTree() {

nodeList = new LinkedListNode();

// 将一个数组的值依次转换为Node节点

for (int nodeIndex = 0; nodeIndex array.length; nodeIndex++) {

nodeList.add(new Node(array[nodeIndex]));

}

// 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树

for (int parentIndex = 0; parentIndex array.length / 2 - 1; parentIndex++) {

// 左孩子

nodeList.get(parentIndex).leftChild = nodeList

.get(parentIndex * 2 + 1);

// 右孩子

nodeList.get(parentIndex).rightChild = nodeList

.get(parentIndex * 2 + 2);

}

// 最后一个父节点:因为最后一个父节点可能没有右孩子，所以单独拿出来处理

int lastParentIndex = array.length / 2 - 1;

// 左孩子

nodeList.get(lastParentIndex).leftChild = nodeList

.get(lastParentIndex * 2 + 1);

// 右孩子,如果数组的长度为奇数才建立右孩子

if (array.length % 2 == 1) {

nodeList.get(lastParentIndex).rightChild = nodeList

.get(lastParentIndex * 2 + 2);

}

}

/**

* 先序遍历

*

* 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已

*

* @param node

* 遍历的节点

*/

public static void preOrderTraverse(Node node) {

if (node == null)

return;

System.out.print(node.data + " ");

preOrderTraverse(node.leftChild);

preOrderTraverse(node.rightChild);

}

/**

* 中序遍历

*

* 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已

*

* @param node

* 遍历的节点

*/

public static void inOrderTraverse(Node node) {

if (node == null)

return;

inOrderTraverse(node.leftChild);

System.out.print(node.data + " ");

inOrderTraverse(node.rightChild);

}

/**

* 后序遍历

*

* 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已

*

* @param node

* 遍历的节点

*/

public static void postOrderTraverse(Node node) {

if (node == null)

return;

postOrderTraverse(node.leftChild);

postOrderTraverse(node.rightChild);

System.out.print(node.data + " ");

}

public static void main(String[] args) {

BinTreeTraverse2 binTree = new BinTreeTraverse2();

binTree.createBinTree();

// nodeList中第0个索引处的值即为根节点

Node root = nodeList.get(0);

System.out.println("先序遍历：");

preOrderTraverse(root);

System.out.println();

System.out.println("中序遍历：");

inOrderTraverse(root);

System.out.println();

System.out.println("后序遍历：");

postOrderTraverse(root);

}

}

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 二叉树前序遍历

//类Node定义二叉树结点的数据结构;

//一个结点应包含结点值，左子结点的引用和右子结点的引用

class Node{

public Node left; //左子结点

public Node right; //右子结点

public int value; //结点值

public Node(int val){

value = val;

}

}

public class Traversal

{

//read()方法将按照前序遍历的方式遍历输出二叉树的结点值

//此处采用递归算法会比较简单，也容易理解，当然也可以用

//循环的方法遍历，但会比较复杂，也比较难懂。二叉树遍历

//用递归算法最为简单，因为每个结点的遍历方式都是，根，

//左，右，递归的调用可以让每个结点以这种方式遍历

public static void read(Node node){

if(node != null){

System.out.println(node.value);//输出当前结点的值

if(node.left != null)

read(node.left); //递归调用 先读左结点

if(node.right != null)

read(node.right); //递归调用 后读右结点

}

}

public static void main(String[] args){

//初始化5个结点，分别初始值为1，2，3，4，5

Node n1 = new Node(1);

Node n2 = new Node(2);

Node n3 = new Node(3);

Node n4 = new Node(4);

Node n5 = new Node(5);

//构建二叉树，以n1为根结点

n1.left = n2;

n1.right = n5;

n2.left = n3;

n2.right = n4;

read(n1);

}

}

注释和代码都是我自己写的，如果楼主觉得有的注释多余可以自己删除一些！代码我都编译通过，并且运行结果如你提的要求一样！你只要把代码复制编译就可以了，注意要以文件名Traversal.java来保存，否则编译不通过，因为main函数所在的类是public类型的！

(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语言实现二叉树的层次遍历的非递归算法及查找算法。

分块查找

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二叉树中序遍历 的递归算法没有看懂。。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树算法题、java树算法的信息别忘了在本站进行查找喔。

The End

发布于：2022-11-28，除非注明，否则均为首码项目网原创文章，转载请注明出处。

标签：