JAVA应用程序开发之二叉树

【本文详细介绍了JAVA应用开发中的二叉树，欢迎读者朋友们阅读、转发和收藏！】

1 基本概念

1.1 二叉树的定义

二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

二叉树 (BinaryTree) 是 n(n ≥ 0) 个结点的有限集，它或者是空集 (n=0) ，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

这个定义是递归的。由于左、右子树也是二叉树， 因此子树也可为空树。下图中展现了五种不同基本形态的二叉树。

其中 (a) 为空树， (b) 为仅有一个结点的二叉树， (c) 是仅有左子树而右子树为空的二叉树， (d) 是仅有右子树而左子树为空的二叉树， (e) 是左、右子树均非空的二叉树。这里应特别注意的是，二叉树的左子树和右子树是严格区分并且不能随意颠倒的，图 (c) 与图 (d) 就是两棵不同的二叉树。

1.2 二叉树的遍历

对于二叉树来讲最主要、最基本的运算是遍历。

遍历二叉树 是指以一定的次序访问二叉树中的每个结点。所谓 访问结点 是指对结点进行各种操作的简称。例如，查询结点数据域的内容，或输出它的值，或找出结点位置，或是执行对结点的其他操作。遍历二叉树的过程实质是把二叉树的结点进行线性排列的过程。假设遍历二叉树时访问结点的操作就是输出结点数据域的值，那么遍历的结果得到一个线性序列。

1.3 二叉树有 3 种遍历方式 :

1, 前序遍历 :

首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树

2, 中序遍历 :

首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树

3, 后序遍历 :

首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根

2 二叉树的 java 实现

首先创建一棵二叉树如下图，然后对这棵叉树进行遍历操作（遍历操作的实现分为递归实现和非递归实现），同时还提供一些方法如获取双亲结点、获取左孩子、右孩子等。

import java.util.Stack;

/**

* 二叉树的链式存储

*/

public class BinaryTree {

private TreeNode root=null;

public BinaryTree(){

root=new TreeNode(1,"rootNode(A)");

}

/**

* 创建一棵二叉树

*

* A

* B C

* D E F

*

* @param root

* @author WWX

*/

public void createBinTree(TreeNode root){

TreeNode newNodeB = new TreeNode(2,"B");

TreeNode newNodeC = new TreeNode(3,"C");

TreeNode newNodeD = new TreeNode(4,"D");

TreeNode newNodeE = new TreeNode(5,"E");

TreeNode newNodeF = new TreeNode(6,"F");

root.leftChild=newNodeB;

root.rightChild=newNodeC;

root.leftChild.leftChild=newNodeD;

root.leftChild.rightChild=newNodeE;

root.rightChild.rightChild=newNodeF;

}

public boolean isEmpty(){

return root==null;

}

// 树的高度

public int height(){

return height(root);

}

// 节点个数

public int size(){

return size(root);

}

private int height(TreeNode subTree){

if(subTree==null)

return 0;// 递归结束：空树高度为 0

else{

int i=height(subTree.leftChild);

int j=height(subTree.rightChild);

return (i

}

}

private int size(TreeNode subTree){

if(subTree==null){

return 0;

}else{

return 1+size(subTree.leftChild)+size(subTree.rightChild);

}

}