用java怎么构造一个二叉树呢？

学数据结构时用的是C，用链表构造二叉树，但大家都懂的，java中不可以自己做指针（内存分配）这部分，那么怎么构造一个二叉树呢？... 学数据结构时用的是C，用链表构造二叉树，但大家都懂的，java中不可以自己做指针（内存分配）这部分，那么怎么构造一个二叉树呢？展开

 我来答

3个回答

#合辑# 面试问优缺点怎么回答最加分？

小傻

推荐于2017-10-15 · 知道合伙人软件行家

小傻
知道合伙人软件行家

采纳数：11567 获赞数：31134

已经做过两个上架的app和两个网页项目.

向TA提问私信TA

关注

展开全部

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(front<rear)
   {
    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 == null&&right == 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 = leftHeight<rightHeight?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(leftLevel<0&&rightLevel<0)
    return -1;
   levelInTree = leftLevel<rightLevel?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==null&&right == 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());
}

已赞过 已踩过<

评论收起

kejiaweiren
推荐于2017-09-28 · TA获得超过6740个赞

知道大有可为答主

回答量：1774

采纳率：0%

帮助的人：3353万

我也去答题访问个人页

关注

展开全部

二叉树的相关操作，包括创建，中序、先序、后序（递归和非递归），其中重点的是java在先序创建二叉树和后序非递归遍历的的实现。
package com.algorithm.tree;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

public class Tree<T> {

	private Node<T> root;
	
	public Tree() {
	}
	
	public Tree(Node<T> root) {
		this.root = root;
	}
	
	//创建二叉树
	public void buildTree() {
		
		Scanner scn = null;
		try {
			scn = new Scanner(new File("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		root = createTree(root,scn);		
	}
	//先序遍历创建二叉树
	private Node<T> createTree(Node<T> node,Scanner scn) {
		
		String temp  = scn.next();
		
		if (temp.trim().equals("#")) {
			return null;
		} else {
			node = new Node<T>((T)temp);
			node.setLeft(createTree(node.getLeft(), scn));
			node.setRight(createTree(node.getRight(), scn));
			return node;
		}
			
	}

//中序遍历(递归)
	public void inOrderTraverse() {
		inOrderTraverse(root);
	}
	
	public void inOrderTraverse(Node<T> node) {
		if (node != null) {
			inOrderTraverse(node.getLeft());
			System.out.println(node.getValue());
			inOrderTraverse(node.getRight());
		}
	}

//中序遍历(非递归)
	public void nrInOrderTraverse() {
		
		Stack<Node<T>> stack = new Stack<Node<T>>();
		Node<T> node = root;
		while (node != null || !stack.isEmpty()) {
			while (node != null) {
				stack.push(node);
				node = node.getLeft();
			}
			node = stack.pop();
			System.out.println(node.getValue());
			node = node.getRight();
			
		}
				
	}
	//先序遍历(递归)
	public void preOrderTraverse() {
		preOrderTraverse(root);
	}
	
	public void preOrderTraverse(Node<T> node) {
		if (node != null) {
			System.out.println(node.getValue());
			preOrderTraverse(node.getLeft());
			preOrderTraverse(node.getRight());
		}
	}

//先序遍历（非递归）
	public void nrPreOrderTraverse() {
		
		Stack<Node<T>> stack = new Stack<Node<T>>();
		Node<T> node = root;
		
		while (node != null || !stack.isEmpty()) {
			
			while (node != null) {
				System.out.println(node.getValue());
				stack.push(node);
				node = node.getLeft();
			}
			node = stack.pop();
			node = node.getRight();
		}
				
	}
	
	//后序遍历(递归)
	public void postOrderTraverse() {
		postOrderTraverse(root);
	}
	
	public void postOrderTraverse(Node<T> node) {
		if (node != null) {
			postOrderTraverse(node.getLeft());
			postOrderTraverse(node.getRight());
			System.out.println(node.getValue());
		}
	}
	
	//后续遍历(非递归)
	public void nrPostOrderTraverse() {
		
		Stack<Node<T>> stack = new Stack<Node<T>>();
		Node<T> node = root;
		Node<T> preNode = null;//表示最近一次访问的节点
		
		while (node != null || !stack.isEmpty()) {
			
			while (node != null) {
				stack.push(node);
				node = node.getLeft();
			}
			
			node = stack.peek();
			
			if (node.getRight() == null || node.getRight() == preNode) {
				System.out.println(node.getValue());
				node = stack.pop();
				preNode = node;
				node = null;
			} else {
				node = node.getRight();
			}
			
		}

}
	
	//按层次遍历
	public void levelTraverse() {
		levelTraverse(root);
	}
	
	public void levelTraverse(Node<T> node) {
	
		Queue<Node<T>> queue = new LinkedBlockingQueue<Node<T>>();
		queue.add(node);
		while (!queue.isEmpty()) {
			
			Node<T> temp = queue.poll();
			if (temp != null) {
				System.out.println(temp.getValue());
				queue.add(temp.getLeft());
				queue.add(temp.getRight());
			}
						
		}
				
	}

}

//树的节点

class Node<T> {
	
	private Node<T> left;
	private Node<T> right;
	private T value;
	
	public Node() {
	}
	public Node(Node<T> left,Node<T> right,T value) {
		this.left = left;
		this.right = right;
		this.value = value;
	}
	
	public Node(T value) {
		this(null,null,value);
	}
	public Node<T> getLeft() {
		return left;
	}
	public void setLeft(Node<T> left) {
		this.left = left;
	}
	public Node<T> getRight() {
		return right;
	}
	public void setRight(Node<T> right) {
		this.right = right;
	}
	public T getValue() {
		return value;
	}
	public void setValue(T value) {
		this.value = value;
	}
		
}
测试代码：
package com.algorithm.tree;

public class TreeTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Tree<Integer> tree = new Tree<Integer>();
		tree.buildTree();
		System.out.println("中序遍历");
		tree.inOrderTraverse();
		tree.nrInOrderTraverse();
		System.out.println("后续遍历");
		//tree.nrPostOrderTraverse();
		tree.postOrderTraverse();
		tree.nrPostOrderTraverse();
		System.out.println("先序遍历");
		tree.preOrderTraverse();
		tree.nrPreOrderTraverse();
		
//
	}

}


本回答被提问者和网友采纳






已赞过已踩过<

你对这个回答的评价是？
评论收起

百度网友23bba7f0
2015-09-14 · TA获得超过4173个赞

知道小有建树答主

回答量：660

采纳率：85%

帮助的人：185万

我也去答题访问个人页

关注

展开全部

定义一个结点类：
public class Node {
private int value;
private Node leftNode;
private Node rightNode;

public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}

}

