1. Definition of tree:
A tree is a non-linear data structure, which is a set of hierarchical relationships composed of n finite nodes.
* There is a special node, which becomes the root node, and the root node has no predecessor nodes
*Except the root node, other nodes are divided into M mutually disjoint sets T1, T2, …, Tm, where each set Ti (1 * The tree is defined recursively 2. Concept
* Degree of node: The number of subtrees contained in a node is called the degree of the node; as shown in the figure above, the degree of A is 6
* Degree of the tree: In a tree, the maximum value of the degrees of all nodes is called the degree of the tree. As shown in the figure above, the degree of the tree is 6
*Leaf node or terminal node: a node with a degree of 0 becomes a leaf node; as shown in the figure above: B, C, H, I, … are all leaf nodes
*Parent node or parent node: If a node contains child nodes, this node is called the parent node of the child node, as shown in the figure above, A is the parent node of B
*Child node or child node: the root node of the subtree contained in a node is called the child node of the node; as shown in the above figure, B is the byte point of A
*Root node: a node in a book without parent nodes, such as A in the above figure
*Node level: starting from the definition of the root, the root is the first level, the node of the root is the second level, and so on
*Tree height or depth: the maximum level of nodes in the tree; as shown above, the height of the tree is 4
*Non-terminal node or branch node: a node whose degree is not 0, as shown in the above figure D, E, F, G… are all branch nodes
*Sibling nodes: Nodes with the same parent node are sibling nodes; B and C in the above figure are sibling nodes
*Cousin nodes: nodes whose parents are on the same layer are cousins; as shown in H and I in the above figure;
*Ancestor of a node: All nodes passed from the root to this node are the ancestor nodes of this node, as shown in the above figure A is the ancestor of all nodes
*Descendants: Any node in the subtree rooted at a node is a descendant of the node; as shown in the above figure, all nodes are descendants of A
Forest: A collection of m disjoint trees is called a forest
3. Tree simulation implementation
* Defines a class for a tree: child-sibling notation
class Node {
int value; // data stored in the tree
Node firstChild; // first child reference
Node nextBrother; // next brother reference
}
4. Binary tree
A binary tree is a finite set of nodes that:
1, or empty
2. Or it is composed of a root node plus two binary trees called left and right subtrees
As can be seen from the figure above:
* There is no node with degree greater than 2
*The subtrees of the binary tree are divided into left and right, and the order cannot be reversed, so the binary tree is an ordered tree
5. Concept
*Full binary tree: a binary tree, if the node tree of each layer reaches the maximum value, then this tree is a full binary tree, that is, if the number of layers of a tree is K, and the total number of nodes is 2^K-1, Then it is a full binary tree
*Complete binary tree: For a binary tree with a depth of k and n nodes, if and only if each node is a node numbered from 0 to n-1 in a full binary tree with a depth of k – it is called complete when corresponding A binary tree, a full binary tree is a special complete binary tree
6. Properties of Binary Trees
*If the number of layers of the root node is specified as 1, then there are at most 2^(i-1) (i>0) nodes on the i-th layer of a non-empty binary tree
*If the depth of a binary tree with only root nodes is specified as 1, then the maximum number of nodes in a binary tree with a depth of k is 2^k-1 (k>=0)
*For any binary tree, if the number of leaf nodes is n0 and the number of non-leaf nodes with degree 2 is n2, then n0=n2 + 1
*The depth K of a complete binary tree with n nodes is log2(k+1) rounded up
*For a complete binary tree with n nodes, if all nodes are numbered from 0 in order from top to bottom and left to right, then for the node with the sequence number i:
If i>0, parent number: (i-1)/2; i=0, i is the root node number, no parent node
If 2i + 1 If 2i + 1 7. Binary tree storage The storage structure of the binary tree is divided into: sequential storage and linked storage similar to linked lists 8. Simulation implementation of binary tree – child representation 9. Binary tree traversal *NLR: Pre-order traversal (pre-order traversal) – visit the root node —> the left subtree of the root —> the right subtree of the root. * Preorder traversal method 1 Method Two Method 3 – sub-problem thinking *Inorder traversal * Post-order traversal *Number of nodes * Find the number of leaf nodes 1. Sub-problem ideas The sub-problem idea is to divide a big problem into N pieces, for a binary tree, it is divided into two, to solve these sub-problems separately, and finally summarize the solution of the big problem 2. Traverse ideas *Get the number of kth layer nodes * Get the height of the binary tree *Judge whether it is a complete binary tree * Hierarchy traversal *Test class result //Define a class representing a node
public static class TreeNode{
// the value of the current node
int value;
//left node
TreeNode left;
//right node
TreeNode right;
public TreeNode(int value) {
this.value = value;
}
}
public void creat(){
TreeNode node1=new TreeNode(1);
TreeNode node2=new TreeNode(2);
TreeNode node3=new TreeNode(3);
TreeNode node4=new TreeNode(4);
TreeNode node5=new TreeNode(5);
TreeNode node6=new TreeNode(6);
TreeNode node7=new TreeNode(7);
node1.left=node2;
node1.right=node3;
node2.left=node4;
node2.right=node5;
node3.left=node6;
node3.right=node7;
root=node1;
}
public TreeNode root;
*LNR: Inorder traversal – the left subtree of the root —> the root node —> the right subtree of the root.
*LRN: post-order traversal – the left subtree of the root —> the right subtree of the root —> the root node. /**
* Preorder traversal
* @param root
*/
public void preOrder(TreeNode root){
//return if the node is empty
if(root==null){
return;
}
//Preorder traversal: middle left
// handle the root node
System.out.println(root.value);
// handle the left subtree
preOrder(root. left);
// handle the right subtree
preOrder(root.right);
}
//Define a list to save the value of the binary tree node
List<Integer> preOrderlist=new ArrayList<>();
public List<Integer> preOederTree(TreeNode root){
//preorder traversal
if(root==null){
return null;
}
preOrderlist.add(root.value);
preOederTree(root.right);
preOederTree(root. left);
return preOrderlist;
}
public List<Integer> preOrderTree1(TreeNode root){
//Define a list collection
List<Integer> list=new ArrayList<>();
//Preorder traversal sub-problem ideas
if(root==null){
return list;
}
//First add the value of the root node to the list collection
list.add(root.value);
// handle the left subtree
List<Integer> leftNode=preOrderTree1(root. left);
list. addAll(leftNode);
// handle the right subtree
List<Integer> rightNode=preOrderTree1(root.right);
list. addAll(rightNode);
return list;
}
/**
* Inorder traversal
*/
public void minOrder(TreeNode root){
// if the root node is empty return
if(root==null){
return;
}
// handle the left subtree
minOrder(root. left);
// handle the root node
System.out.println(root.value);
// handle the right subtree
minOrder(root.right);
}
//post-order traversal: left-right-root
public void bihindOrder(TreeNode root){
// if the root node is empty return
if(root==null){
return;
}
//handle the left node
bihindOrder(root. left);
//handle the right node
bihindOrder(root.right);
// print the root node
System.out.println(root.value);
}
/**
* Number of nodes
* @param root
* @return
*/
public int size(TreeNode root){
//1. Termination condition, (an empty tree, a leaf node)
if(root==null){
return 0;
}
//2. If there is only one root node, return 1
//3, process the left subtree
int leftTreeNode=size(root. left);
//4, process the right subtree
int rightTreeNode=size(root.right);
// Return the sum of nodes: root node + left node + right node
return 1 + leftTreeNode + rightTreeNode;
}
// Sub-problem ideas, find the number of leaf nodes
public int leafNode(TreeNode root){
if(root==null){
return 0;
}
if(root.left==null & amp; & amp;root.right==null){
//return 1 when the condition is met
return 1;
}
// handle the left subtree
int left=leafNode(root. left);
// handle the right subtree
int right=leafNode(root.right);
// Return the sum of the leaf nodes added left and right
return left + right;
}
public int count;
public int leafNode1(TreeNode root){
if(root==null){
return 0;
}
if(root.left==null & amp; & amp;root.right==null){
count + + ;
}
leafNode1(root. left);
leafNode1(root.right);
return count;
}
//Get the number of kth layer nodes
public int findKNode(TreeNode root, int k){
//If the root node or K==0, return 0
if(root==null||k==0){
return 0;
}
//Query termination condition
if(k==1){
return 1;
}
int leftTree=findKNode(root.left,k-1);
int rightTree=findKNode(root.right,k-1);
return leftTree + rightTree;
}
//Get the height of the binary tree
public int heightTree(TreeNode root){
//If root is 0, return 0
if(root==null){
return 0;
}
//Use the Math.max() method to judge the height of the left and right subtrees
int left=heightTree(root. left);
int right=heightTree(root.right);
int high=Math.max(left,right) + 1;
return high;
}
//Judge whether it is a complete binary tree
public boolean isCompleteTree(TreeNode root){
//Define the queue structure auxiliary save node
Queue<TreeNode> queue=new LinkedList<>();
// first judge the empty condition
if(root==null){
return true;
}
//Enqueue the root node first
queue.offer(root);
// Loop condition: the queue is not empty
while(!queue.isEmpty()){
//The root node is dequeued, save the node
TreeNode node=queue. poll();
if(node!=null) {
//The node is not empty, regardless of whether the left and right nodes are empty, all enter the queue
queue.offer(root.left);
queue.offer(root.right);
}else{
//When the node is empty, all the queue elements will be dequeued,
while(queue.isEmpty()){
//When the dequeue element is not null, it is not a complete binary tree, return false
TreeNode checkNode=queue.poll();
if(checkNode!=null){
return false;
}
}
}
}
//Finally return true
return true;
}
/**
* Hierarchy traversal
* @param root
* @return
*/
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list1=new ArrayList<>();
if(root==null){
return list1;
}
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> list=new ArrayList<>();
int size=queue. size();
while(size>0){
TreeNode node=queue. poll();
list.add(node.value);
if(root. left!=null){
queue.offer(node.left);
}
if(root. right!=null){
queue.offer(node.right);
}
size--;
}
list1. add(list);
}
return list1;
}
public class TextBinaryTree {
public static void main(String[] args) {
Day20221022.Tree.BinaryTree binarytree=new BinaryTree();
binarytree. creat();
System.out.println(binarytree.preOederTree(binarytree.root));
System.out.println("The number of nodes in the binary tree");
System.out.println(binarytree.size(binarytree.root));
System.out.println("The number of subproblems traversing the leaf nodes of the binary tree");
System.out.println(binarytree.leafNode(binarytree.root));
System.out.println("Traverse the number of leaf nodes in the binary tree");
System.out.println(binarytree.leafNode1(binarytree.root));
System.out.println("Query the number of K-layer nodes");
System.out.println(binarytree.findKNode(binarytree.root,2));
System.out.println("Query the height of the tree");
System.out.println(binarytree.heightTree(binarytree.root));
System.out.println("Is it a complete binary tree");
System.out.println(binarytree.isCompleteTree(binarytree.root));
System.out.println("================");
}
}
