1. The concept of binary trees

  1. There are many kinds of trees, and each node can have at most two child nodes in a form called binary tree.

  2. The children of a binary tree are divided into left and right nodes

  3. Schematic diagram

  1. If all the leaves of the binary tree are in the last layer and the total number of nodes =
    2 n 2^n     – 1    , n is the number of layers, then we call it full binary tree.

  1. If all the leaf nodes of the binary tree are in the last or penultimate layer, and the leaf nodes of the last layer are continuous on the left and the leaf nodes of the penultimate layer are continuous on the right, we call it a complete binary tree

2. Description of binary tree traversal

The following binary tree is traversed using pre-order, middle-order, and post-order.

    1. Fore-order traversal: Outputs the parent node, then traverses the left and right subtrees
    1. Middle-order traversal: First traverses the left subtree, then outputs the parent node, then traverses the right subtree
    1. Back-order traversal: first traverses the left subtree, then the right subtree, and finally outputs the parent node
    1. summary: See the order of the output parent node, to determine whether it is pre-order, mid-order or post-order

2. Create the HeroNode node

class HeroNode {
	private int no;
	private String name;
	private HeroNode left; / / null by default
	private HeroNode right; / / null by default
	public HeroNode(int no, String name) {
		this.no = no;
		this.name = name;
	}
	public int getNo(a) {
		return no;
	}
	public void setNo(int no) {
		this.no = no;
	}
	public String getName(a) {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public HeroNode getLeft(a) {
		return left;
	}
	public void setLeft(HeroNode left) {
		this.left = left;
	}
	public HeroNode getRight(a) {
		return right;
	}
	public void setRight(HeroNode right) {
		this.right = right;
	}
	@Override
	public String toString(a) {
		return "HeroNode [no=" + no + ", name=" + name + "]";
	}
	
	// Write a preorder traversal method
	public void preOrder(a) {
		System.out.println(this); // Output the parent first
		// recursively traverses the left subtree
		if(this.left ! =null) {
			this.left.preOrder();
		}
		// recursively traverses the right subtree forward
		if(this.right ! =null) {
			this.right.preOrder(); }}// middle order traversal
	public void infixOrder(a) {
		
		// Recursively traverses the left subtree in order
		if(this.left ! =null) {
			this.left.infixOrder();
		}
		// Outputs the parent
		System.out.println(this);
		// recursively traverses the right subtree
		if(this.right ! =null) {
			this.right.infixOrder(); }}// after the sequence traversal
	public void postOrder(a) {
		if(this.left ! =null) {
			this.left.postOrder();
		}
		if(this.right ! =null) {
			this.right.postOrder();
		}
		System.out.println(this); }}Copy the code

3. Search the specified node in the binary tree

  1. Write pre-order lookup, mid-order lookup and post-order lookup methods.

  2. The node with heroNO = 5 is searched with three search methods

  3. And analysis of various search methods, respectively compared how many times

