二叉树在Java中有两种方法可以实现，用数组实现和用链表实现，本篇主要讲这两个方法：
一、数组实现二叉树，缺点是浪费空间，代码如下：
package offer.tree;
/**
* Created by Taoyongpan on 2017/10/15.
* 二叉树的创建和一般操作
* 数组实现二叉树，浪费很多的内存空间
* 左孩子下标 = 父节点下标*2
* 右孩子下标 = 父节点下标*2+1
*/
public class TreeDemo {
// int root = 1;
int btree[];
private int root = 1;
private int leftchild;
private int rightchild;
public TreeDemo(int data){
btree = new int[16];
btree[1] = data;
}
//新增
public void add(int data){
int root =1;
while (btree[root]!=0){
if (btree[root]>=data){
root = root*2;
}else {
root = root*2+1;
}
}
btree[root] = data;
}
//遍历
public void display(){
for (int i = 1 ; i<btree.length;i++){
System.out.println("btree["+i+"]="+btree[i]);
}
}
//删除
public void del(int data){
int root = 1;
while (btree[root]!=data){
if (btree[root]>data){
root = root*2;
}else if (btree[root]<data){
root = root*2+1;
}
}
btree[root] = 0;
}
//查找
public int query(int data){
int root = 1;
while (btree[root]!=data){
if (btree[root]>data){
root = root*2;
}else if (btree[root]<data){
root = root*2+1;
}
}
return root;
}
public static void main(String[] args){
TreeDemo tree = new TreeDemo(10);
tree.add(8);
tree.add(7);
tree.add(11);
tree.add(3);
tree.add(20);
tree.display();
tree.del(3);
tree.display();
}
}
二、用链表实现，代码如下：
package offer.tree;
/**
* Created by Taoyongpan on 2017/10/15.
* 链表实现二叉树
*/
public class TreeNode {
int data;
TreeNode leftchild;
TreeNode rightchild;
//初始化
public TreeNode(){
data = 0;
leftchild = null;
rightchild =null;
}
//新增节点
public TreeNode(int data){
this.data = data;
leftchild = null;
rightchild =null;
}
}
package offer.tree;
import java.util.*;
/**
* Created by Taoyongpan on 2017/10/15.
* 前序遍历 ：根节点，左节点，右节点
* 中序遍历：左节点，根节点，右节点
* 后序遍历：左节点，右节点，根节点
*/
public class TreeLink {
TreeNode root = null;
//创建根节点
public TreeLink(int data){
root = new TreeNode(data);
}
//创建节点
public void add(int data){
TreeNode d = new TreeNode(data);
TreeNode p = root;
while (p!=null){
if (p.data>=d.data){
//往左走
if (p.leftchild!=null){
p = p.leftchild;
}else {
p.leftchild=d;
break;
}
}else {
//往右走
if (p.rightchild!=null){
p = p.rightchild;
}else {
p.rightchild = d;
break;
}
}
}
}
//前序遍历
public void display(TreeNode root){
TreeNode p = root;
System.out.println("p.data="+p.data);
if (p.leftchild!=null){
display(p.leftchild);
}
if (p.rightchild!=null){
display(p.rightchild);
}
}
//递归版前序遍历
public static List<Integer> preorderRecursively(TreeNode root){
List<Integer> tree = new ArrayList<>();
if (root==null){
return tree;
}
tree.add(root.data);
tree.addAll(preorderRecursively(root.leftchild));
tree.addAll(preorderRecursively(root.rightchild));
return tree;
}
//递归版中序遍历
public static List<Integer> inorderRecursively(TreeNode root){
List<Integer> tree = new ArrayList<>();
if (root==null){
return tree;
}
tree.addAll(inorderRecursively(root.leftchild));
tree.add(root.data);
tree.addAll(inorderRecursively(root.rightchild));
return tree;
}
//递归版后序遍历
public static List<Integer> postorderRecursively(TreeNode root){
List<Integer> tree = new ArrayList<>();
if (root==null){
return tree;
}
tree.addAll(postorderRecursively(root.leftchild));
tree.addAll(postorderRecursively(root.rightchild));
tree.add(root.data);
return tree;
}
//非递归版本前序遍历
public static List<Integer> preorderIteratively(TreeNode root){
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
TreeNode p = root;
if (root == null){
return list;
}
while (p!=null||!stack.isEmpty()){
if (p!=null){
list.add(p.data);
stack.push(p);
p = p.leftchild;
}else {
p = stack.pop().rightchild;
}
}
return list;
}
//非递归版本中序遍历
public static List<Integer> inorderIteratively(TreeNode root){
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
TreeNode p = root;
while (p!=null||!stack.isEmpty()){
if (p!=null){
stack.push(p);
p = p.leftchild;
}else {
list.add(stack.peek().data);
p = stack.pop().rightchild;
}
}
return list;
}
//非递归版后序遍历
public static List<Integer> postorderIteratively(TreeNode root){
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
TreeNode p = root;
TreeNode d = null;
while (p!=null||!stack.isEmpty()){
if (p!=null){
stack.push(p);
p = p.leftchild;
}else {
p = stack.peek().rightchild;
if (p!=null&&d!=p){
stack.push(p);
p = p.leftchild;
}else {
d = stack.pop();
list.add(d.data);
p = null;
}
}
}
return list;
}
//层序遍历
public static List<Integer> levelorder(TreeNode root){
Queue<TreeNode> queue = new LinkedList<>();
TreeNode p = null;
List<Integer> list = new LinkedList<>();
if (root==null){
return null;
}
queue.offer(root);
while (!queue.isEmpty()){
p = queue.poll();
list.add(p.data);
if (p.leftchild!=null){
queue.offer(p.leftchild);
}
if (p.rightchild!=null){
queue.offer(p.rightchild);
}
}
return list;
}
//主函数
public static void main(String[] args){
TreeLink tree = new TreeLink(10);
tree.add(8);
tree.add(11);
tree.add(20);
tree.add(7);
tree.add(3);
//递归版前序遍历
tree.display(tree.root);
//递归版前序遍历
System.out.println("递归版本前序遍历：");
List<Integer> list = preorderRecursively(tree.root);
for (int i = 0 ; i<list.size();i++){
System.out.println(list.get(i));
}
//递归版中序遍历
System.out.println("递归版本中序遍历：");
List<Integer> list1 = inorderRecursively(tree.root);
for (int i = 0 ; i<list1.size();i++){
System.out.println(list1.get(i));
}
//递归版后序遍历
System.out.println("递归版本后序遍历：");
List<Integer> list2 = postorderRecursively(tree.root);
for (int i = 0 ; i<list2.size();i++){
System.out.println(list2.get(i));
}
//非递归版本前序遍历
System.out.println("非递归版本前序遍历：");
List<Integer> list3 = preorderIteratively(tree.root);
for (int i = 0 ; i<list3.size();i++){
System.out.println(list3.get(i));
}
//非递归版本中序遍历
System.out.println("非递归版本中序遍历：");
List<Integer> list4 = inorderIteratively(tree.root);
for (int i = 0 ; i<list4.size();i++){
System.out.println(list4.get(i));
}
//非递归版本后序遍历
System.out.println("非递归版本后序遍历：");
List<Integer> list5 = postorderIteratively(tree.root);
for (int i = 0 ; i<list5.size();i++){
System.out.println(list5.get(i));
}
//层序遍历
System.out.println("非递归版本后序遍历：");
List<Integer> list6 = levelorder(tree.root);
for (int i = 0 ; i<list6.size();i++){
System.out.println(list6.get(i));
}
}
}
相关推荐
java二叉树实现 （简单实现，入门用） /**创建二叉树*/ public BinaryTree createTree(String treeStr); /**寻找结点*/ public BinaryTree findNode(BinaryTree tree ,char sign); /**找所给结点的左子树*/ ...
二叉树的java实现
标题“利用二叉树实现多项式计算”明确指出本文将探讨如何通过构建二叉树来实现对多项式的运算处理。 #### 描述解读： 描述部分提到该资源为txt文本，内容包括实现思路与具体代码实现，仅供学习参考使用，不得用于...
在这个Java实现中，我们可以看到一个完整的二叉树可视化系统，包括四个关键的Java源文件：BinaryNode、Show1_12、Display_Tree和TreeControl。 1. **BinaryNode.java**: 这个文件代表二叉树的基本节点。在Java中，...
在本话题中，我们将深入探讨Java中二叉树的插入、删除操作以及遍历方法。 1. **二叉树的基本概念**： - **根节点**：二叉树中的顶级节点，没有父节点。 - **子节点**：由一个节点指向另一个节点的连接，指向的...
这篇博客"java二叉树算法（转）"可能会探讨如何在Java中实现和操作二叉树，特别是涉及算法的部分。二叉树通常用于搜索、排序和组织数据，其特性是每个节点最多有两个子节点，通常分为左子节点和右子节点。 二叉树的...
java实现二叉树非递归前序中序后序遍历
以下是对"java二叉树"这个主题的详细解析。 首先，我们要理解二叉树的基本操作： 1. 插入节点：在二叉树中插入新节点时，需要遵循二叉树的规则，即新节点只能作为现有节点的左孩子或右孩子。插入操作取决于比较新...
### Java简单实现二叉树知识点解析 #### 一、二叉树基本概念 二叉树是一种树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树在计算机科学中有着广泛的应用，如搜索算法、排序算法...
本课程设计将详细介绍如何使用Java编程语言实现二叉树的中序遍历。 首先，我们先构建二叉树的节点类（Node），它包含一个数据字段（data）以及指向左子节点（left）和右子节点（right）的引用： ```java public ...
用java写的二叉树，一种特别的二叉树，右子树大于左子树，具体的名称不记得了。
下面我们将详细讨论在给定的“java实现的二叉树源码”中涉及的知识点。 1. **节点(Node)**: 节点是二叉树的基本构建单元，通常包含两个子节点（左子节点和右子节点）以及一个存储数据的属性。在`Node.java`文件中，...
在Java中实现二叉树的最佳方法涉及对其逻辑结构和存储结构的理解，以及如何通过代码高效地构建和遍历二叉树。 首先，数据结构可以按逻辑结构分类，其中二叉树属于非线性结构。二叉树的逻辑分类是基于节点与子树之间...
java实现 二叉树的遍历 前序遍历用到递归， 中序和后序遍历用到栈， 其实还是有一定难度的
本文将深入探讨“数据结构 二叉树 java图形界面实现”这一主题，主要围绕二叉树的基本概念、常见操作以及如何在Java环境中结合图形界面进行实现。 首先，二叉树是一种非线性的数据结构，每个节点最多有两个子节点，...
这个名为"Java二叉树算法实例.zip"的压缩包显然是一个针对初学者的教程，旨在帮助他们理解并掌握二叉树的基本概念和常见算法。 首先，二叉树是由节点构成的数据结构，每个节点包含两个子节点，分别称为左子节点和右...
java用队列实现的二叉树程序//入队 public void enqueue(E e); //出队 public E dequeue(); //取队列第一个 public E front(); //队列是否为空 public boolean isEmpty(); //队列大小 public int size...
本项目提供了Java实现二叉树的相关代码，帮助你理解和操作这种数据结构。 首先，我们要了解二叉树的基本概念。二叉树可以分为几种类型：满二叉树（每个节点要么没有子节点，要么有左右两个子节点）、完全二叉树...
在Java中动态实现二叉树，即在运行时根据需要创建、更新和操作树结构，这涉及到对数据结构和Swing组件的深入理解。 首先，二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点，分别称为左孩子和右孩子。...
在Java中实现二叉树的基本操作是编程学习中的一个重要环节，这包括创建、插入节点、删除节点、遍历以及查找等操作。下面将详细介绍这些知识点。 1. **创建二叉树** 创建二叉树首先需要定义一个二叉树节点类，包含...