java数据结构 （两叉树）

   树
一，为什么需要使用树？
    有序数组插入数据项和删除数据项太慢。
    链表查找数据太慢。
    在树中能非常快速的查找数据项，插入数据项和删除数据项。

二，树的结构


                                          树的基本概念
三，路径
    顺着连接节点的边从一个节点到另一个节点，所经过的节点顺序排列称为路径。

四，根
    树最上面的节点称为根节点。一棵树只有一个根。而且从根到任何节点有且只有一条路径。

五，父节点
    每个节点都有一条边向上连接到另一个节点，这个节点就称为是下面这个节点的父节点。

六，子节点
    每个节点都有一条边向下连接到另一个节点，下面的节点就是该节点的子节点。

七，叶子节点
    没有子节点的节点称为叶子节点。

八，子树
    每个节点都可以作为一个子树的根，它和它所有的子节点，子节点的子节点组合在一起就是一个子树。

九，访问
    访问一个节点是为了在这个节点上执行一些操作；如查看节点的数据项。但是如果仅仅是经过一个节点，不认为是访问了这个节点。

十，层
    一个节点的层数是指从根开始到这个节点有多少代。


                                                二叉树
一，二叉树
    树的每个节点最多只能有两个子节点的树，成为二叉树。

二，代码实现二叉树

/* 
 * 二叉树节点 
 */ 
public class Node { 
    //数据项 
    public long data; 
    //左子节点 
    public Node leftChild; 
    //右子节点 
    public Node rightChild; 
 
    /** 
     * 构造方法 
     * @param data 
     */ 
    public Node(long data) { 
        this.data = data; 
    } 
}

/* 
 * 二叉树类 
 */ 
public class Tree { 
    //根节点 
    private Node root; 
 
    /** 
     * 插入节点 
     * @param value 
     */ 
    public void insert(long value) { 
 
    } 
 
    /** 
     * 查找节点 
     * @param value 
     */ 
    public void find(long value) { 
 
    } 
 
    /** 
     * 删除节点 
     * @param value 
     */ 
    public void delte(long value) { 
 
    } 
}

      二叉树操作
一，插入节点。
    从根节点开始查找一个相应的节点，这个节点将成为新插入节点的父节点。当父节点找到后，通过判断新节点的值比父节点的值的大小来决定是连接到左子节点还是右子节点。

二，查找节点。
    从根节点开始查找，如果查找的节点值比当前节点的值小，则继续查找其左子树，否则查找其右子树。

/* 
 * 二叉树节点 
 */ 
public class Node { 
    //数据项 
    public long data; 
    //数据项 
    public String sData; 
    //左子节点 
    public Node leftChild; 
    //右子节点 
    public Node rightChild; 
 
    /** 
     * 构造方法 
     * @param data 
     */ 
    public Node(long data,String sData) { 
        this.data = data; 
        this.sData = sData; 
    } 
 
}

/* 
 * 二叉树类 
 */ 
public class Tree { 
    //根节点 
    public Node root; 
 
    /** 
     * 插入节点 
     * @param value 
     */ 
    public void insert(long value,String sValue) { 
        //封装节点 
        Node newNode = new Node(value,sValue); 
        //引用当前节点 
        Node current = root; 
        //引用父节点 
        Node parent; 
        //如果root为null，也就是第一插入的时候 
        if(root == null) { 
            root = newNode; 
            return; 
        } else { 
            while(true) { 
                //父节点指向当前节点 
                parent = current; 
                //如果当前指向的节点数据比插入的要大,则向左走 
                if(current.data > value) { 
                    current = current.leftChild; 
                    if(current == null) { 
                        parent.leftChild = newNode; 
                        return; 
                    } 
                } else { 
                    current = current.rightChild; 
                    if(current == null) { 
                        parent.rightChild = newNode; 
                        return; 
                    } 
                } 
            } 
        } 
    } 
 
    /** 
     * 查找节点 
     * @param value 
     */ 
    public Node find(long value) { 
        //引用当前节点，从根节点开始 
        Node current = root; 
        //循环，只要查找值不等于当前节点的数据项 
        while(current.data != value) { 
            //进行比较，比较查找值和当前节点的大小 
            if(current.data > value) { 
                current = current.leftChild; 
            } else { 
                current = current.rightChild; 
            } 
            //如果查找不到 
            if(current == null) { 
                return null; 
            } 
        } 
        return current; 
    } 
 
