Tree structure and Java implementation

directory

• preface
• The concept of tree
  • An overview of the
  • The term
  • The practical application
• Realize the tree
  • TreeNode
  • TreeNodeIterator
  • test
• conclusion
• A link to the
  • The author resources
  • The resources

preface

When it comes to the “tree” data structure, I believe that many people first think of “binary tree”.

Indeed, as an important data structure, binary tree combines the advantages of array and linked list and has many important applications.

As we all know, arrays are quick to query and can quickly locate an element based on index. However, if you want to insert an element, you need to move all elements after that element position back. On average, an ordered array of length N moves N over 2 elements. The time complexity of an ordered array is O(N) for insert and O(N) for delete.

Ordered arrays are not recommended for data that is frequently inserted or deleted.

Linked lists can be inserted and deleted efficiently by changing references to a few values in O(1) time. But the query efficiency of linked list is very low, each time to start from scratch, access each data item of linked list in turn. On average, to query an element from a list of N elements, it takes N over 2 elements to traverse in order time.

Linked lists are not recommended for frequently looking up data.

Instead of introducing binary trees, this section will focus on trees as data structures. With the knowledge in this section as a foundation, it will be much easier to understand binary trees.

The concept of tree

An overview of the

In computer science, a tree (English: tree) is an abstract data type (ADT) or a data structure that implements such an abstract data type, used to simulate a collection of data that has a tree-like structure.

It is composed of n (n>0) finite nodes to form a hierarchical set.

It’s called a tree because it looks like an upside-down tree, meaning it has roots up and leaves down.

It has the following characteristics:

Each node has limited or no children. A node without a parent is called the root node. Each non-root node has one and only one parent; In addition to the root node, each child node can be divided into multiple disjoint subtrees. There is no cycle in a tree — Wikipedia

By tree definition, the following structure is not a tree:

The term

• The path

All the nodes that pass from one node to another are the paths between the two nodes.

• The root

The nodes at the top of the tree are called roots. There is only one path from the root to any node.

• The parent node

In addition to the root node, each node can be traced up to a unique node, which is the parent of the current node. Accordingly, below the parent node is the child node.

• A leaf node

A “light rod commander” with no children is called a leaf node.

• subtree

Each tree whose child is the root is a child tree.

• layer

The algebra of a tree structure is the layers of the tree.

• The degree of

The degree of the largest node in a tree is called the degree of the tree.

• Brother nodes

Nodes with the same parent node are called sibling nodes.

The practical application

Tree structure has a very wide range of applications, such as our common file directory system, is a tree structure.

For example, enter the tree command in the CMD command line of Windows10 to output the directory tree:

Tree volume list Windows folder PATH volume serial number is 1 ceb - 7 Abe C:. ├ ─ blog │ ├ ─ cache │ │ └ ─ JavaCacheGuidance │ ├ ─ datastructure │ ├ ─ editor │ │ └ ─ notepad + + │ ├ ─ framework │ │ └ ─ guava │ │ └ ─ retry │ ├ ─ git │ └ ─ Java │ └ ─ package - info ├ ─ category │ ├ ─ food │ │ ├ ─ fruit │ │ └ ─ self │ ├ ─ job │ │ └ ─ bz │ │ └ ─ project │ │ └ ─ AD │ │ └ ─ exch │ ├ ─ people │ ├ ─ practical │ │ └ ─ work │ │ └ ─ ecommerce │ │ └ ─ the inventory │ ├ ─ tech │ │ ├ ─ algorithm │ │ │ └ ─ tree │ │ └ ─ Java │ │ ├ ─ concurrent │ │ │ └ ─ thread │ │ ├ ─ design │ │ ├ ─ i18n │ │ ├ ─ JCF │ │ └ ─ spring │ │ └ ─ springboot │ └ ─ tool │ ├ ─ data │ │ └ ─ db │ │ ├ ─ mysql │ │ └ ─ redis │ └ ─ site │ └ ─ stackoverflow └ ─ the me └ ─ phonephotoCopy the code

