java二叉树实现代码

public class Tree {

private TreeNode root = null;
public Tree() {
        root = new TreeNode(1, "A");
    }

private class TreeNode {
private int key;
private String data;
private boolean isVisted;
private TreeNode leftChild;
private TreeNode rightChild;

public TreeNode(int key, String data) {
this.key = key;
this.data = data;
this.leftChild = null;
this.rightChild = null;
this.isVisted = false;
        }
    }
/**
     * 创建一颗二叉树
     *             A
     *         B        C
     *       D   E            F
     * createBinTree:(). 
     * @author 
     * @param root
*/
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;
//        newNodeC.rightChild = newNodeF;
//        newNodeB.leftChild = newNodeD;
//        newNodeB.rightChild = newNodeE;
        root.rightChild.rightChild = newNodeF;
        root.leftChild.leftChild = newNodeD;
        root.leftChild.rightChild = newNodeE;
    }

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;

int i = height(subTree.leftChild);
int j = height(subTree.rightChild);

return i < j ? j + 1 : i + 1;
    }

private int size(TreeNode subTree) {
if (subTree == null)
return 0;
return 1 + size(subTree.leftChild) + size(subTree.rightChild);
    }
//返回双亲节点
public TreeNode parent(TreeNode element) {
return (root == null || root == element) 
? null : parent(root, element);
    }

public TreeNode parent(TreeNode subTree, TreeNode element) {
if (subTree == null)
return null;
if (subTree.leftChild == element || subTree.rightChild == element) {
//返回父节点地址
return subTree;
        }
        TreeNode p;
//先在左子树中查找，如果左子树中没有找到，则到右子树中查找
if ((p = parent(subTree.leftChild, element)) != null)
return p; //递归左子树中搜索
else
return parent(subTree.rightChild, element);
    }

public TreeNode getLeftChildNode(TreeNode element) {
return element != null ? element.leftChild : null;
    }

public TreeNode getRightChildNode(TreeNode element) {
return element != null ? element.rightChild : null;
    }

public TreeNode getRoot() {
return root;
    }

//在释放某个节点时，该节点的左右子树都已经释放，
//所以应该采用后续遍历，当访问某个节点时将该节点的存储空间释放
public void distroy(TreeNode subTree) {
//删除根为subTree的子树
if (subTree != null) {
//删除左子树
            distroy(subTree.leftChild);
//删除右子树
            distroy(subTree.rightChild);
//删除根节点
            subTree = null;
        }
    }

public void traverse(TreeNode subTree) {
        System.out.println("key:" + subTree.key + "--name:" + subTree.data);
        traverse(subTree.leftChild);
        traverse(subTree.rightChild);
    }
//前序遍历
public void perOrder(TreeNode subTree) {
if (subTree != null) {
            visted(subTree);
            perOrder(subTree.leftChild);
            perOrder(subTree.rightChild);
        }
    }
//中序遍历
public void inOrder(TreeNode subTree) {
if (subTree != null) {
            perOrder(subTree.leftChild);
            visted(subTree);
            perOrder(subTree.rightChild);
        }
    }
//后序遍历
public void postOrder(TreeNode subTree) {
if (subTree != null) {
            perOrder(subTree.leftChild);
            perOrder(subTree.rightChild);
            visted(subTree);
        }
    }
//将二叉树镜面对称
public void mirror(TreeNode subTree) {
if (subTree == null)
return;
        TreeNode node = new TreeNode(subTree.key, subTree.data);
        node.leftChild = subTree.leftChild;
        subTree.leftChild = subTree.rightChild;
        subTree.rightChild = node.leftChild;
        mirror(subTree.leftChild);
        mirror(subTree.rightChild);
    }

public void visted(TreeNode subTree) {
        subTree.isVisted = true;
        System.out.println("key:" + subTree.key + "---data:" + subTree.data);
    }
//测试
public static void main(String[] args) {
        Tree bt = new Tree();
        bt.createBinTree(bt.root);

        System.out.println(bt.size() + "---size");
        System.out.println(bt.height() + "---height");

        System.out.println("**************前序遍历************");
        bt.perOrder(bt.root);
        System.out.println("************镜面对称**前序遍历************");
        bt.mirror(bt.root);
        bt.perOrder(bt.root);
//        System.out.println("**************中序遍历************");
//        bt.inOrder(bt.root);
//        
//        System.out.println("**************后序遍历************");
//        bt.postOrder(bt.root);
    }

}