二叉树的实现

二叉树的节点

package com.tree;

public class TreeNode {

    private String data = null;
    private TreeNode Lchild;
    private TreeNode Rchild;
    
    public TreeNode() {
        
    }

    public TreeNode(String data, TreeNode lchild, TreeNode rchild) {
        super();
        this.data = data;
        Lchild = lchild;
        Rchild = rchild;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public TreeNode getLchild() {
        return Lchild;
    }

    public void setLchild(TreeNode lchild) {
        Lchild = lchild;
    }

    public TreeNode getRchild() {
        return Rchild;
    }

    public void setRchild(TreeNode rchild) {
        Rchild = rchild;
    }
    
}

二叉树的实现

package com.tree;

import java.util.LinkedList;
import java.util.Queue;

public class BinTree {

    private TreeNode root;

    public BinTree() {

    }

    public BinTree(TreeNode root) {
        this.root = root;
    }

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }   
    
    /*
     * 返回element的父节点
     */
    public TreeNode getParent(TreeNode element)
    {
        return (root == null ||root == element)?null:parent(root,element);
    }
    
    private TreeNode parent(TreeNode subelem,TreeNode element)
    {
        //如果当前节点为空，直接返回null
        if(subelem == null)
        {
            return null;
        }
        //如果当前节点的左孩子或者右孩子为element，则返回当前节点
        if(subelem.getLchild() == element || subelem.getRchild() == element)
        {
            return subelem;
        }
        
        //否则去当前节点的左子树查找
        TreeNode p = parent(subelem.getLchild(),element);
        if(p != null)
        {
            return p;
        }else
        //没有找到再去右子树查找
        {
            return parent(subelem.getRchild(),element);
        }
    }
    
    /*
     * 节点个数
     */
    public int getSize()
    {
        return getNum(root);
    }
    
    private int getNum(TreeNode element)
    {
        if(element == null)
        {
            return 0;
        }
        else
        {
            int i = getNum(element.getLchild());
            int j = getNum(element.getRchild());
            return i+j+1;
        }
    }
    
    /*
     * 树的高度
     */
    public int getHeight()
    {
        return getHeight(root);
    }
    
    private int getHeight(TreeNode node)
    {
        if(node == null)
        {
            return 0;
        }
        else
        {
            int i = getHeight(node.getLchild());
            int j = getHeight(node.getRchild());
            return (i>j)?(i+1):(j+1);
        }
    }
    
    /**
     * 前序遍历
     */
    public void preOrder(TreeNode node)
    {
        if(node != null){
            System.out.println(node.getData() + " ");
            preOrder(node.getLchild());
            preOrder(node.getRchild());
        }               
    }
    
    /*
     * 中序遍历
     */
    public void inOrder(TreeNode node)
    {
        if(node!=null)
        {
            inOrder(node.getLchild());
            System.out.println(node.getData());
            inOrder(node.getRchild());
        }
    }
    
    /**
     * 后序遍历
     */
    
    public void postOrder(TreeNode node)
    {
        if(node != null)
        {
            postOrder(node.getLchild());
            postOrder(node.getRchild());
            System.out.println(node.getData());
        }
    }
    
    /**
     * 层次遍历
     */
    public void levelOrder(TreeNode root)
    {
        if(root == null)
        {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty())
        {
            TreeNode temp = queue.poll();
            System.out.println(temp.getData());
            if(temp.getLchild()!=null)
            {
                queue.add(temp.getLchild());
            }
            if(temp.getRchild()!=null)
            {
                queue.add(temp.getRchild());
            }
        }
    }
    
}

测试

package com.tree;

public class TreeDemo {

    public static void main(String[] args) {
         TreeNode l12 = new TreeNode("left12", null, null);
         TreeNode r12 = new TreeNode("right12", null, null);
         TreeNode l22 = new TreeNode("left22", null, null);
         TreeNode r22 = new TreeNode("right22", null, null);
         TreeNode l1 = new TreeNode("left1", l12, r12);// 根节点左子树
         TreeNode r1 = new TreeNode("right1", l22, r22);// 根节点右子树
         TreeNode root = new TreeNode("root", l1, r1);// 创建根节点
          
         BinTree bt = new BinTree(root);
         System.out.println("=======先序遍历======");
         bt.preOrder(bt.getRoot());
         System.out.println("=======中序遍历======");
         bt.inOrder(bt.getRoot());
         System.out.println("=======后续遍历======");
         bt.postOrder(bt.getRoot());     
         System.out.println("=======层次遍历======");
         bt.levelOrder(bt.getRoot());
         
         System.out.println("===========");
         System.out.println(bt.getHeight());
         System.out.println(bt.getSize());
         
         System.out.println(bt.getParent(r22).getData());
    }
}