Realize the tree

After explaining the characteristics and related concepts of tree structure, the following uses Java to implement the basic operations of tree structure, and demonstrates the operation of creating a tree, adding child nodes, traversing the tree, and searching for specified nodes.

TreeNode

package net.ijiangtao.tech.algorithms.algorithmall.datastructure.tree;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/** * implements tree structure **@author ijiangtao
 * @createBut * * / 2019-04-18
public class TreeNode<T> implements 可迭代<TreeNode<T>> {

    /** * tree node */
    public T data;

    /** * parent, root has no parent */
    public TreeNode<T> parent;

    /** * child node, leaf node has no child node */
    public List<TreeNode<T>> children;

    /** * saves the current node and all its children, which is convenient to query */
    private List<TreeNode<T>> elementsIndex;

    /** * constructor **@param data
     */
    public TreeNode(T data) {
        this.data = data;
        this.children = new LinkedList<TreeNode<T>>();
        this.elementsIndex = new LinkedList<TreeNode<T>>();
        this.elementsIndex.add(this);
    }

    /** * Root: root has no parent node **@return* /
    public boolean isRoot(a) {
        return parent == null;
    }

    /** * Check whether it is a leaf node: the child node has no child node **@return* /
    public boolean isLeaf(a) {
        return children.size() == 0;
    }

    /** * add a child node **@param child
     * @return* /
    public TreeNode<T> addChild(T child) {
        TreeNode<T> childNode = new TreeNode<T>(child);

        childNode.parent = this;

        this.children.add(childNode);

        this.registerChildForSearch(childNode);

        return childNode;
    }

    /** * gets the layer ** of the current node@return* /
    public int getLevel(a) {
        if (this.isRoot()) {
            return 0;
        } else {
            return parent.getLevel() + 1; }}/** * Recursively adds a new node to the current node and to all of its parents **@param node
     */
    private void registerChildForSearch(TreeNode<T> node) {
        elementsIndex.add(node);
        if(parent ! =null) { parent.registerChildForSearch(node); }}/** * Searches for a node ** from the current node and all its children@param cmp
     * @return* /
    public TreeNode<T> findTreeNode(Comparable<T> cmp) {
        for (TreeNode<T> element : this.elementsIndex) {
            T elData = element.data;
            if (cmp.compareTo(elData) == 0)
                return element;
        }

        return null;
    }

    /** * gets the iterator ** for the current node@return* /
    @Override
    public Iterator<TreeNode<T>> iterator() {
        TreeNodeIterator<T> iterator = new TreeNodeIterator<T>(this);
        return iterator;
    }

    @Override
    public String toString(a) {
        returndata ! =null ? data.toString() : "[tree data null]"; }}Copy the code

TreeNodeIterator

package net.ijiangtao.tech.algorithms.algorithmall.datastructure.tree;

import java.util.Iterator;

/** ** iterator **@author ijiangtao
 * @createIn the 2019-04-18 s and the * * /
public class TreeNodeIterator<T> implements Iterator<TreeNode<T>> {

    enum ProcessStages {
        ProcessParent, ProcessChildCurNode, ProcessChildSubNode
    }

    private ProcessStages doNext;

    private TreeNode<T> next;

    private Iterator<TreeNode<T>> childrenCurNodeIter;

    private Iterator<TreeNode<T>> childrenSubNodeIter;

    private TreeNode<T> treeNode;

    public TreeNodeIterator(TreeNode<T> treeNode) {
        this.treeNode = treeNode;
        this.doNext = ProcessStages.ProcessParent;
        this.childrenCurNodeIter = treeNode.children.iterator();
    }

    @Override
    public boolean hasNext(a) {

        if (this.doNext == ProcessStages.ProcessParent) {
            this.next = this.treeNode;
            this.doNext = ProcessStages.ProcessChildCurNode;
            return true;
        }

        if (this.doNext == ProcessStages.ProcessChildCurNode) {
            if (childrenCurNodeIter.hasNext()) {
                TreeNode<T> childDirect = childrenCurNodeIter.next();
                childrenSubNodeIter = childDirect.iterator();
                this.doNext = ProcessStages.ProcessChildSubNode;
                return hasNext();
            } else {
                this.doNext = null;
                return false; }}if (this.doNext == ProcessStages.ProcessChildSubNode) {
            if (childrenSubNodeIter.hasNext()) {
                this.next = childrenSubNodeIter.next();
                return true;
            } else {
                this.next = null;
                this.doNext = ProcessStages.ProcessChildCurNode;
                returnhasNext(); }}return false;
    }

    @Override
    public TreeNode<T> next(a) {
        return this.next;
    }

    /** * Currently, nodes cannot be deleted */
    @Override
    public void remove(a) {
        throw newUnsupportedOperationException(); }}Copy the code

