[原创分享]离散数学 Binary Tree in Java 基本实现

原文转载自：http://bbs.qxinnet.com/thread-25756-1-1.html

刚闲来无事，下个星期二就考Java了。
全部人都考完了，无名都回新山了，只剩下我一个人。。。夜晚，码头，我一个人，看着遥远的家乡。。。
所以没有事情，无聊人又在忙。。。就只好写一个Java吧！
上个学期数学上了数学，学到Tree，Binary Tree 的。。。上个学期原本想用 Java 实现，但基于基础不够好，怎么可能用Array弄出来呢，但现在也要上完基础的Java了，对物件导向也有较深一层的认识，因此我尝试根据我的思考，来编写了这个基本的实现程序。。。
我用英文做了一些注释，大家慢慢看吧！蛮简单的程序。
有问题还是有错误，请指教

class Node {

    public Node parentElement; // parent element of the node

    public Node leftElement; // left child element of the node

    public Node rightElement; // right child element of the node

    public String value; // the value of the node

}

public class TestNode {

    public static void main(String args[]) {

        //String sentence = "The fox is jump over that fence";

        String sentence = "The three fox are jump over that fence";

        

        // Break each word into array

        String word[] = sentence.split(" ");

        

        // Initialize the main tree

        Node node = new Node();

        

        // SetTree

        for(int i=0; i
            if(i == 0) {

                node.value = word[i];

                node.parentElement = null;

            } else

                setNode(node, word[i]);

            

        }

        

        // GetTree

        System.out.println("Demonstration of Mathematic for Computing: Tree");

        System.out.println("Sentence: " + sentence);

        System.out.println("Height of tree: " + getNodeHeight(node));

        System.out.println("Leaf: " + getLeaf(node));

        System.out.println("Parent of jump: " + getParent(node, getNode(node, "jump")).value);

        System.out.println("Parent of fence: " + getParent(node, getNode(node, "fence")).value);

        System.out.println("Height of sub-tree on fox: " + getNodeHeight(getNode(node, "fox")));

    }

    

    // Set the structure of the tree on each node

    // @param Tree of node, word (value)

    public static void setNode(Node node, String word) {

        Node childNode;

        if(node.value != null) {

            childNode = new Node();

            childNode.parentElement = node;

            childNode.value = word;

            

            // compare ignore case

            word = word.toLowerCase();

            node.value = node.value.toLowerCase();

            

            if(word.compareTo(node.value) == 0)

                return; // if equal, break out of method

            else if(word.compareTo(node.value) < 0) {

                if(node.leftElement != null)

                    setNode(node.leftElement, word);

                else

                    node.leftElement = childNode;

                

            } else {

                if(node.rightElement != null)

                    setNode(node.rightElement, word);

                else

                    node.rightElement = childNode;

                

            }

            

        }

    }

    

    // Get node by value

    // @param Tree of node, value

    // @return the node want to get

    public static Node getNode(Node node, String value) {

        Node targetNode = null;

        if(value.equals(node.value))

            targetNode = node;

        else {

            // check if left or right got target, then only one target found only, strange problem, getParent also encountered, maybe not very good

            if(node.leftElement != null)

               targetNode = targetNode == null ? getNode(node.leftElement, value) : targetNode;

            

            if(node.rightElement != null)

               targetNode = targetNode == null ? getNode(node.rightElement, value) : targetNode;

        }

        

        return targetNode;

    }

    

    // Get height of the tree

    // @param Tree node

    // @return height of tree

    public static int getNodeHeight(Node node) {

        int height = 1;

        int leftHeight = 0, rightHeight = 0;

        if(node.leftElement == null && node.rightElement == null)

            return height;

        else {

            if(node.leftElement != null)

                leftHeight += getNodeHeight(node.leftElement);

            

            if(node.rightElement != null)

                rightHeight += getNodeHeight(node.rightElement);

            

        }

        

        return height + Math.max(leftHeight, rightHeight);

    }

    

    // Get number of leafs in the tree

    // @param Tree node

    // @return number of leaf

    public static int getLeaf(Node node) {

        int leaf = 0;

        if(node.leftElement == null && node.rightElement == null)

            return 1;

        else {

            if(node.leftElement != null)

                leaf += getLeaf(node.leftElement);

            

            if(node.rightElement != null)

                leaf += getLeaf(node.rightElement);

            

        }

        

        return leaf;

    }

    

    // Get parent of node by value

    // @param Tree of node, child of node

    // @return the parent of node

    public static Node getParent(Node node, Node childNode) {

        // found that node

        Node parentNode = null;

        

        if(node.value.equals(childNode.value))

            return node.parentElement;

        else {

            if(node.leftElement != null)

                parentNode = parentNode == null ? getParent(node.leftElement, childNode) : parentNode;

           

            if(node.rightElement != null)

                parentNode = parentNode == null ? getParent(node.rightElement, childNode) : parentNode;

            

         }     

        return parentNode;

    }

}