We know that data structure can be divided into linear structure and nonlinear structure according to the way of data storage, and trees belong to nonlinear structure.

A tree is a hierarchical set composed of n(n>0) finite nodes. When n=0, it’s called an empty tree.

This data structure is called a tree because it looks like an “upside-down tree,” with roots up and leaves down.

It has the following characteristics:

  • A tree without a parent is called a root
  • Each node can have one or more children
  • Each non-root node has only one parent

Basic terms for trees

  • Degree of node: the number of subtrees of nodes

  • Tree degree: The maximum degree of all nodes in the tree

  • Path and path length: the path from node N1 to nk is a sequence of nodes n1, n2… , nk

    Where ni is the parent of Ni +1. The number of edges a path contains is called the length of the path

  • Hierarchy of nodes: specify that the hierarchy of the root node is 1, and the hierarchy of any other node is the hierarchy of its parent node plus one

  • Tree depth: The maximum level of all nodes in a tree is the depth of the tree

Binary tree

Binary trees are just a special case of trees. The difference is:

  • A binary tree can have at most two nodes per node
  • The nodes in a binary tree are left and right. The order cannot be reversed

Binary trees have the following properties:

  • There are at most 2I-1 nodes at level I of the binary tree
  • A binary tree of depth k, with at most 2K-1 nodes (k>=1)
  • n0 = n2N + 10Is the number of nodes with degree 0, n2 Number of knots of degree 2

Inclined tree

A binary tree where all nodes have only left subtrees is called a left slant tree. All nodes are binary trees with only right subtrees called right-inclined trees. These two are collectively known as inclined trees.

Left oblique tree

Right tree

Full binary tree

In a binary tree. A binary tree is called a full binary tree if all nodes have left and right subtrees and all leaves are on the same level.

Complete binary tree

A binary tree with N nodes is numbered by layers. If the node numbered I (1<= I <=n) is exactly in the same position as the node numbered I in the full binary tree with the same depth, the binary tree is called a complete binary tree.

Properties of complete binary trees:

  • The depth of a complete binary tree with n nodes [log2N] + 1, where log2n is rounded down.

The storage structure of binary trees

The nodes of a binary tree can be stored using a one-dimensional array or a linked list.

Sequential storage

The sequential storage of binary tree is to store the nodes of the binary tree using a one-dimensional array, and the location of the nodes is the subscript index of the array.

Therefore, we know that the sequential storage structure of binary tree has the advantage of high search efficiency, and high efficiency of adding and deleting nodes.

The disadvantage is that when the binary tree structure is not a complete binary tree, it is easy to waste space.

For example, in the case of a slanted tree, most of the locations in the array have no storage nodes, wasting space.

The corresponding one-dimensional array is stored as follows:

Chain store

The chain storage of binary tree is the storage of nodes by linked list.

The structure of a node has one data field and two pointer fields.

Traversal of binary trees

Binary tree traversal means that all nodes in the binary tree are visited in a certain order starting from the root node, so that each node is visited once and only once.

The order of binary tree access can be divided into four types:

  • The former sequence traversal
  • In the sequence traversal
  • After the sequence traversal
  • Sequence traversal

The former sequence traversal

A front-order traversal first visits the root, then the left subtree, and finally the right subtree. When traversing the left and right subtrees, we still visit the root first, then the left subtree, and finally the right subtree.

In the sequence traversal

A middle-order traversal first traverses the left subtree, then the root, and finally the right subtree. When traversing the left and right subtrees, we still traverse the left subtree first, then the root, and finally the right subtree.

After the sequence traversal

Back-order traversal first traverses the left subtree, then the right subtree, and finally the root. When traversing the left and right subtrees, the left subtree is traversed first, then the right subtree, and finally the root.

Level traversal

Hierarchical traversal is traversing a binary tree from top to bottom according to the tree levels.

Binary tree code implementation

Sequential storage

package com.xgc.tree.binarytree.sequentialstoreage;

public class BinaryTree {
	
	Object[] arr;
	
	public void buildTree(Object[] arr) {
		this.arr = arr;
	}
	
