So we’ve been talking about linear table structures, stacks, queues, and so on. Today we are going to talk about a nonlinear table structure called a tree. The Tree data structure is much more complex than the linear table data structure, the content is also more, first of all, let’s start with the Tree. @[toc]
A Tree (Tree)
Tree structure is a kind of nonlinear structure, which is characterized by branching and stratification among data elements.
1. Tree definition
A Tree is a finite set T composed of N (n≥0) nodes. When n=0, T is called an empty Tree. Otherwise, in any non-empty tree T: (1) there is only one specific node, which has no precursor node and is called Root node; (2) The remaining nodes can be divided into m(m≥0) disjoint subsets T1, T2… Tm, where each subset is itself a tree and is called a Subtree of the root.
Note: The definition of a tree is recursive, that is, there are trees within trees. The recursive definition of trees reveals the inherent properties of trees
2. What is tree structure
What is a tree? No good definition is as straightforward as a diagram. So I drew some “trees” in the picture. Let’s see, what are the features of these trees?
3. Why a tree structure
In an ordered array, you can quickly find a specific value, but to insert a new item into the ordered array, you must first find where the new item was inserted, and then move the larger item one bit back to make room for the new item. Similarly, deletion takes time. Obviously, if you’re going to do a lot of inserts and deletes and deletes, you shouldn’t use ordered arrays. On the other hand, you can quickly add and remove items from a linked list, but it’s not easy to find items in a linked list, and you have to access every item in the list from scratch until you find that item, which is a slow process. Trees are data structures that can be inserted and deleted as quickly as linked lists and searched as quickly as ordered arrays
4. Common terms for trees
Node – contains a data element and its tree branching degree, several points to subtree number of tree nodes have degrees – the biggest degree node in the tree Leaf nodes branch – degree zero (the terminal nodes) – node degree is not zero Children and parents – node subtree is called the root of the node’s children, in turn, This node is called the child’s parent siblings — the children’s ancestors and descendants of the same parent — from the root to the branch through which the node passes. Accordingly, any node in a subtree rooted at a node is called a descendant of that node. Hierarchy of nodes – The hierarchy of nodes is defined from the root, which has hierarchy 1 and its children at hierarchy 2… Cousins — the depth of the tree of nodes whose parents are in the same layer — the largest hierarchical ordered tree and unordered tree of nodes in the tree — if the subtrees of each node in the tree are considered to be ordered from left to right (that is, their positions are not interchangeable), the tree is called an ordered tree; Otherwise it is called an unordered tree. Forest — a finite set of m(m≥0) disjoint trees
Binary Tree
There are many kinds of tree structures, but the most commonly used tree is binary tree, the most commonly used tree is binary tree. Each node of a binary tree has a maximum of two children, namely, the left child and the right child. In binary trees, there are two special trees, namely full binary tree and complete binary tree. Full binary tree is a special case of complete binary tree.
1. The definition and characteristics of binary tree
A Binary Tree is a finite set BT of N (n≥0) nodes, which is either an empty set or consists of a root node and two disjoint Binary trees called left and right subtrees respectively. The characteristics of ———————————— binary tree: each node has at most two subtrees (that is, no node with a degree greater than 2); The subtrees of a binary tree can be divided into left and right, and their order cannot be reversed arbitrarily.
2. Some special forms of binary trees
1. Full binary tree: Definition: a full binary tree with a depth of K and 2K-1 nodes. 2. Complete binary tree: Definition: a binary tree with depth K and n nodes is called a complete binary tree if and only if each node corresponds to the nodes numbered from 1 to N in the full binary tree with depth K. Leaf nodes can only occur on the two largest layers of the hierarchy; Feature 2: For any node, if the maximum level of descendants under its right branch is L, the maximum level of descendants under its left branch must be L or L +1
It is suggested to read the picture and understand the text comprehensively
Code creates a binary tree
First, create a Node Node class
package demo5;
/* * node (node) point class */
public class Node {
// The weight of the node
int value;
// Left son (left node)
Node leftNode;
// Right son (right node)
Node rightNode;
// constructor, which assigns weights to the binary tree when initialized
public Node(int value) {
this.value=value;
}
// Set the left son (left node)
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
// Set the right son (right node)
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
Copy the codeNext, create a BinaryTree class, BinaryTree
package demo5;
/* * binary tree Class */
public class BinaryTree {
// Root node root
Node root;
// Set the root node
public void setRoot(Node root) {
this.root = root;
}
// Get the root node
public Node getRoot(a) {
returnroot; }}Copy the codeFinally, create the TestBinaryTree class (which is mainly used to test the main method) to create a binary tree
package demo5;
public class TestBinaryTree {
public static void main(String[] args) {
// Create a tree
BinaryTree binTree = new BinaryTree();
// Create a root node
Node root = new Node(1);
// Assign the root node to the tree
binTree.setRoot(root);
// Create a left node
Node rootL = new Node(2);
// Set the newly created node as a child of the root node
root.setLeftNode(rootL);
// Create a right node
Node rootR = new Node(3);
// Set the newly created node as a child of the root node
root.setRightNode(rootR);
// Create two child nodes for the layer 2 left node
rootL.setLeftNode(new Node(4));
rootL.setRightNode(new Node(5));
// Create two child nodes for the right node of the second layer
rootR.setLeftNode(new Node(6));
rootR.setRightNode(new Node(7)); }}Copy the codeThe following sections of traversal, node finding, and node deletion will all revolve around these three classes
It is not difficult to see that the created binary tree is as follows:
3. Two ways to store binary trees
Binary trees can be stored either chained or array sequentially. Array sequential storage is more suitable for complete binary trees. Other types of binary trees will waste storage space by array storage, so chain storage is more suitable.
Let’s look at the simple, intuitive chain storage method.
Sequential storage of arrays
4. Traversal of binary trees
I’ve talked about the basic definition of binary trees and how to store them. Now let’s look at the very important operation in binary trees, the traversal of binary trees. This is also a very common interview question.
There are three methods of classical traversal: pre-order traversal, mid-order traversal and post-order traversal
Pre-traversal means that, for any node in the tree, the node is printed first, then its left subtree, and finally its right subtree.
Middle-order traversal means that, for any node in the tree, the left subtree is printed first, then itself, and finally the right subtree.
Post-traversal means that, for any node in the tree, the left subtree is printed first, then the right subtree, and finally the node itself.
I’m sure you’re smart enough to realize that a binary tree traversal is a recursive process
On top of the binary tree code we created earlier, let’s iterate through ~ using these three methods
The same method is added to the Node class: you can see that the traversal methods are all recursive
package demo5;
/* * node (node) point class */
public class Node {
/ / = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = began to traverse the = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
// preorder traversal
public void frontShow(a) {
// Iterate over the contents of the current node
System.out.println(value);
/ / the left node
if(leftNode! =null) {
leftNode.frontShow();
}
/ / right node
if(rightNode! =null) { rightNode.frontShow(); }}// middle order traversal
public void midShow(a) {
// Left child node
if(leftNode! =null) {
leftNode.midShow();
}
// The current node
System.out.println(value);
// Right child node
if(rightNode! =null) { rightNode.midShow(); }}// after the sequence traversal
public void afterShow(a) {
// Left child node
if(leftNode! =null) {
leftNode.afterShow();
}
// Right child node
if(rightNode! =null) {
rightNode.afterShow();
}
// The current nodeSystem.out.println(value); }}Copy the codeThe method is then added to the BinaryTree class again, and the added method calls the traversal method in the Node class
package demo5;
/* * binary tree Class */
public class BinaryTree {
public void frontShow(a) {
if(root! =null) {
// Call the forward-traversal frontShow () method of the Node class Noderoot.frontShow(); }}public void midShow(a) {
if(root! =null) {
// Call the midShow() method of the Node class Noderoot.midShow(); }}public void afterShow(a) {
if(root! =null) {
// Call the afterShow() method of the Node class Noderoot.afterShow(); }}}Copy the codeWe’re still testing in the TestBinaryTree class
package demo5;
public class TestBinaryTree {
public static void main(String[] args) {
// Walk the tree forward
binTree.frontShow();
System.out.println("= = = = = = = = = = = = = = =");
// middle order traversal
binTree.midShow();
System.out.println("= = = = = = = = = = = = = = =");
// after the sequence traversal
binTree.afterShow();
System.out.println("= = = = = = = = = = = = = = =");
// preorder search
Node result = binTree.frontSearch(5);
System.out.println(result);
}
Copy the codeIf recursion is not well understood, I can share a small way to learn: I suggest that you can do this breakpoint debugging, step by step, thinking to keep up, carefully examine each step of the operation believe me, you will re-understand recursion! (Paste a picture like the following step by step break point thinking more clearly)
The recursive implementation
Low efficiency
Nonrecursive ergodic algorithm
Analysis of binary tree traversal calculation method:
The basic operation of binary tree traversal algorithm is to visit the root node. No matter which order is traversal, all nodes are accessed. The time complexity of binary tree containing N nodes is O (n). The required auxiliary space is the stack space required in the traversal process, which is at most equal to the depth of the binary tree K times the number of space required by each node. In the worst case, the depth of the tree is the number of nodes N. Therefore, its space complexity is also O(n).
5. Search and delete nodes in binary tree
Just talked about three kinds of binary tree traversal put method, then the search of nodes can also be followed, respectively called pre-order search, middle-order search and post-order search, the following code only before order search as an example, the three search method ideas similar ~
As for deleting nodes, there are three cases:
If the root node is deleted, then the binary tree is completely deleted. If the parent node is deleted, then the subtree formed by the parent node and all its children is deleted. If the leaf node is deleted, then the binary tree is deleted directly
So, I post the complete three classes (create, traverse, find, delete)
It’s still the Node class
package demo5;
/* * node (node) point class */
public class Node {
// The weight of the node
int value;
/ / left son
Node leftNode;
/ / right son
Node rightNode;
// constructor, which assigns weights to the binary tree when initialized
public Node(int value) {
this.value=value;
}
// Set the left son
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
// Set the right son
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
// preorder traversal
public void frontShow(a) {
// Iterate over the contents of the current node
System.out.println(value);
/ / the left node
if(leftNode! =null) {
leftNode.frontShow();
}
/ / right node
if(rightNode! =null) { rightNode.frontShow(); }}// middle order traversal
public void midShow(a) {
// Left child node
if(leftNode! =null) {
leftNode.midShow();
}
// The current node
System.out.println(value);
// Right child node
if(rightNode! =null) { rightNode.midShow(); }}// after the sequence traversal
public void afterShow(a) {
// Left child node
if(leftNode! =null) {
leftNode.afterShow();
}
// Right child node
if(rightNode! =null) {
rightNode.afterShow();
}
// The current node
System.out.println(value);
}
// preorder search
public Node frontSearch(int i) {
Node target=null;
// Compare the value of the current node
if(this.value==i) {
return this;
// The value of the current node is not the node to look for
}else {
// Find the left son
if(leftNode! =null) {
// Target is still null
target = leftNode.frontSearch(i);
}
// If it is not empty, it is found in the left son
if(target! =null) {
return target;
}
// Find the right son
if(rightNode! =null) { target=rightNode.frontSearch(i); }}return target;
}
// Delete a subtree
public void delete(int i) {
Node parent = this;
// Judge the left son
if(parent.leftNode! =null&&parent.leftNode.value==i) {
parent.leftNode=null;
return;
}
// Determine the right son
if(parent.rightNode! =null&&parent.rightNode.value==i) {
parent.rightNode=null;
return;
}
// Recursively check and delete the left son
parent=leftNode;
if(parent! =null) {
parent.delete(i);
}
// Recursively check and delete the right son
parent=rightNode;
if(parent! =null) { parent.delete(i); }}}Copy the codeIt’s still a BinaryTree
package demo5;
/* * binary tree Class */
public class BinaryTree {
// Root node root
Node root;
// Set the root node
public void setRoot(Node root) {
this.root = root;
}
// Get the root node
public Node getRoot(a) {
return root;
}
public void frontShow(a) {
if(root! =null) {
// Call the forward-traversal frontShow () method of the Node class Noderoot.frontShow(); }}public void midShow(a) {
if(root! =null) {
// Call the midShow() method of the Node class Noderoot.midShow(); }}public void afterShow(a) {
if(root! =null) {
// Call the afterShow() method of the Node class Noderoot.afterShow(); }}// find node I
public Node frontSearch(int i) {
return root.frontSearch(i);
}
// Delete node I
public void delete(int i) {
if(root.value==i) {
root=null;
}else{ root.delete(i); }}}Copy the codeIt’s still the TestBinaryTree test class
package demo5;
public class TestBinaryTree {
public static void main(String[] args) {
// Create a tree
BinaryTree binTree = new BinaryTree();
// Create a root node
Node root = new Node(1);
// Assign the root node to the tree
binTree.setRoot(root);
// Create a left node
Node rootL = new Node(2);
// Set the newly created node as a child of the root node
root.setLeftNode(rootL);
// Create a right node
Node rootR = new Node(3);
// Set the newly created node as a child of the root node
root.setRightNode(rootR);
// Create two child nodes for the layer 2 left node
rootL.setLeftNode(new Node(4));
rootL.setRightNode(new Node(5));
// Create two child nodes for the right node of the second layer
rootR.setLeftNode(new Node(6));
rootR.setRightNode(new Node(7));
// Walk the tree forward
binTree.frontShow();
System.out.println("= = = = = = = = = = = = = = =");
// middle order traversal
binTree.midShow();
System.out.println("= = = = = = = = = = = = = = =");
// after the sequence traversal
binTree.afterShow();
System.out.println("= = = = = = = = = = = = = = =");
// preorder search
Node result = binTree.frontSearch(5);
System.out.println(result);
System.out.println("= = = = = = = = = = = = = = =");
// Delete a subtree
binTree.delete(4); binTree.frontShow(); }}Copy the codeSo, just to summarize, we’ve learned about a nonlinear table data structure called a tree. There are some common concepts you need to know about trees: root, leaf, parent, child, and sibling nodes, as well as the height, depth, number of layers of nodes, and the height of the tree. The most common tree we use is a binary tree. Each node of a binary tree has a maximum of two children, namely, the left child and the right child. In binary trees, there are two special trees, namely full binary tree and complete binary tree. Full binary tree is a special case of complete binary tree. Binary trees can be stored either chained or array sequentially. Array sequential storage is suitable for complete binary trees, other types of binary trees using array storage will waste storage space. In addition to that, the very important operations in binary trees are the front, middle, and back traversal, traversal in order O(n) time, and you need to understand and implement it in recursive code.
If this article is helpful to you, even a little bit, please give a thumbs up. Thank you
Welcome to pay attention to my public number, discuss technology together, yearning for technology, the pursuit of technology… Said come is a friend oh…