test

The tree structure implemented below is exactly the same as the tree structure in the previous figure.

package net.ijiangtao.tech.algorithms.algorithmall.datastructure.tree;

/**
 * tree
 *
 * @author ijiangtao
 * @create2019-04-18 15:03 * * /
public class TreeDemo1 {

    public static void main(String[] args) {

        System.out.println("* * * * * * * * * * * * * * * * * * * * test through * * * * * * * * * * * * * * * * * * * * * * * * *");

        TreeNode<String> treeRoot = getSetA();
        for (TreeNode<String> node : treeRoot) {
            String indent = createIndent(node.getLevel());
            System.out.println(indent + node.data);
        }

        System.out.println("* * * * * * * * * * * * * * * * * * * * search test * * * * * * * * * * * * * * * * * * * * * * * * *");

        Comparable<String> searchFCriteria = new Comparable<String>() {
            @Override
            public int compareTo(String treeData) {
                if (treeData == null)
                    return 1;
                boolean nodeOk = treeData.contains("F");
                return nodeOk ? 0 : 1; }}; TreeNode<String> foundF = treeRoot.findTreeNode(searchFCriteria); System.out.println("F: parent=" + foundF.parent + ",children=" + foundF.children);

    }

    private static String createIndent(int depth) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            sb.append(' ');
        }
        return sb.toString();
    }

    public static TreeNode<String> getSetA(a) {

        TreeNode<String> A = new TreeNode<String>("A");
        {
            TreeNode<String> B = A.addChild("B");
            TreeNode<String> C = A.addChild("C");
            TreeNode<String> D = A.addChild("D");
            {
                TreeNode<String> E = B.addChild("E");
                TreeNode<String> F = C.addChild("F");
                TreeNode<String> G = C.addChild("G");
                {
                    TreeNode<String> H = F.addChild("H");
                    TreeNode<String> I = F.addChild("I");
                    TreeNode<String> J = F.addChild("J"); }}}returnA; }}Copy the code

• The output

* * * * * * * * * * * * * * * * * * * * test through * * * * * * * * * * * * * * * * * * * * * * * * * A B E C H I J G D F * * * * * * * * * * * * * * * * * * * * search test * * * * * * * * * * * * * * * * * * * * * * * * * F: parent=C,children=[H, I, J]Copy the code

conclusion

In this section, I take you through the important data structure of trees, explain tree-related concepts and terminology, and finally implement basic tree operations for you.

This section will help you with binary trees and the source code for TreeSet and TreeMap in Java.

A link to the

The author resources

• Java implements one-way linked lists
• Stack (Stack) – Java implementation
• Github – Java tree implementation

The resources

• Java Tree Data Structure
• Understanding Java Tree APIs
• Java tree data-structure
• Java data structures and algorithms (2nd edition) by RobertLafore
• Tree (data structure)