	/** * traverses * in order@paramThe root of the root tree */
	public void preOrderTree(a) {
		preOrderTree(0);
	}
	
	private void preOrderTree(int index) {
		if (arr==null || arr.length == 0) return;
		System.out.print(arr[index] + "");
		if((index*2+1)<arr.length){
			preOrderTree(index*2+1);
        }
        if((index*2+2)<arr.length){
        	preOrderTree(index*2+2); }}Middle-order and post-order traversals are similar to pre-order traversals
	// The hierarchy traversal is easier, traversal the number of groups can be done
}
Copy the code

Chain store

package com.xgc.tree.binarytree.linkedstoreage;

/** * the node of the binary tree *@author xgc
 *
 */
public class TreeNode {

	Object data;
	/ / the left node
	TreeNode left;
	/ / right node
	TreeNode right;
	
	public TreeNode(Object data) {
		this.data = data;
	}
	
	public TreeNode(TreeNode left , Object data, TreeNode right) {
		this.left = left;
		this.data = data;
		this.right = right; }}Copy the code
package com.xgc.tree.binarytree.linkedstoreage; @author XGC ** / public class TreeNode {Object data; // TreeNode left; // TreeNode right; public TreeNode(Object data) { this.data = data; } public TreeNode(TreeNode left , Object data, TreeNode right) { this.left = left; this.data = data; this.right = right; }}Copy the code

Testing:

package com.xgc.tree.binarytree.linkedstoreage;

public class BinaryTreeTest {

	public static void main(String[] args) {
		Object[] arr = {1.2.3.4.5.6.7.8.9};
		BinaryTree tree = new BinaryTree();
		TreeNode root = tree.buildTree(arr);
		System.out.print("Sequential traversal");
		tree.preOrderTree(root);
		System.out.println();
		
		System.out.print("Middle order traversal");
		tree.inOrderTree(root);
		System.out.println();
		
		System.out.print("Post-order traversal");
		tree.postOrderTree(root);
		System.out.println();
		
		System.out.print("Hierarchical traversal"); tree.levelOrderTree(root); System.out.println(); }}Copy the code

The result is as follows:

1 2 4 8 9 5 3 6 7 2 4 8 9 5 1 3 6 7 2 4 8 9 5 3 6 7 1 level 1 2 3 3 4 5 6 7 8 9Copy the code

Binary search tree

Binary search tree: a binary tree that can be null. If it is not empty, it has the following properties:

  • The value of all nodes of a non-empty left subtree is less than the value of the root

  • The value of all nodes in a non-null right subtree is greater than the value of the root

  • Both the left and right subtrees are binary search trees

Binary search trees do not have duplicate elements, so they are not inserted when they do.

Binary search tree operation functions are:

  • Insert new node
  • Delete nodes
  • Find maximum and minimum values
  • Finds the node of the specified value

In the above operation, the operation of deleting nodes is more complex, so the implementation of the operation of deleting nodes is introduced, and the other is not introduced, it is ok to see the code.

Discussion on deletion operation classification of binary search tree:

  1. The node to be deleted has no children, i.e. leaves.

    So here we’re going to delete the parent node and we’re going to set the left or right of the parent node to NULL

    “Left” and “right” depend on whether the node being deleted is the left or right of the parent node

If current is the current node to be deleted, we simply set parent. Left to null

  1. The deleted node has a child node

    Assign the child node to the left or right of the parent node to be deleted

  1. The node to be deleted has two child nodes

    This is a complicated case, so we introduce the concept of a successor node.

    Successor node: If the output of a binary tree is traversed in middle order, the next node of any node is the successor node of that node.

    • The successor node is the right node of the node to be deleted

      Replace the node to be deleted with the successor node. Pay attention to the left and right of the deleted node

  • The successor node is the left child of the right child of the node to be deleted

    This is a complicated situation, as you can see from the GIFs

Binary search tree code implementation

package com.xgc.tree.binarysearchtree;

import java.util.LinkedList;
import java.util.Queue;

/** * binary search tree *@author xgc
 *
 */
public class BinarySearchTree {
	
	/** * binary search tree node *@author xgc
	 *
	 */
	private class Node {
        int data; / / data domain
        Node right; / / right subtree
        Node left; / / the left subtree
        
        public Node(int data) {
        	this.data = data;
        }

		public Node(a) {}}// The root of the tree
	private Node root;
	
	/** * Find the corresponding node * in the binary search tree based on the specified value@param data
	 * @return* /
	public Node find(int data) {
		Node current = root;
		while(current.data ! = data) {if (data > current.data) {
				current = current.right;
			}
			if (data < current.data) {
				current = current.left;
			}
			if (current == null) {
				return null; }}return current;
	}
	
	/** * binary search tree insertion *@param data
	 */
	public void insert(int data) {
		// The node to insert
		Node p = new Node(data);
		
		if (root == null) {
			root = p;
		} else {
			Node parent = new Node();
			Node current = root;
			while(true) {
				parent = current;
				
				if (data>current.data) {
					current = current.right;
					if (current==null) {
						parent.right = p;
						return; }}else if(data == current.data) {
					return;
				} else {
					current = current.left;
					if (current==null) {
						parent.left = p;
						return;
					}
				}
			}
		}
	}
	

	/** * Delete the specified data *@param data
	 * @returnCheck whether the deletion succeeded */
	public boolean delete(int data) {
		Node current = root;
		Node parent = new Node();
		
		boolean isRightChild = true;
		
		// Find the node to delete
		while(current.data ! = data) { parent = current;if (data > current.data) {
				current = current.right;
				isRightChild = true;
			} else {
				current = current.left;
				isRightChild = false; }}// The node to be deleted is a leaf
		if (current.right == null && current.left == null) {
			if (current == root) {
				root = null;
			} else {
				if (isRightChild) {
					parent.right = null;
				} else {
					parent.left = null; }}return true;
		}
		// The node to be deleted has only one child
		else if(current.left == null) {
			if (current == root) {
				root = current.right;
			}else if(isRightChild) {
				parent.right = current.right;
			}else {
				parent.left = current.right;
			}
			
			return true;
		}
		else if(current.right == null) {
			if (current == root) {
				root = current.left;
			}else if(isRightChild) {
				parent.right = current.left;
			}else {
				parent.left = current.left;
			}
			
			return true;
		}
		// The node to be deleted has two children
		else {
			Node successor = getSuccessor(current);
			
			if (current == root) {
				root = successor;
			} else if (isRightChild) {
				parent.right = successor;
			} else {
				parent.left  =successor;
			}
			
			successor.left = current.left;
			return true; }}/** * get the descendant of the given node * not only get the descendant of the node, but also adjust the right subtree structure of the deleted node *@param current
	 * @returnThe next node */
	private Node getSuccessor(Node node) {
		Node successorParent = node;
		Node successor = node;
		Node current = node.right;
		
		while(current! =null) {
			successorParent = successor;
			successor = current;
			current = current.left;
		}
		// The successor node is already found
		
		// If the successor is the left child of the right node of the node to be deleted, adjust the right subtree of the node to be deleted
		if(successor ! = node.right) { successorParent.left = successor.right; successor.right = node.right; }return successor;
	}
	
	public void levelOrderTree(a) {
		if (root == null) return;
		Queue<Node> nodes = new LinkedList<>();
		nodes.add(root);
		while(! nodes.isEmpty()) { Node node = nodes.poll(); System.out.print(node.data +"");
			if(node.left ! =null) {
				nodes.add(node.left);
			}
			if(node.right ! =null) { nodes.add(node.right); }}}public void show(Node node) { System.out.println(node.data); }}Copy the code

test

package com.xgc.tree.binarysearchtree;

public class BinarySearchTreeTest {

	public static void main(String[] args) {
		BinarySearchTree tree = new BinarySearchTree();
		tree.insert(5);
		tree.insert(6);
		tree.insert(7);
		tree.insert(3);
		tree.insert(4);
		tree.insert(7);
		
		tree.levelOrderTree();
		
		tree.delete(3);
		
		System.out.println();
		tree.levelOrderTree();
		
		System.out.println();
		tree.show(tree.find(7)); }}Copy the code

The execution result is as follows:

5 3 6 4 7 
5 4 6 7 
7
Copy the code