  4. Thought analysis diagram

Code implementation

1. Create the HeroNode node

class HeroNode {
	private int no;
	private String name;
	private HeroNode left; / / null by default
	private HeroNode right; / / null by default
	public HeroNode(int no, String name) {
		this.no = no;
		this.name = name;
	}
	public int getNo(a) {
		return no;
	}
	public void setNo(int no) {
		this.no = no;
	}
	public String getName(a) {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public HeroNode getLeft(a) {
		return left;
	}
	public void setLeft(HeroNode left) {
		this.left = left;
	}
	public HeroNode getRight(a) {
		return right;
	}
	public void setRight(HeroNode right) {
		this.right = right;
	}
	@Override
	public String toString(a) {
		return "HeroNode [no=" + no + ", name=" + name + "]";
	}
	

	// preorder traversal search
	/ * * * *@paramNo Find no star@returnReturns the Node if found, or null */ if not
	public HeroNode preOrderSearch(int no) {
		System.out.println("Pre-entry traversal");
		// Compare the current node is not
		if(this.no == no) {
			return this;
		}
		//1. Then determine whether the left child node of the current node is empty. If not, recursively search for the preceding node
		//2. If a node is found, return it
		HeroNode resNode = null;
		if(this.left ! =null) {
			resNode = this.left.preOrderSearch(no);
		}
		if(resNode ! =null) {// we found the left subtree
			return resNode;
		}
		//1. Find the node, then return, if not continue to judge,
		//2. Check whether the right child of the current node is empty. If not, continue the recursive search to the right
		if(this.right ! =null) {
			resNode = this.right.preOrderSearch(no);
		}
		return resNode;
	}
	
	// order traversal search
	public HeroNode infixOrderSearch(int no) {
		// Check whether the left child node of the current node is empty. If not, search recursively
		HeroNode resNode = null;
		if(this.left ! =null) {
			resNode = this.left.infixOrderSearch(no);
		}
		if(resNode ! =null) {
			return resNode;
		}
		System.out.println("Search in middle order");
		If not, compare with the current node. If so, return the current node
		if(this.no == no) {
			return this;
		}
		// Otherwise, continue with the right recursive middle-order search
		if(this.right ! =null) {
			resNode = this.right.infixOrderSearch(no);
		}
		return resNode;
		
	}
	
	// after the order traversal search
	public HeroNode postOrderSearch(int no) {
		
		// Check whether the left child node of the current node is empty, if not, then recursively search
		HeroNode resNode = null;
		if(this.left ! =null) {
			resNode = this.left.postOrderSearch(no);
		}
		if(resNode ! =null) {// found in the left subtree
			return resNode;
		}
		
		// If the left subtree is not found, the right subtree is recursively traversed
		if(this.right ! =null) {
			resNode = this.right.postOrderSearch(no);
		}
		if(resNode ! =null) {
			return resNode;
		}
		System.out.println("Search after entry");
		// If both subtrees are not found, the current node is not
		if(this.no == no) {
			return this;
		}
		returnresNode; }}Copy the code

Binary tree Deletes a specified node

1. The requirements

  1. If the node to be deleted is a leaf node, delete it

  2. If the node to be deleted is a non-leaf node, the subtree is deleted.

  3. Test, delete leaf node 5 and subtree 3.

  4. The deletion analysis is complete

Code 2.

1.HeroNode

	// Delete nodes recursively
	If the node to be deleted is a leaf node, delete the node
	//2. If the node to be deleted is a non-leaf node, delete the subtree
	public void delNode(int no) {
		
		/ / way of thinking
		/* * 1. Since our binary tree is unidirectional, we can determine whether the children of the current node need to be deleted, rather than whether the current node needs to be deleted. Set this.left = null if the left child of the current node is not null, and the left child is deleting the node. If the right child of the current node is not null, and the right child is deleting the node, set this.right= null; 4. If steps 2 and 3 do not remove the node, then we need to recursively delete the left subtree 5. If the node is not removed in step 4, a recursive deletion should be made to the right subtree. */
		// set this.left = null if the left child of the current node is not null, and the left child is to delete the node; And return (end recursive deletion)
		if(this.left ! =null && this.left.no == no) {
			this.left = null;
			return;
		}
		// set this. Right = null if the current node's right child is not null and the right child is to delete the node; And return (end recursive deletion)
		if(this.right ! =null && this.right.no == no) {
			this.right = null;
			return;
		}
		//4. We need to recursively delete the left subtree
		if(this.left ! =null) {
			this.left.delNode(no);
		}
		//5. The right subtree should be recursively deleted
		if(this.right ! =null) {
			this.right.delNode(no); }}Copy the code

2. Define a BinaryTree

class BinaryTree {
	private HeroNode root;

	public void setRoot(HeroNode root) {
		this.root = root;
	}
	
