Java 中的二叉树

引言

二叉搜索树 (BST) 是一种基于节点的二叉树数据结构，具有以下属性：

• 节点左子树中的所有节点都具有小于该节点键的键。
• 节点右子树中的所有节点都具有大于该节点键的键。
• 左子树和右子树都必须是二叉搜索树。

根据上述属性，自然可以得出每个节点（树中的项目）都具有唯一的键。通常，每个节点表示的信息是一个对象元素。但是，为了排序目的，节点是根据其键而不是其关联记录的任何部分进行比较的。

二叉搜索树相对于其他数据结构的主要优势在于，相关的排序算法和搜索算法（例如中序遍历）可以非常高效。

Using the Code

如引言所述，每个节点都有左节点和右节点。以下是节点应该呈现的样子：

public class BNode {

    public BNode leftBNode,  rightBNode; // the nodes
    public AnyClass anyClass; //the AnyClass objext

    public BNode(AnyClass anyClass ) {//constructor
        this.anyClass= anyClass;
        this.leftBNode = null;
        this.rightBNode = null;
    }

    public void show() {
        //calls the show method of the AnyClass
        System.out.print(anyClass.show());
    }
}

以下是一个简单的类，用于遍历、添加和搜索特定节点值：

public class BinTree {
    BNode theBTRootNode;

    public BinTree() // constructor
    {
        theBTRootNode = null;
    }

    // ------------------ Addition of the node to the BST-------------------
    protected BNode insertAB(BNode theRootNode, BNode myNewNode) {
        if (theRootNode == null) {
            theRootNode = myNewNode;
            //checks if the username is smaller than 
            //the root object, if smaller appends to the left
        } else if (myNewNode.anyClass.surname.compareTo(
                          theRootNode.anyClass.surname) < 0) {
            theRootNode.leftBNode = insertAB(theRootNode.leftBNode, myNewNode);
        } else {
            // else if bigger appends to the right
            theRootNode.rightBNode = 
               insertAB(theRootNode.rightBNode, myNewNode);
        }
        return theRootNode;
    }

    public void insertBST(AnyClass anyClass) {
        BNode anyClassBTNode = new BNode(anyClass);
        //calls insert above
        theBTRootNode = insertAB(theBTRootNode, anyClassBTNode);
    }

    // ------------------ InOrder traversal-------------------
    protected void inorder(BNode theRootNode) {
        if (theRootNode != null) {
            inorder(theRootNode.leftBNode);
            theRootNode.show();
            inorder(theRootNode.rightBNode);
        }
    }

    //calls the method to do in order
    public void inorderBST() {
        inorder(theBTRootNode);
    }

    // ----- Search for key name and  returns ref. 
    //              to BNode or null if not found--------
    protected BNode search(BNode theRootNode, String keyName) {
        //if the root is null returns null
        if (theRootNode == null) {
            return null;
        } else {
            //checks if they are equal
            if (keyName.compareTo(theRootNode.anyClass.surname) == 0) {
                return theRootNode;
            //checks id the key is smaller than the current
            //record  if smaller traverses to the left
            } else if (keyName.compareTo(theRootNode.anyClass.surname) < 0) {
                return search(theRootNode.leftBNode, keyName);
            } else {
                // if bigger traverses to the left
                return search(theRootNode.rightBNode, keyName);
            }
        }
    }

    //returns null if no result else returns 
    //the AnyClass object matched with the keyName
    public AnyClass searchBST(String keyName) {
        BNode temp = search(theBTRootNode, keyName);
        if (temp == null) {
      //noresults found
           return null;
        } else {
         //result found
           return temp.anyClass;
        }
    }
}

关注点

这应该在遍历列表时帮助您实现更快的应用程序。

您可以将此方法添加到 BinTree 类对象中，以将您的列表转换为二叉树。

public void populateBinTree(List theList) {
    //clearing the root as not to append, 
    //if you want to append just remove the below line
    theBTRootNode = null;
   //keeps looping untill reaches the end of the list
    for(int i = 0;i < theList.size();i++)
            Node temporaryNode = null; 
         //inserts in the BST
        insertBST((AnyClass)theList.get(i));
        //goes to the next element
    }
}

历史

• 初始版本。