Basic concept analysis and code example of Java data structure tree

The storage structure of tree in Java is different from linear structures such as linear table, stack and queue. Tree is a For the parent-child relationship between nodes, you can add a parent field for each node to record the parent of the node

A tree is an abstract data type (ADT) or a data structure that implements this abstract data type, which is used to simulate a data set with tree structure. It is a set with hierarchical relationship composed of n (n > 0) finite nodes. It is called "tree" because it looks like an upside down tree, that is, it has roots facing up and leaves facing down.

Tree definitions and basic terms

definition

A tree is a finite set t of n (n ≥ 0) nodes and satisfies the following conditions when n > 0:

(1) There is only one specific node called root;

(2) When n > 1, the other nodes can be divided into m (M > 0) disjoint finite sets T1, T2,..., TM. Each set Ti (1 ≤ I ≤ m) is a tree and is called a subtree of tree t.

In particular, a tree without any nodes (i.e. n = 0) is called an empty tree.

The following is the structure of a tree:

Basic terms

Node: stores data elements and links to subtrees. It is composed of data elements and references that construct the relationship between data elements. Child node: the root node of the subtree of a node in the tree is called the child node of this node. For example, the child node of a in Figure 1 has b, C and D parent nodes: a node in the tree has a child node (that is, the degree of the node is not 0). This node is called the parent node of its child node, also known as the precursor node. Parent nodes and child nodes are mutual. As shown in Figure 1, the child nodes of a are B, C and D, and the parent nodes of B, C and D are a. Sibling node: a node with the same parent node (i.e. the same precursor) is called a sibling node. As shown in Figure 1, B, B and D are sibling nodes. Degree of node: the number of all subtrees of a node is called the degree of the node. As shown in Figure 1, the degree of a is 3 and the degree of B is 2 Degree of tree: the maximum degree of all nodes in the tree is called the degree of tree, as shown in Figure 1, the degree is 3 Leaf node: a node with a degree of 0 is called a leaf node, also known as a terminal node. For example, K, l, F, G, m, I and j branch nodes in Figure 1: nodes with degree not 0 are called branch nodes, also known as non terminal nodes. As shown in the hierarchy of nodes a, B, C, D, e and h in Figure 1, the number of branches of the path from the root node to a node in the tree is called the hierarchy of the node. The level of the root node is generally 1 (or 0 can be defined by itself). In this way, the level of other nodes is the level of their parent nodes plus 1 Depth of tree: the maximum value of the hierarchy of all nodes in the tree is called the depth of the tree (that is, the hierarchy of the lowest node). Ordered tree and unordered tree: the subtrees of any node in the tree are ordered from left to right, which is called ordered tree, otherwise it is called unordered tree. The abstract data type of tree describes data elements: a collection of data elements with the same characteristics. Structural relationship: the structural relationship between data elements in the tree is determined by the definition of the tree.

Basic operations: the main operations of the tree are

(1) & create tree inttree create 1 empty tree. (2) Destroy tree destroytree (3) construct tree createtree (4) empty tree cleartree (T) set tree T as empty tree. (5) Empty tree treeempty (T) (6) find the depth of the tree treedepth (T) (7) get the tree root (T) (8) get the node value (T, cur_e, & E) put the node cur in the tree_ E is stored in E unit. (9) Data assignment assign (T, cur_, e, value) assigns node value to node cur of tree t_ E. (10) Get the parent (T, cur_e) and return the node cur in the tree t_ E's parent node. (11) Get the leftchild (T, cur_e) of the leftmost child and return to the node cur in the tree t_ E's leftmost child. (12) Get the right sibling (T, cur_e) and return the node cur in the tree t_ E's right brother. (13) Insert subtree insertchild & T, & P, I, c) insert tree c into tree T before the ith subtree where p points to the node. (14) Delete subtree & deletechild, & P, I) delete the ith subtree where p points to the node in tree t. (15) Traversetree (T, visit())

Tree implementation

A tree is a recursive structure. There are generally two representations: child representation and child brother representation. There are many tree implementations, including recursive implementation of generalized tables and binary tree implementation. The most common is to convert the tree into a binary tree using child brother representation.

Let's take the child representation as an example to talk about the implementation of the tree:

Definition and implementation of tree

Tree traversal

There are two ways to traverse a tree

Front root traversal

(1) . access the root node;

(2) . traverse the first subtree of the root node in the order from left to right;

Post root traversal

(1) . traverse the first subtree of the root node in the order from left to right;

(2) . access the root node;

Visit. Java

order. java

Test:

The tree to traverse is as follows:

result:

First node: A is left: false data: a front root traversal: a bl e c f Di L H back root traversal: B Le C F D IL h a

Conclusion:

The above is all about the basic concept analysis and code examples of Java data structure tree in this paper. I hope it will be helpful to you. Interested friends can continue to refer to this website:

Introduction to two methods of finding the image of binary tree by Java programming

Complete code example of red black tree implemented by Java algorithm

Java implementation traverses the tree menu to realize code sharing