	// Delete the node
	public void delNode(int no) {
		if(root ! =null) {
			// If there is only one root node, the root node should be deleted immediately
			if(root.getNo() == no) {
				root = null;
			} else {
				// Delete recursivelyroot.delNode(no); }}else{
			System.out.println("Empty tree, cannot delete ~"); }}// preorder traversal
	public void preOrder(a) {
		if(this.root ! =null) {
			this.root.preOrder();
		}else {
			System.out.println("Binary tree is empty and cannot be traversed."); }}// middle order traversal
	public void infixOrder(a) {
		if(this.root ! =null) {
			this.root.infixOrder();
		}else {
			System.out.println("Binary tree is empty and cannot be traversed."); }}// after the sequence traversal
	public void postOrder(a) {
		if(this.root ! =null) {
			this.root.postOrder();
		}else {
			System.out.println("Binary tree is empty and cannot be traversed."); }}// preorder traversal
	public HeroNode preOrderSearch(int no) {
		if(root ! =null) {
			return root.preOrderSearch(no);
		} else {
			return null; }}// middle order traversal
	public HeroNode infixOrderSearch(int no) {
		if(root ! =null) {
			return root.infixOrderSearch(no);
		}else {
			return null; }}// after the sequence traversal
	public HeroNode postOrderSearch(int no) {
		if(root ! =null) {
			return this.root.postOrderSearch(no);
		}else {
			return null; }}}Copy the code

test

public static void main(String[] args) {
		// Create a binary tree
		BinaryTree binaryTree = new BinaryTree();
		// Create the desired node
		HeroNode root = new HeroNode(1."Sung river");
		HeroNode node2 = new HeroNode(2."吴用");
		HeroNode node3 = new HeroNode(3."Junyi Lu");
		HeroNode node4 = new HeroNode(4."Lin");
		HeroNode node5 = new HeroNode(5."GuanSheng");
		
		< span style = "max-width: 100%; clear: both
		root.setLeft(node2);
		root.setRight(node3);
		node3.setRight(node4);
		node3.setLeft(node5);
		binaryTree.setRoot(root);
		
		/ / test
// system.out.println (" preorder traversal "); / / 1,2,3,5,4
// binaryTree.preOrder();
		
		/ / test
// system.out. println(" middle traversal "); // system.out.println (" middle traversal ");
//		binaryTree.infixOrder(); // 2,1,5,3,4
//		
// system.out. println(" backorder traversal ");
//		binaryTree.postOrder(); // 2,5,4,3,1
		
		// preorder traversal
		// The number of previous traversals: 4
// system.out. println(" preorder traversal mode ~~~");
// HeroNode resNode = binaryTree.preOrderSearch(5);
//		if (resNode != null) {
Printf (" no=%d name=%s", resNode.getNo(), resNode.getName()); // system.out.printf (" No =%d name=%s", resNode.getNo(), resNode.getName());
// } else {
// system.out. printf(" no hero = %d ", 5);
/ /}
		
		// order traversal search
		// The sequence is traversed 3 times
// system.out. println(" middle order traversal mode ~~~");
// HeroNode resNode = binaryTree.infixOrderSearch(5);
//		if (resNode != null) {
Printf (" no=%d name=%s", resNode.getNo(), resNode.getName()); // system.out.printf (" No =%d name=%s", resNode.getNo(), resNode.getName());
// } else {
// system.out. printf(" no hero = %d ", 5);
/ /}
		
		// after the order traversal search
		// The number of times after the sequence traversal search 2 times
// system.out. println(" backorder traversal ~~~"); // system.out. println(" backorder traversal ~~~");
// HeroNode resNode = binaryTree.postOrderSearch(5);
//		if (resNode != null) {
Printf (" no=%d name=%s", resNode.getNo(), resNode.getName()); // system.out.printf (" No =%d name=%s", resNode.getNo(), resNode.getName());
// } else {
// system.out. printf(" no hero = %d ", 5);
/ /}
		
		// Test a delete node
		
		System.out.println("Traversal before deleting");
		binaryTree.preOrder(); //  1,2,3,5,4
		binaryTree.delNode(5);
		//binaryTree.delNode(3);
		System.out.println("After deletion, preorder traversal");
		binaryTree.preOrder(); / / 1, 2, 3, 4
		
		
		
	}
Copy the code