Java数据结构（四）

Java数据结构（四）

——二叉树

我们都知道数据结构时计算机存储时、组织数据的方式。数据结构是指相互之间存在一种或者多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行效率或者存储效率。而一般来说，我们常用的数据结构是：数组，栈，队列，链表，树，图，堆，散列表。这次主要就是二叉树的一点基本知识以及基本实现。

 

定义

一般的定义是二叉树是由n（n>=0）个结点构成的，每个结点最多只有两个子树的有序树。而在图论中是这么定义的：二叉树是一个连通的无环图，并且每一个顶点的度不大于3，有跟二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了一个唯一的父结点，和最多2个子节点。如果不考虑连通性的话，允许图中有多个连通通量，那么这样的结构，可以称之为森林。

在逻辑上二叉树有着5种基本形态：

 

 

 

（1）空二叉树，如图a所示；

（2）只有一个根结点的树，如图b所示；

（3）只有左子树，如图c所示；

（4）只有右子树，如图d所示；

（5）完全二叉树，如图e所示；

 

类型

（1）完全二叉树：设二叉树的高度为h，出第h层以外，其他各层的结点数都达到了其的最大数目，这样的二叉树就是完全二叉树。

（2）满二叉树：在一颗二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树就是满二叉树。

（3）平衡二叉树：平衡二叉树又被称为AVL树，它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两棵子树的高度差的绝对值不小于1，并且左右两个子树都是一棵平衡二叉树。

 

性质

（1）若规定根结点的层次是0，则一棵非空二叉树的第i层上最多有2^i(i>=0)个结点；

（2）若规定孔二叉树树的深度为-1（即根结点的深度为0），则深度为k的二叉树最大结点数是(2^(k+1))-1个；

（3）具有n个结点的完全二叉树的深度k为不超过lb（n+1）的最大整数；

（4）对于一棵非空的二叉树，如果叶结点个数为n0，度为2的结点数为n2，则有n0=n2+1；

（5）具有n个结点的完全二叉树的深度为log2（n+1）；

（6）对于具有n个结点的完全二叉树，如果从上至下和从左至右的顺序对所有结点从0开始顺序编号，则对于序号为i的结点，有：

     A、如果i>0，则序号为i结点的双亲结点的序号为（i-1)/2（/表示整除）;如果i=0，则序号为i的结点为根结点，无双亲结点。

     B、如果2*i+1<n，则序号为i结点的左孩子结点的序号为2*i+1;如果2*i+1>=n，则序号为i的结点无左孩子结点。

  C、如果2*i+2<n，则序号为i结点的右孩子的序号为2*i+2;如果2*i+2>=n，则序号为i的结点无右孩子结点。

 

遍历顺序

遍历是对树最基本的运算，所谓遍历二叉树，就是按照一定规则和顺序走遍二叉树的所有结点，是每个结点都被访问一次，且只访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成一个线性序列来表示。二叉树的基本遍历方法一共有3个：

（1）前序遍历（DLR），首先访问根结点，再遍历左子树，最后遍历右子树，简称为根左右。

（2）中序遍历（LDR），首先遍历左子树，再访问根结点，最后遍历右子树，简称为左根右。

（3）后序遍历（LRD），首先遍历左子树，再遍历右子树，最后访问根结点，简称为左右根。

如图所示：

 

采用前序遍历，则输出序列为ABDCEFGH;

采用中序遍历，则输出序列为BDAFEHGC;

采用后序遍历，则输出序列为DBFHGECA;

 

二叉搜索树的实现代码：

 

package pzw.LinBinaryTree;
/**
 * 二叉树的链式存储结构实现
 * @author pzw
 *
 */
public class BinaryTree {
	
	private TreeNode root;//根结点
	
	//向树中添加元素
	public void add(int elm){
		TreeNode temp = new TreeNode();
		temp.setElm(elm);
		if(root == null){
			root = temp;
		}else{
			add(root,temp);
		}
	}
	
	private void add(TreeNode top,TreeNode temp){
		if(top.getElm() > temp.getElm()){
			//如果想要添加的结点值小于其父结点的值，就将其添加到左子树上，否则添加到右子树上
			if(top.getLeftChild() != null){
				add(top.getLeftChild(),temp);
			}else{
				top.setLeftChild(temp);
			}	
		}else{
			if(top.getRightChild() != null){
				add(top.getRightChild(),temp);
			}else{
				top.setRightChild(temp);
			}
		}
	}
	
	//删除结点subTree及其子树
	public void destroy(TreeNode subTree){
		if(subTree != null){
			destroy(subTree.getLeftChild());
			destroy(subTree.getRightChild());
			subTree = null;
		}
	}
	
	//树的前序遍历,根左右
	public void preOrder(){
		System.out.println("树的前序遍历：");
		System.out.println("root:"+root.getElm());
		preOrder(root.getLeftChild());
		preOrder(root.getRightChild());
	}
	private void preOrder(TreeNode temp){
		if(temp != null){
			System.out.println("temp:"+temp.getElm());
			preOrder(temp.getLeftChild());
			preOrder(temp.getRightChild());
		}
	}
	
	//树的中序遍历，左根右
	public void InOrder(){
		System.out.println("树的中序遍历：");
		InOrder(root.getLeftChild());
		System.out.println("root:"+root.getElm());
		InOrder(root.getRightChild());
	}
	private void InOrder(TreeNode temp){
		if(temp != null){	
			InOrder(temp.getLeftChild());
			System.out.println("temp:"+temp.getElm());
			InOrder(temp.getRightChild());
		}
	}
	
	//树的后序遍历
	public void PostOrder(){
		System.out.println("树的后序遍历：");
		PostOrder(root.getLeftChild());
		PostOrder(root.getRightChild());
		System.out.println("root:"+root.getElm());
	}
	private void PostOrder(TreeNode temp){
		if(temp != null){	
			PostOrder(temp.getLeftChild());
			PostOrder(temp.getRightChild());
			System.out.println("temp:"+temp.getElm());
		}
	}
}