JAVA 实现二叉树（链式存储结构）

二叉树的分类（按存储结构）

树的分类（按存储结构）

             　顺序存储（用数组表示（静态二叉树））
　　　　  链式存储

一些特别的二叉根：

                                   完全二叉树，平衡二叉树（avl），线索二叉树，三叉的（带父亲的指针）
　　　　　　　　　   二叉搜索树或者叫二叉　查找树（bst）

 所用二叉树如下图所示：

 

二叉树的java实现（链式存储结构）

class treenode {
  private int key = 0;
  private string data = null;
  private boolean isvisted = false;
  private treenode leftchild = null;
  private treenode rightchild = null;
  
  public treenode(){
    
  }
  public treenode(int key, string data){
    this.key = key;
    this.data = data;
    this.leftchild = null;
    this.rightchild = null;
  }
  public int getkey() {
    return key;
  }
  public void setkey(int key) {
    this.key = key;
  }
  public string getdata() {
    return data;
  }
  public void setdata(string data) {
    this.data = data;
  }
  public treenode getleftchild() {
    return leftchild;
  }
  public void setleftchild(treenode leftchild) {
    this.leftchild = leftchild;
  }
  public treenode getrightchild() {
    return rightchild;
  }
  public void setrightchild(treenode rightchild) {
    this.rightchild = rightchild;
  }
  public boolean isvisted() {
    return isvisted;
  }
  public void setvisted(boolean isvisted) {
    this.isvisted = isvisted;
  }
}

public class binarytree {

  private treenode root = null;

  public binarytree() {
    root = new treenode(1, "rootnode(a)");
  }
  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.setleftchild(newnodeb);
    root.setrightchild(newnodec);
    root.getleftchild().setleftchild(newnoded);
    root.getleftchild().setrightchild(newnodee);
    root.getrightchild().setrightchild(newnodef);
  }
  public boolean isempty() {
    // 判二叉树空否
    return root == null;
  }

  public int height() {
    // 求树高度
    return height(root);
  }

  public int height(treenode subtree) {
    if (subtree == null)
      return 0; //递归结束：空树高度为0
    else {
      int i = height(subtree.getleftchild());
      int j = height(subtree.getrightchild());
      return (i < j) ? j + 1 : i + 1;
    }

  }

  public int size() {
    // 求结点数
    return size(root);
  }

  public int size(treenode subtree) {
    if (subtree == null)
      return 0;
    else {
      return 1 + size(subtree.getleftchild())
          + size(subtree.getrightchild());
    }
  }

  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.getleftchild() == element
        || subtree.getrightchild() == element)
      //找到, 返回父结点地址
      return subtree;
    treenode p;
    //先在左子树中找，如果左子树中没有找到，才到右子树去找
    if ((p = parent(subtree.getleftchild(), element)) != null)
      //递归在左子树中搜索
      return p;
    else
      //递归在左子树中搜索
      return parent(subtree.getrightchild(), element);

  }

  public treenode leftchild(treenode element) {
    //返回左子树
    return (element != null) ? element.getleftchild() : null;
  }

  public treenode rightchild(treenode element) {
    //返回右子树
    return (element != null) ? element.getrightchild() : null;
  }

  public treenode getroot() {
    //取得根结点
    return root;
  }

  public void destroy(treenode subtree) {
    //私有函数: 删除根为subtree的子树
    if (subtree != null) {
      destroy(subtree.getleftchild()); //删除左子树
      destroy(subtree.getrightchild()); //删除右子树
      //delete subtree;       //删除根结点
      subtree = null;
    }
  }

  public void traverse(treenode subtree) {

    system.out.println("key:" + subtree.getkey() + "--name:"
        + subtree.getdata());
    traverse(subtree.getleftchild());
    traverse(subtree.getrightchild());
  }

  public void preorder(treenode subtree) {
    //先根
    if (subtree != null) {
      visted(subtree);
      preorder(subtree.getleftchild());
      preorder(subtree.getrightchild());
    }
  }

  public void inorder(treenode subtree) {
    //中根
    if (subtree != null) {
      inorder(subtree.getleftchild());
      visted(subtree);
      inorder(subtree.getrightchild());
    }
  }

  public void postorder(treenode subtree) {
    //后根
    if (subtree != null) {
      postorder(subtree.getleftchild());
      postorder(subtree.getrightchild());
      visted(subtree);
    }
  }
  public void levelorder(treenode subtree) {
     //水平遍边
  }
  public boolean insert(treenode element){
    //插入
    return true;
  }
  public boolean find(treenode element){
    //查找
    return true;
  }
  public void visted(treenode subtree) {
    subtree.setvisted(true);
    system.out.println("key:" + subtree.getkey() + "--name:"
        + subtree.getdata());
  }

  public static void main(string[] args) {
    binarytree bt = new binarytree();
    bt.createbintree(bt.root);
    system.out.println("the size of the tree is " + bt.size());
    system.out.println("the height of the tree is " + bt.height());
    system.out.println("*******先根(前序)[abdecf]遍历*****************");
    bt.preorder(bt.root);
    system.out.println("*******中根(中序)[dbeacf]遍历*****************");
    bt.inorder(bt.root);
    system.out.println("*******后根(后序)[debfca]遍历*****************");
    bt.postorder(bt.root);
  }

}

 结果输出：
the size of the tree is 6
the height of the tree is 3
*******先根(前序)[abdecf]遍历*****************
key:1--name:rootnode(a)
key:2--name:b
key:4--name:d
key:5--name:e
key:3--name:c
key:6--name:f
*******中根(中序)[dbeacf]遍历*****************
key:4--name:d
key:2--name:b
key:5--name:e
key:1--name:rootnode(a)
key:3--name:c
key:6--name:f
*******后根(后序)[debfca]遍历*****************
key:4--name:d
key:5--name:e
key:2--name:b
key:6--name:f
key:3--name:c
key:1--name:rootnode(a)

 希望本文对学习java程序设计的同学有所帮助。