二叉树之二叉链表

　　本文利用java语言模拟二叉树的二叉链表的实现，下面先对二叉树的相关概念作简单介绍：
　　二叉树：每个结点至多有两颗子树，且子树有左右之分，其次序不能任意颠倒； 基本形态：空、仅有根结点、左子树为空、右子树为空、左右子树均非空；
　　完全二叉树父子结点序号关系：
　　* 如果i=1，则结点i为根结点，否则其双亲结点为[i/2];
　　* 如果2i > n，则结点i无左孩子，否则其左孩子结点为2i;
　　* 如果2i+1 > n，则结点i无右孩子，否则右孩子结点为2i+1;
　　二叉链表：结点包含数据域和左右指针（引用）域的链表；
　　下面主要给出二叉链表的实现：
　　1. 二叉链表的结点
　　package org.sky.tree;
　　/**
　　* 二叉链表结点
　　*
　　* @author sky
　　*
　　* @param <E>
　　*/
　　public class BinaryTreeNode<E> {
　　E element;
　　BinaryTreeNode<E> leftChild;
　　BinaryTreeNode<E> rightChild;
　　public BinaryTreeNode() {
　　super();
　　this.element = null;
　　this.leftChild = null;
　　this.rightChild = null;
　　}
　　public BinaryTreeNode(E element) {
　　super();
　　this.element = element;
　　this.leftChild = null;
　　this.rightChild = null;
　　}
　　public BinaryTreeNode(E element， BinaryTreeNode<E> leftChild，
　　BinaryTreeNode<E> rightChild) {
　　super();
　　this.element = element;
　　this.leftChild = leftChild;
　　this.rightChild = rightChild;
　　}
　　public E getElement() {
　　return element;
　　}
　　public void setElement(E element) {
　　this.element = element;
　　}
　　public BinaryTreeNode<E> getLeftChild() {
　　return leftChild;
　　}
　　public void setLeftChild(BinaryTreeNode<E> leftChild) {
　　this.leftChild = leftChild;
　　}
　　public BinaryTreeNode<E> getRightChild() {
　　return rightChild;
　　}
　　public void setRightChild(BinaryTreeNode<E> rightChild) {
　　this.rightChild = rightChild;
　　}  
　　public boolean isLeaf() {
　　if (this.leftChild == null && this.rightChild == null) {
　　return true;
　　}
　　return false;
　　}
　　}
　　2. 二叉链表实现
　　package org.sky.tree;
　　import java.util.Collection;
　　import java.util.LinkedList;
　　import java.util.List;
　　import java.util.Queue;
　　import java.util.Scanner;
　　import java.util.Stack;
　　import java.util.concurrent.LinkedBlockingDeque;
　　import java.util.concurrent.LinkedBlockingQueue;
　　/**
　　* 二叉链表实现
　　*
　　* @author sky
　　*
　　* @param <E>
　　*/
　　public class BinaryTree<E> {
　　private BinaryTreeNode<E> root;
　　public BinaryTree() {
　　super();
　　this.root = new BinaryTreeNode<E>();
　　}
　　public boolean isEmpty() {
　　if (root == null) {
　　return true;
　　}
　　return false;
　　}
　　public BinaryTreeNode<E> getRoot() {
　　return root;
　　}  
　　/**
　　* 将输入的数据随机分配在二叉树的结点，以生成随机二叉树
　　* @param node
　　* @param element
　　*/
　　public void createTreeRandomly(BinaryTreeNode<E> node， E element){
　　if(root == null){
　　root = new BinaryTreeNode<E>();
　　}else{
　　if(Math.random() > 0.5){
　　if(node.leftChild == null){
　　node.leftChild = new BinaryTreeNode<E>(element);
　　}else{
　　createTreeRandomly(node.leftChild，element);
　　}
　　}else{
　　if(node.rightChild == null){
　　node.rightChild = new BinaryTreeNode<E>(element);
　　}else{
　　createTreeRandomly(node.rightChild，element);
　　}
　　}
　　}
　　}
　　/**
　　* 根据传入的集合创建完全二叉树
　　* 此处利用了完全二叉树父结点和子结点间的关系：如果i=1，则结点i为根结点，否则其双亲结点为[i/2];
　　*                              如果2i > n，则结点i无左孩子，否则其左孩子结点为2i;
　　*                              如果2i+1 > n，则结点i无右孩子，否则右孩子结点为2i+1;
　　* @param c
　　*/
　　private BinaryTreeNode<E> node = null;
　　public void createCompleteBinaryTree(Collection<? extends E> c){
　　if(c != null && c.size() > 0){
　　List<BinaryTreeNode<E>> treeList = new LinkedList<BinaryTreeNode<E>>();
　　for(Object o : c){             
　　BinaryTreeNode<E> binaryTreeNode = new BinaryTreeNode<E>((E)o);
　　treeList.add(binaryTreeNode);
　　}
　　LinkedBlockingDeque<BinaryTreeNode<E>> queue = new LinkedBlockingDeque<BinaryTreeNode<E>>();
　　//对前treeList.size()/2 - 1个父节点按照父节点与孩子节点的数字关系建立二叉树
　　for(int parentIndex =  0; parentIndex < treeList.size()/2; parentIndex++){             
　　if(parentIndex == 0){
　　root = treeList.get(parentIndex);
　　//左子树
　　root.leftChild = treeList.get(parentIndex*2 + 1);
　　queue.add(root.leftChild);
　　//右子树
　　root.rightChild = treeList.get(parentIndex*2 +2);
　　queue.add(root.rightChild);
　　}else{
　　if(!queue.isEmpty() && parentIndex*2+1 < treeList.size()){
　　node = (BinaryTreeNode<E>) queue.poll();
　　if(parentIndex*2+1 < treeList.size()){
　　//左子树
　　node.leftChild = treeList.get(parentIndex*2 + 1);
　　queue.add(root.leftChild);
　　}
　　if(parentIndex*2+2 < treeList.size()){
　　//右子树
　　node.rightChild = treeList.get(parentIndex*2 + 2);
　　queue.add(root.rightChild);
　　}
　　}else{
　　return ;
　　};
　　}
　　}          
　　}
　　}
　　/**
　　* 先序遍历创建二叉树，其中输入的‘#’代表空结点;
　　* 例如输入input.txt:- + a # # * # # / e # # f # #;
　　* @param inputFile
　　*/
　　public void preOrderCreateBinaryTree(String inputFile){
　　Scanner scanner = null;
　　try{
　　scanner = new Scanner(inputFile);
　　}catch(Exception  e){
　　e.printStackTrace();
　　}
　　this.root = preOrderCreateBinaryTree(root， scanner);
　　}  
　　public BinaryTreeNode<E> preOrderCreateBinaryTree(BinaryTreeNode<E> node， Scanner scanner){
　　String temp = scanner.next();
　　if(temp.trim().equals("#")){
　　return null;
　　}else{
　　node = new BinaryTreeNode<E>((E)temp);
　　node.setLeftChild(preOrderCreateBinaryTree(node.getLeftChild()， scanner));
　　node.setRightChild(preOrderCreateBinaryTree(node.getRightChild()， scanner));
　　return node;
　　}
　　}
　　/**
　　* 递推：知道第一个，推出下一个，直到达到目的。
　　* 递归：要知道第一个，需要先知道下一个，直到一个已知的，再反回来，得到上一个，直到第一个。
　　*/
　　/**
　　* 递归求二叉树结点个数
　　* @param root
　　* @return 二叉树结点个数
　　*/
　　public int getNodeNumber(BinaryTreeNode<E> root){
　　if(root == null){
　　return 0;
　　}else{
　　return getNodeNumber(root.leftChild) + getNodeNumber(root.rightChild) + 1;
　　}
　　}
　　/**
　　* 递归求二叉树的深度
　　* @param root
　　* @return 二叉树的深度
　　*/
　　public int getDepth(BinaryTreeNode<E> root){
　　if(root == null){
　　return 0;
　　}else{
　　int depthLeft = getDepth(root.leftChild);   //左子树深度
　　int depthRight = getDepth(root.rightChild); //右子树深度
　　return depthLeft > depthRight ? (depthLeft+1) : (depthRight+1);
　　}
　　}
　　/**
　　* 递归求二叉树第k层的结点个数
　　* @param root
　　* @param k
　　* @return 第k层的结点个数
　　*/
　　public int getKthLevelNodeNumber(BinaryTreeNode<E> root， int k){
　　if(root == null || k < 1){
　　return 0;
　　}
　　if(k == 1){
　　return 1;
　　}
　　int leftNumber = getKthLevelNodeNumber(root.leftChild， k-1);
　　int rightNumber = getKthLevelNodeNumber(root.rightChild，k-1);
　　return (leftNumber + rightNumber);
　　}
　　/**
　　* 递归求二叉树的叶子结点数
　　* @param root
　　* @return
　　*/
　　public int getLeafNodeNumber(BinaryTreeNode<E> root){
　　if(root == null){
　　return 0;
　　}
　　if(root.leftChild == null && root.rightChild == null){
　　return 1;
　　}
　　int leftNumber = getLeafNodeNumber(root.leftChild);
　　int rightNumber = getLeafNodeNumber(root.rightChild);
　　return (leftNumber + rightNumber);
　　}
　　/**
　　* 判定两个二叉树结构是否相同
　　* 递归解法：
　　* （1）如果两棵二叉树都为空，返回真
　　* （2）如果两棵二叉树一棵为空，另一棵不为空，返回假
　　* （3）如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假
　　* @param root1
　　* @param root2
　　* @return 结构相同时，返回true;
　　*/
　　public boolean strutureComp(BinaryTreeNode<E> root1， BinaryTreeNode<E> root2){
　　if(root1 == null && root2 == null){
　　return true;
　　}else if(root1 == null || root2 == null){
　　return false;
　　}
　　boolean leftResult = strutureComp(root1.leftChild， root2.leftChild);
　　boolean rightResult = strutureComp(root1.rightChild， root2.rightChild);
　　return (leftResult && rightResult);
　　}
　　/**
　　* 递归插入结点
　　* @param root
　　* @param element
　　* @return 二叉树
　　*/
　　public BinaryTreeNode<E> insert(BinaryTreeNode<E> root， E element){
　　BinaryTreeNode<E> pointer = new BinaryTreeNode<E>(element);
　　if(root == null){
　　root = pointer;
　　}else if(root.leftChild == null){
　　root.leftChild = insert(root.leftChild， element);
　　}else if(root.rightChild == null){
　　root.rightChild = insert(root.rightChild， element);
　　}
　　return root;
　　}