blinkedtree.java

来自「一个可以以图形方式直观表示的树状二叉树算法程序,可以实现生成和遍历.」· Java 代码 · 共 127 行

package binarytreetravel;

import java.util.*;
import java.awt.Point;
import java.awt.Rectangle;

/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2005</p>
 * <p>Company: </p>
 * @author not attributable
 * @version 1.0
 */

public class BLinkedTree {
  public BTreeNode root;  //二叉树的根节点
  LinkedList llist;       //遍历使得到的结点的集合

  public BLinkedTree(BTreeNode root) {
    this.root = root;
  }
  public BTreeNode getRoot() {
    return this.root;
  }
  public boolean isEmpty() {
    if(root == null) return true;
    return false;
  }
  public boolean deleteNode(BTreeNode node) {
    if(node != null) {
      node = null;
      return true;
    }
    else return false;
  }
  public LinkedList preOrder(BTreeNode t, int first) {
    //前序遍历
    BTreeNode current;

    if(first == 1) {
      llist = new LinkedList();
      current = root;
      first = 0;
    }
    else current = t;

    if(current != null) {
      llist.add(current);              //先遍历父结点
      preOrder(current.lchild, first); //接着遍历左孩子
      preOrder(current.rchild, first); //最后遍历右孩子
    }
    return llist;
  }
  public LinkedList inOrder(BTreeNode t, int first) {
    //中序遍历
    BTreeNode current;
    //LinkedList llist = new LinkedList();  //把遍历到的节点都放入链表中

    if(first == 1) {
      llist = new LinkedList();
      current = root;
      first = 0;
    }
    else current = t;

    if(current != null) {
      inOrder(current.lchild, first);
      llist.add(current);
      inOrder(current.rchild, first);
    }
    return llist;
  }
  public LinkedList postOrder(BTreeNode t, int first) {
    //后序遍历
    BTreeNode current;

    if(first == 1) {
      llist = new LinkedList();
      current = root;
      first = 0;
    }
    else current = t;

    if(current != null) {
      postOrder(current.lchild, first);
      postOrder(current.rchild, first);
      llist.add(current);
    }
    return llist;
  }
  public int depth(BTreeNode t, int first) {
    //求树的深度,返回树的深度.
    int currentDepth, leftDepth, rightDepth;
    BTreeNode current;

    if(first == 1) {
      current = root;
      first = 0;
    }
    else current = t;

    if(current == null)
      currentDepth = 0;   //如果树为空,则返回0
    else {
      leftDepth = depth(current.lchild, first);
      rightDepth = depth(current.rchild, first);
      if (leftDepth > rightDepth)
        currentDepth = leftDepth + 1;
      else
        currentDepth = rightDepth + 1;
    }
    return currentDepth;
  }
  public BTreeNode searchNode(Point p) {
    //按给定的位置p查找结点,找到返回该结点,找不到返回空
    llist = this.preOrder(null, 1);

    Iterator iter = llist.iterator();
    while(iter.hasNext()) {
      BTreeNode bn = (BTreeNode)iter.next();
      if(new Rectangle(bn.rect).contains(p))
        return bn;
    }
    return null;
  }
}