Binary tree concept and related operations (including code implementation)

1. Definition of tree
Tree is a kind of important nonlinear data structure, which is a hierarchical structure defined by branching relationship. Each node has zero or more child nodes; A node without a parent node is called a root node; Each non root node has only one parent node; In addition to the root node, each child node can be divided into multiple disjoint subtrees

2. Related concepts
Degree of node: the number of subtrees contained in a node is called the degree of the node; As shown in the figure above: A is 6
Leaf node or terminal node: a node with a degree of 0 is called a leaf node; As shown in the figure above: nodes B, C, H, I... Are leaf nodes
Parent node: if a node contains child nodes, this node is called the parent node of its child nodes; 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 figure above: B is the child node of A
Tree degree: the degree of the largest node in a tree is called the degree of the tree; As shown in the figure above: the degree of the tree is 6
Height or depth of tree: the maximum level of nodes in the tree; As shown in the figure above: the height of the tree is 4
Forest: a collection of m (m > = 0) disjoint trees is called forest;

3. Basic concept of binary tree
Binary tree is a finite set of nodes, which has at most two nodes. At the same time, the order of left subtree and right subtree cannot be disordered.
4. Complete binary tree and full binary tree

Full binary tree: a binary tree. If the number of nodes in each layer reaches the maximum, the binary tree is a full binary tree. In other words, if the number of layers of a binary tree is K and the total number of nodes is (2^k) -1, it is a full binary tree.

Complete binary tree: a complete binary tree is a highly efficient data structure. A complete binary tree is derived from a full binary tree.
If the depth of the binary tree is set as h, the number of nodes in all other layers (1~h-1) except layer h reaches the maximum (that is, layer 1~h-1 is a full binary tree), and all nodes in layer h are continuously concentrated on the left, which is a complete binary tree.
5. Traversal of binary tree
Preorder traversal (front root traversal): Root - > left - > right
Middle order traversal (middle root traversal): left - > root - > right
Post order traversal (post root traversal): left - > right - > root
Sequence traversal: start from the root, layer by layer, from left to right.
The first, middle and last are named according to the relative position of the root during traversal.

6. The code implements the following binary tree and its traversal and other related operations (recursion):

import java.util.LinkedList;

class Node{//Define a node that contains its own data, references to the left subtree, and references to the right subtree.
     String val;
     Node left;
     Node right;
     public Node(String val){
         this.val = val;
    }
}

public class Mytree { 
    public static Node Tree(){ //Initialize the binary tree and connect manually
        Node a = new Node("A");
        Node b = new Node("B");
        Node c = new Node("C");
        Node d = new Node("D");
        Node e = new Node("E");
        Node f = new Node("F");
        Node g = new Node("G");
        Node h = new Node("H");
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        e.left = g;
        g.right = h;
        c.right = f;
        return a;
    }

    public static void PreOrder(Node root){ //Preorder traversal 
        if (root == null) {
            return;
        }
        System.out.print(root.val+" ");
        PreOrder(root.left);
        PreOrder(root.right);
    }

    public static void MidOrder(Node root){//Middle order traversal
        if (root == null) {
            return;
        }
        MidOrder(root.left);
        System.out.print(root.val+" ");
        MidOrder(root.right);
    }

    public static void LastOrder(Node root){//Postorder traversal
        if (root == null) {
            return;
        }
        LastOrder(root.left);
        LastOrder(root.right);
        System.out.print(root.val+" ");
    }

    public static void LevalOrder(Node root){ //level traversal 
        LinkedList<Node> list = new LinkedList<>(); //Define a linked list to save the number traversed
        if(root == null)return; //If empty, return
        list.add(root);//If it is not empty, add the root to the linked list
        while (list.isEmpty() == false ) {//When the linked list is not empty, the loop outputs the elements in the linked list and continues to traverse until the end of traversal
            Node tem = list.poll();
            System.out.print(tem.val+" ");
            if(tem.left != null){
                list.add(tem.left);
            }
            if(tem.right != null){
                list.add(tem.right);
            }
        }
    }

    public static int Size(Node root){ //Calculate the number of linked list nodes
        if(root == null)return 0;
        int tem = 0;
        tem = 1+Size(root.left)+Size(root.right);
        return tem;
    }

    public static int LeafNode(Node root){//Calculate the number of leaf nodes
        if(root == null)return 0;
        if(root.left == null && root.right == null)return 1;
        return LeafNode(root.left)+ LeafNode(root.right);
    }

    public static int LvelSize(Node root,int k){ //Calculate the number of nodes in layer K
        if(k < 1 || root == null)return 0;
        if(k == 1)return 1;
        return LvelSize(root.left,k-1)+LvelSize(root.right,k-1);
    }

    public static Node Find(Node root,String a){//Find the specified node value
        if(root == null)return null;
        if(root.val.equals(a))return root;
        Node result = Find(root.left,a);
        if(result != null) return result;
        else return Find(root.right,a);
    }


    public static void main(String[] args) { //Test function
        Node root = Tree();
        System.out.print("Preorder traversal:");PreOrder(root);
        System.out.println("");
        System.out.print("Middle order traversal:");MidOrder(root);
        System.out.println("");
        System.out.print("Post order traversal:");LastOrder(root);
        System.out.println("");
        System.out.print("Sequence traversal:");LevalOrder(root);
        System.out.println("");
        System.out.print("Number of nodes:");System.out.print(Size(root));
        System.out.println("");
        System.out.print("The number of leaf nodes is:");System.out.print(LeafNode(root));
        System.out.println("");
        System.out.print("K The number of layer nodes is:");System.out.print(LvelSize(root,3));
        System.out.println("");
        System.out.print("The corresponding node of this value is:");System.out.print(Find(root,"F"));
        System.out.println("");
    }
}

Operation results:

Preorder traversal: A B D E G H C F 
Middle order traversal: D B G H E A C F 
Post order traversal: D H G E B F C A 
Sequence traversal: A B C D E F G H 
Number of nodes: 8
 Number of leaf nodes: 3
K Number of nodes: 3
 The corresponding node of this value is: Node@4554617c

Tags: Java

Posted by izy on Sat, 14 May 2022 06:53:43 +0300