    /** 
     * 删除节点 
     * @param value 
     */ 
    public void delte(long value) { 
 
    } 
 
}

public class TestTree { 
    public static void main(String[] args) { 
        Tree tree = new Tree(); 
        tree.insert(10,"James"); 
        tree.insert(20,"YAO"); 
        tree.insert(15,"Kobi"); 
        tree.insert(3,"Mac"); 
 
        System.out.println(tree.root.data); 
        System.out.println(tree.root.rightChild.data); 
        System.out.println(tree.root.rightChild.leftChild.data); 
        System.out.println(tree.root.leftChild.data); 
 
        Node node = tree.find(3); 
        System.out.println(node.data + ", " + node.sData); 
    } 
}

                                                遍历二叉树
一，遍历树
    遍历树是根据一个特定的顺序访问树的每一个节点，根据顺序的不同分为前序，中序，后序遍历三种。

二，前序遍历
    （1）访问根结点
    （2）前序遍历左子树
    （3）前序遍历右子树

三，中序遍历
    （1）中序遍历左子树
    （2）访问根结点
    （3）中序遍历右子树

四，后序遍历
    （1）后序遍历左子树
    （2）后序遍历右子树
    （3）访问根结点

/* 
 * 二叉树节点 
 */ 
public class Node { 
    //数据项 
    public long data; 
    //数据项 
    public String sData; 
    //左子节点 
    public Node leftChild; 
    //右子节点 
    public Node rightChild; 
 
    /** 
     * 构造方法 
     * @param data 
     */ 
    public Node(long data,String sData) { 
        this.data = data; 
        this.sData = sData; 
    } 
 
}

/* 
 * 二叉树类 
 */ 
public class Tree { 
    //根节点 
    public Node root; 
 
    /** 
     * 插入节点 
     * @param value 
     */ 
    public void insert(long value,String sValue) { 
        //封装节点 
        Node newNode = new Node(value,sValue); 
        //引用当前节点 
        Node current = root; 
        //引用父节点 
        Node parent; 
        //如果root为null，也就是第一插入的时候 
        if(root == null) { 
            root = newNode; 
            return; 
        } else { 
            while(true) { 
                //父节点指向当前节点 
                parent = current; 
                //如果当前指向的节点数据比插入的要大,则向左走 
                if(current.data > value) { 
                    current = current.leftChild; 
                    if(current == null) { 
                        parent.leftChild = newNode; 
                        return; 
                    } 
                } else { 
                    current = current.rightChild; 
                    if(current == null) { 
                        parent.rightChild = newNode; 
                        return; 
                    } 
                } 
            } 
        } 
    } 
 
    /** 
     * 查找节点 
     * @param value 
     */ 
    public Node find(long value) { 
        //引用当前节点，从根节点开始 
        Node current = root; 
        //循环，只要查找值不等于当前节点的数据项 
        while(current.data != value) { 
            //进行比较，比较查找值和当前节点的大小 
            if(current.data > value) { 
                current = current.leftChild; 
            } else { 
                current = current.rightChild; 
            } 
            //如果查找不到 
            if(current == null) { 
                return null; 
            } 
        } 
        return current; 
    } 
 
    /** 
     * 删除节点 
     * @param value 
     */ 
    public void delte(long value) { 
 
    } 
 
    /** 
     * 前序遍历 
     */ 
    public void frontOrder(Node localNode) { 
        if(localNode != null) { 
            //访问根节点 
            System.out.println(localNode.data + ", " + localNode.sData); 
            //前序遍历左子树 
            frontOrder(localNode.leftChild); 
            //前序遍历右子树 
            frontOrder(localNode.rightChild); 
        } 
    } 
 
    /** 
     * 中序遍历 
     */ 
    public void inOrder(Node localNode) { 
        if(localNode != null) { 
            //中序遍历左子树 
            inOrder(localNode.leftChild); 
            //访问根节点 
            System.out.println(localNode.data + ", " + localNode.sData); 
            //中旬遍历右子树 
            inOrder(localNode.rightChild); 
        } 
    } 
 
    /** 
     * 后序遍历 
     */ 
    public void afterOrder(Node localNode) { 
        if(localNode != null) { 
            //后序遍历左子树 
            afterOrder(localNode.leftChild); 
            //后序遍历右子树 
            afterOrder(localNode.rightChild); 
            //访问根节点 
            System.out.println(localNode.data + ", " + localNode.sData); 
        } 
    } 
}