初始化结点树：
public void initNodeTree()
{
int nodeNumber;
HashMap<String, Integer> map = new HashMap<String, Integer>();
Node nodeTree = new Node();

Scanner reader = new Scanner(System.in);

nodeNumber = reader.nextInt();
for(int i = 0; i < nodeNumber; i++) {
int value = reader.nextInt();
String str = reader.next();
map.put(str, value);
}

if (map.containsKey("#")) {
int value = map.get("#");
nodeTree.setValue(value);
setChildNode(map, value, nodeTree);
}

preTraversal(nodeTree);
}

private void setChildNode(HashMap<String, Integer> map, int nodeValue, Node parentNode) {
int value = 0;
if (map.containsKey("L" + nodeValue)) {
value = map.get("L" + nodeValue);
Node leftNode = new Node();
leftNode.setValue(value);
parentNode.setLeftNode(leftNode);

setChildNode(map, value, leftNode);
}

if (map.containsKey("R" + nodeValue)) {
value = map.get("R" + nodeValue);
Node rightNode = new Node();
rightNode.setValue(value);
parentNode.setRightNode(rightNode);

setChildNode(map, value, rightNode);
}
}

前序遍历该结点树：
public void preTraversal(Node nodeTree) {
if (nodeTree != null) {
System.out.print(nodeTree.getValue() + "\t");
preTraversal(nodeTree.getLeftNode());
preTraversal(nodeTree.getRightNode());
}
}

已赞过 已踩过<

评论收起

更多回答（1）

推荐律师服务：若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询

您可能关注的内容

超级码客~2025版海量5000道Java面试题+笔试题&答案

超级码客涵盖高级java面试海量Java面试题#Java语言，多线程，Java框架，Java高并发等超4500题

www.chaojimake.cn广告

java 前端技术Java工程师2024革新版，高薪就业加速器!

java 前端技术从零到高阶，39周课程铺就高薪成长路，大厂讲师亲自授课，7年迭代精品课java 前端技术实战项目+源码解析+性能调优，全面打造高薪竞争力，18个月教学服务

m.imooc.com广告

用java怎么构造一个二叉树呢？

您可能关注的内容

其他类似问题

为你推荐：