1 Features of binary trees Each node has a maximum degree of 2(a maximum of 2 subtrees). The left and right subtrees are sequential

Binomial trees are faster to understand by using a graph and I’m not going to use the graph above to refer to the difference in the order of traversal of the two binomial trees that we learned from the data structure

  1. Middle-order traversal: middle-order traversal traverses the right subtree in the root node of the left subtree
  2. Pre-traversal: The root node traverses the left subtree before traversing the right subtree
  3. Back-order traversal: back-order traversal the left subtree and back-order traversal the root node of the right subtree
  4. Hierarchy traversal: Access from top to bottom, left to right

Let’s create a binary tree interface

    public interface BinaryTreeInfo {
	/** * who is the root node */
	Object root();
	/** * how to get the left child of the node */
	Object left(Object node);
	/** * how to get the right child of the node */
	Object right(Object node);
	/** * how to print the node */
	Object string(Object node);
}
Copy the code

Next up is an implementation class

public class BinaryTree<E> implements BinaryTreeInfo {

    // Member variables
    protected int size;
    protected Node<E> root;
    
    //node inner class
    protected static class Node<E> {
		E element;
		Node<E> left;
		Node<E> right;
		Node<E> parent;
		public Node(E element, Node<E> parent) {
			this.element = element;
			this.parent = parent;
		}
		
		public boolean isLeaf() {
			return left == null && right == null;
		}
		
		public boolean hasTwoChildren() {
			returnleft ! =null&& right ! =null;
		}
		
		public boolean isLeftChild() {
			returnparent ! =null && this == parent.left;
		}
		
		public boolean isRightChild() {
			returnparent ! =null && this == parent.right;
		}
		
                // Sibling nodes
		public Node<E> sibling() {
			if (isLeftChild()) {
				return parent.right;
			}
			
			if (isRightChild()) {
				return parent.left;
			}
			
			return null;
		}
	}
        
        
        @Override
	public Object root() {
		return root;
	}

	@Override
	public Object left(Object node) {
		return ((Node<E>)node).left;
	}

	@Override
	public Object right(Object node) {
		return ((Node<E>)node).right;
	}

	@Override
	public Object string(Object node) {
		return node;
	}
        
        // Basic method
        public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public void clear() {
		root = null;
		size = 0;
	}
        
        // Traversal processing of elements is passed in by the caller
        public static abstract class Visitor<E> {
		boolean stop;
		/ * * *@return If true, it stops traversing */
		abstract boolean visit(E element);
	}
        
        // preorder traversal recursive call
        public void preorder(Visitor<E> visitor) {
		if (visitor == null) return;
		preorder(root, visitor);
	}
	
	private void preorder(Node<E> node, Visitor<E> visitor) {
		if (node == null || visitor.stop) return;
		// Process the object first
		visitor.stop = visitor.visit(node.element);
                // call recursively
		preorder(node.left, visitor);
		preorder(node.right, visitor);
	}
        
        // middle order traversal
        public void inorder(Visitor<E> visitor) {
		if (visitor == null) return;
		inorder(root, visitor);
	}
	
	private void inorder(Node<E> node, Visitor<E> visitor) {
		if (node == null || visitor.stop) return;
		
		inorder(node.left, visitor);
		if (visitor.stop) return;
		visitor.stop = visitor.visit(node.element);
		inorder(node.right, visitor);
	}
        
        // after the sequence traversal
        public void postorder(Visitor<E> visitor) {
		if (visitor == null) return;
		postorder(root, visitor);
	}
	
	private void postorder(Node<E> node, Visitor<E> visitor) {
		if (node == null || visitor.stop) return;
		
		postorder(node.left, visitor);
		postorder(node.right, visitor);
		if (visitor.stop) return;
		visitor.stop = visitor.visit(node.element);
	}
        
        // Hierarchy traversal uses queues
        public void levelOrder(Visitor<E> visitor) {
		if (root == null || visitor == null) return;
		
		Queue<Node<E>> queue = new LinkedList<>();
		queue.offer(root);
		
		while(! queue.isEmpty()) { Node<E> node = queue.poll();if (visitor.visit(node.element)) return;
			
			if(node.left ! =null) {
				queue.offer(node.left);
			}
			
			if(node.right ! =null) { queue.offer(node.right); }}}// The precursor node
        protected Node<E> predecessor(Node<E> node) {
		if (node == null) return null;
		
		/ / precursor of node in the left subtree (left, right. Right. Right...).
		Node<E> p = node.left;
		if(p ! =null) {
			while(p.right ! =null) {
				p = p.right;
			}
			return p;
		}
		
		// Find the precursor node from the parent node and the grandfather node
		while(node.parent ! =null && node == node.parent.left) {
			node = node.parent;
		}

		// node.parent == null
		// node == node.parent.right
		return node.parent;
	}
        
        // The previous node in the sequential traversal of the succeeding nodes
        // If it is a binary search tree, it is a node smaller than it
        < span style = "box-sizing: inherit! Important; word-break: inherit! Important
        // The right subtree of a node containing the parent node starts with a left turn to the right
        protected Node<E> successor(Node<E> node) {
		if (node == null) return null;
		
		// The successor node is in the left subtree (right.left.left.left....)
		Node<E> p = node.right;
		if(p ! =null) {
			while(p.left ! =null) {
				p = p.left;
			}
			return p;
		}
		
		// Find the direction of the successor node from the parent node and the grandfather node
		while(node.parent ! =null && node == node.parent.right) {
			node = node.parent;
		}

		return node.parent;
	}
        
        // Whether to use hierarchy traversal for complete binary trees
        public boolean isComplete() {
		if (root == null) return false;
		Queue<Node<E>> queue = new LinkedList<>();
		queue.offer(root);
		
		boolean leaf = false;
		while(! queue.isEmpty()) { Node<E> node = queue.poll();if(leaf && ! node.isLeaf())return false;

			if(node.left ! =null) {
				queue.offer(node.left);
			} else if(node.right ! =null) {
				return false;
			}
			
			if(node.right ! =null) {
				queue.offer(node.right);
			} else { // All nodes traversed must be leaf nodes
				leaf = true; }}return true;
	}
        
        // Find the height using hierarchy traversal
        public int height() {
		if (root == null) return 0;
		
		// Height of the tree
		int height = 0;
		// Store the number of elements in each layer
		int levelSize = 1;
		Queue<Node<E>> queue = new LinkedList<>();
		queue.offer(root);
		
		while(! queue.isEmpty()) { Node<E> node = queue.poll(); levelSize--;if(node.left ! =null) {
				queue.offer(node.left);
			}
			
			if(node.right ! =null) {
				queue.offer(node.right);
			}

			if (levelSize == 0) { // Indicates that the next layer is about to be accessedlevelSize = queue.size(); height++; }}returnheight; }}Copy the code