GitHub source code sharing

Project homepage: github.com/gozhuyinglo…

Source: github.com/gozhuyinglo…

1. Introduction

We’ve talked about arrays and linked lists, and each of them has its own pros and cons. Let’s review them.

  • Array

Advantages: Very fast access through subscripts.

Disadvantages: Less efficient when you need to retrieve a specific value, or when inserting a value (which moves as a whole)

  • Linked Lists

Advantages: When inserting a value, it is more efficient than an array

Disadvantages: Retrieving a value is still inefficient

In this article, trees can improve the efficiency of data storage and reading.

2. The Tree is very beautiful.

A tree is a nonlinear data structure that contains a finite set of n(n>=1) nodes and (n-1) edges. It’s called a tree because it looks like an upside down tree, meaning it has roots up and leaves down.

3. Characteristics of tree structure

  • Each element of the tree structure is called a node.
  • Each node has zero or more child nodes
  • A node that has no parent is called root.
  • Each non-root node has one and only one parent
  • In addition to the root, each child can be divided into multiple disjoint subtrees
  • Parent nodes are connected by a directed edge (edgeo).

4. Common terms for trees

Use the above figure to understand some common tree terms to deepen your understanding of trees.

  • Node (node)

Each element in the tree structure is called a node, as ABC…… in the figure above M

  • Root node (root)

A node without A parent is called A root node, as shown in the figure above

  • Parent node

The parent node of a node is called its parent node. A node can have at most one parent node. For example, C is the parent node of F in the figure above

  • Child node

The children of a node are called its children. A node can have more than one child, as in the figure above, IJK is a child of E

  • Siblings

Nodes with the same parent are called siblings, such as L and M in the figure above

  • Leaf node

A node with no children is called a leaf node, as shown in BFGLMIJK

  • Edge (dege)

The connections between parent and child nodes are called edges, and the number of edges in a tree is (n-1).

  • The weight of a node

The element value on the node

  • Path

Find the path of the node from root. In the figure above, the path of L is A-D-H-L. The length of a path is the number of paths above it. The length of L path is 3 (n-1).

  • Layer (layer)

The path length equal to the root node is one layer. For example, A is the first layer in the figure above. BCDE is the second layer; FGHIJK is the third tier; LM is the fourth tier

  • Child tree

A tree whose root is A node (other than root) is called A subtree. For example, A tree whose root is E is called A subtree

  • Height of the tree

The maximum number of layers in a tree, the height of which is 4

  • Forest (Words)

Many subtrees form a forest

5. Code implementation

We implemented the tree structure diagram from Chapter 3 in Java code.

The TreeNode class is a node of the tree, where:

  • Element: Stores the element data of the current node
  • FirstChild: points to the firstChild of the current node (e.g. A’s firstChild is B; FirstChild of D is G; G firstChild is null)
  • 12. nextSibling: the nextSibling of the current node (e.g., B’s nextSibling is C; NextSibling of G is H; NextSibling of H is null)

The Tree class implements the initialization and traversal of a Tree. The core of listAll traversal algorithm is recursion. See the code for details

public class TreeDemo {

    public static void main(String[] args) {
        new Tree().initTree().listAll();

    }

    private static class Tree {

        private TreeNode root; / / the roots

        /** * initializes a tree */
        private Tree initTree(a) {

            TreeNode a = new TreeNode("A");
            TreeNode b = new TreeNode("B");
            TreeNode c = new TreeNode("C");
            TreeNode d = new TreeNode("D");
            TreeNode e = new TreeNode("E");
            TreeNode f = new TreeNode("F");
            TreeNode g = new TreeNode("G");
            TreeNode h = new TreeNode("H");
            TreeNode i = new TreeNode("I");
            TreeNode j = new TreeNode("J");
            TreeNode k = new TreeNode("K");
            TreeNode l = new TreeNode("L");
            TreeNode m = new TreeNode("M");

            root = a;

            a.firstChild = b;

            b.nextSibling = c;

            c.nextSibling = d;
            c.firstChild = f;

            d.nextSibling = e;
            d.firstChild = g;

            e.firstChild = i;

            g.nextSibling = h;

            h.firstChild = l;

            i.nextSibling = j;

            j.nextSibling = k;

            l.nextSibling = m;

            return this;
        }


        /** * traverses a tree, starting from root */
        public void listAll(a) {
            listAll(root, 0);
        }

        /** * traverses a tree **@paramNode Tree node *@paramDepth (for auxiliary output) */
        public void listAll(TreeNode node, int depth) {
            StringBuilder t = new StringBuilder();
            for (int i = 0; i < depth; i++) {
                t.append("\t");
            }
            System.out.printf("%s%s\n", t.toString(), node.element);

            // Iterate over the child node first, the child node hierarchy needs +1
            if(node.firstChild ! =null) {
                listAll(node.firstChild, depth + 1);
            }

            // The hierarchy of the sibling nodes remains unchanged
            if(node.nextSibling ! =null) { listAll(node.nextSibling, depth); }}}private static class TreeNode {
        private final Object element; // Current node data
        private TreeNode firstChild; // The first child of the current node
        private TreeNode nextSibling; // Next sibling of the current node

        public TreeNode(Object element) {
            this.element = element; }}}Copy the code

Output result:

A
	B
	C
		F
	D
		G
		H
			L
			M
	E
		I
		J
		K
Copy the code

Get more content

Wechat search: code nong StayUp

Personal homepage: GoZhuyinglong.github. IO