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
- Middle-order traversal: middle-order traversal traverses the right subtree in the root node of the left subtree
- Pre-traversal: The root node traverses the left subtree before traversing the right subtree
- Back-order traversal: back-order traversal the left subtree and back-order traversal the root node of the right subtree
- 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 codeNext 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