二叉树

 节点类

package com.nanjing.study.dataStructure;

public class Node {
    Person person;
    Node leftNode;
    Node rightNode;

    public Node(Person person, Node leftNode, Node rightNode) {
        this.person = person;
        this.leftNode = leftNode;
        this.rightNode = rightNode;
    }

    public void toNodeString() {
        System.out.println("根节点:" + person);
        while (leftNode != null) {
            System.out.println("rightNode=" + rightNode.person);
            leftNode = leftNode.leftNode;
        }

        while (rightNode != null) {
            System.out.println("rightNode=" + rightNode.person);
            rightNode = rightNode.rightNode;
        }
    }
}

 

 数据对象类

package com.nanjing.study.dataStructure;

public class Person {
    int iData;
    double fData;

    public Person() {
    }

    public Person(int iData, double fData) {
        this.iData = iData;
        this.fData = fData;
    }

    @Override
    public String toString() {
        return "Person{" +
                "iData=" + iData +
                ", fData=" + fData +
                '}';
    }
}

 

二叉树类

package com.nanjing.study.dataStructure;

public class Tree {
    private Node root;

    public Tree(Node root) {
        if (root == null) {
            this.root = new Node(new Person(100, 0), null, null);
        }
    }


    //二叉树特点，当前节点左节点的值<当前节点的值<当前节点右节点的值
    public Node find(int key) {
        Node current = root;
        while (current.person.iData != key) {
            if (current.person.iData > key) {
                current = current.leftNode;
            } else if (current.person.iData < key) {
                current = current.rightNode;
            }
            if (current == null) {
                return null;
            }
        }
        return current;
    }

    public void insert(int id, double dd) {
        Node newNode = new Node(new Person(id, dd), null, null);
        if (root == null) {
            root = newNode;
        } else {
            Node current = root;
            Node parent;
            while (true) {
                parent = current;
                if (current.person.iData > id) {
                    current = current.leftNode;
                    if (current == null) {
                        parent.leftNode = newNode;
                        return;
                    }
                } else {
                    current = current.rightNode;
                    if (current == null) {
                        parent.rightNode = newNode;
                        return;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Tree tree = new Tree(null);
        tree.insert(12, 11);
        tree.insert(10, 102);
        tree.insert(111, 12);
        tree.insert(105, 86);
        tree.insert(65, 203);
        System.out.println("前序遍历.........");
        preOrder(tree.root);
        System.out.println("中序遍历.........");
        inOrder(tree.root);
        System.out.println("后序遍历.........");
        postOrder(tree.root);
        System.out.println("寻找元素.........");
        System.out.println(tree.find(65).person);
    }

    //前序遍历
    public static void preOrder(Node node) {
        if (node != null) {
            System.out.println(node.person);
            preOrder(node.leftNode);
            preOrder(node.rightNode);
        }
    }

    //中序遍历
    public static void inOrder(Node node) {
        if (node != null) {
            inOrder(node.leftNode);
            System.out.println(node.person);
            inOrder(node.rightNode);
        }
    }

    //后序遍历
    public static void postOrder(Node node) {
        if (node != null) {
            postOrder(node.leftNode);
            postOrder(node.rightNode);
            System.out.println(node.person);
        }
    }

}