java二叉树的实现

package arithmetic;

import java.util.Stack;

public class BinaryTree <T>{

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        node root = new node(1,"A");
        BinaryTree bt = new BinaryTree();
        bt.createBinaryTree(root);
        System.out.println("************************根序遍(修改前）******************************");
        //bt.preOrderTraverse(root);
        bt.preOder(root);
        System.out.println("************************先根序遍(修改后）******************************");
        bt.insertChileftd(root, 6, 0, 9, "QQQQQQ");    //实现了结点的插入
        bt.preOder(root);

    };
    /**
     * 创建该树，也可以通过insertChileftd来进行创建
     * @param root
     */
    public void createBinaryTree(node root){
        node b = new node(2,"B");
        node c = new node(3,"C");
        node d = new node(4,"D");
        node e = new node(5,"E");
        node f = new node(6,"F");
        node g = new node(7,"G");
        
        root.left = b;
        root.r = c;
        b.left = d;
        b.r = e;
        e.left = f;
        e.r = g;
    }
    /**
     * @param root 根节点
     * @param p        插入结点的编号
     * @param leftr    需要插入的是左孩子还是右孩子
     * @param ID    插入结点的编号
     * @param valeftue    插入结点的值
     */
    public void insertChileftd(node root, int p,int leftr,int ID, T valeftue){
        Stack<node> s = new Stack<node>();
        node Node = root;        //根节点
        node point= null;        //所需寻找的结点
        
        //通过栈的先序遍历寻找出p结点
         while (Node != null || s.size() > 0){
             while(Node != null){
                 s.push(Node);
                 if (Node.id == p){
                     point = Node;
                     break;
                 }
                 if (Node.id == ID) {
                     System.out.println("改标号已存在，请重新插入");
                     System.exit(0);
                 }
                 Node = Node.left;
             }
             Node = s.pop();
             Node = Node.r;
        }
         //根据leftr的只判断需要插入左孩子还是右孩子 leftr=0 表示插入做孩子 leftr = 1表示差入有孩子
         if (leftr == 0){
             //判断左孩子是否为空，为空只修改值不修改编号，当孩子为空时插入孩子结点，并编号和赋值
             if (point.left != null) {
                 point.left.valeft = valeftue;
             }
             else {
                 node lefteftChileftd = new node(0,null);
                 point.left = lefteftChileftd;
                 lefteftChileftd.id = ID;
                 lefteftChileftd.valeft = valeftue;
             }
         }
         
         else if (leftr == 1){
             if (point.r != null){
                 point.r.valeft = valeftue;
             }
             else {
                 node rightChileftd = new node(0,null);
                 point.left = rightChileftd;
                 rightChileftd.id = ID;
                 rightChileftd.valeft = valeftue;
             }
         }
                     
    }
    /**
     * 用递归实现先序遍历
     * @param Node
     */
    public void  preOrderTraverse(node Node){
        if (Node != null){
            System.out.println("结点为："+Node.id+"     结点值为："+Node.valeft+" 	 ");
            preOrderTraverse(Node.left);
            preOrderTraverse(Node.r);
        }    
    }
    
    /**
     * 非递归实现先序遍历
     */
    public void preOder(node Node){
        Stack<node> s = new Stack<node>();
         while (Node != null || s.size() > 0){
             while(Node != null){
                 s.push(Node);
                 System.out.println("结点为："+Node.id+"     结点值为："+Node.valeft+" 	 ");
                 Node = Node.left;
             }
             Node = s.pop();
             Node = Node.r;
        }
    }
}
/**
 * 二叉树的节点数据结构
 * @author yb
 * @param <T>
 */
class node<T>{
    node left;
    node r;
    //id为结点的标识号，valeft为结点的值
    T valeft = null;
    int id = 0;
    
    public node(int ID,T s){
        this.valeft = s;
        this.id = ID;
        this.left = null;
        this.r = null;
    }
}