On binary tree

Catalog

 

1. Tree structure

 1.1 Definition

1.2 Tree representation

1.3 The application of tree

2. The binary tree theorem

2.1 Concept

2.2  Two special binary trees

2.2 Properties of binary trees

2.3 Binary tree storage

2.6 Traversal of binary tree

2.7 Sequence traversal

---

1. Tree structure

Trees are a kind of nonlinear Data structure of , It is from n（n>=0） Finite nodes make up a set with hierarchical relations . It is called a tree because it looks It looks like an upside down tree , That is to say, it is root up , And leaf down . It has the following characteristics ：

     1）    There's a special node , Called the root node , The root node does not have a precursor node

     2）    Except for the root node , The remaining nodes are divided into M(M > 0) Disjoint sets T1、T2、......、Tm, Every one of them                 Sets   close Ti (1 <= i <= m) Another subtree similar to a tree . The root node of each subtree has only one drive ,                  There can be  0 One or more successors

    3）     Trees are defined recursively .

         

 1.1 Definition

Degree of node ： The number of subtrees a node contains is called the degree of the node ; Pictured above ：A For the 6

The degree of a tree ： In a tree , The degree of the largest node is called the degree of the tree ; Pictured above ： The degree of the tree is 6

Leaf node or terminal node ： Degree is 0 A node of is called a leaf node ; Pictured above ：B、C、H、I... Equal nodes are leaf nodes

Parent node or parent node ： If a node has child nodes , This node is called the parent of its child ; Pictured above ：A yes B Parent node

Child node or child node ： The root node of the subtree that a node contains is called the child node of the node ; Pictured above ：B yes A The child node of

Root node ： In a tree , Nodes without parents ; Pictured above ：A

Hierarchy of nodes ： Starting from the root , The root for the first 1 layer , The child node of the root is the 2 layer , And so on

The height or depth of a tree ： The maximum level of nodes in the tree ; Pictured above ： The height of the tree is 4

Non terminal node or branch node ： The degree is not for 0 The node of ; Pictured above ：D、E、F、G... Such nodes are branch nodes

Brother node ： Nodes with the same parent are called siblings ; Pictured above ：B、C It's a brother node

Cousin node ： The nodes of both parents on the same layer are cousins to each other ; Pictured above ：H、I Be brothers to each other

The ancestor of node ： From the root to all nodes on the branch through which the node passes ; Pictured above ：A Is the ancestor of all nodes

descendants ： Any node in a subtree with a node as its root is called the descendant of the node . Pictured above ： All nodes are A The descendants of

The forest ： from m（m>=0） A collection of trees that do not intersect each other is called a forest

1.2 Tree representation

Tree structure is more complex than linear table , It's more troublesome to store and represent , In fact, there are many representations of trees , Such as ： Parenting , Child representation 、 Child brother notation and so on . Let's briefly understand the most commonly used Child brother notation .

class Node {
 int value; //  Data stored in the tree 
 Node firstChild; //  The first child quoted 
 Node nextBrother; //  The next brother quotes 
}

1.3 The application of tree

Used for file system management ： Directories and files

2. The binary tree theorem

2.1 Concept

A binary tree is a finite set of nodes , The set is either empty , Or it's a root node plus two binary trees called left and right subtrees .

Characteristics of binary trees ：

1. Each node has at most two subtrees , In other words, the degree of nonexistence of binary tree is greater than 2 The node of .

2. The subtree of a binary tree has left and right branches , The order of its subtrees cannot be reversed , So a binary tree is an ordered tree .

Be careful ： For any binary tree, it is composed of the following cases

2.2  Two special binary trees

1. Full binary tree : A binary tree , If The node number of each layer reaches the maximum , Then this binary tree is full of binary trees . in other words , If The number of layers of a binary tree is K, And the total number of nodes is 2^k - 1, Then it's full of binary trees .

2. Perfect binary tree : A complete binary tree is an efficient data structure , A complete binary tree is derived from a full binary tree . For a depth of K Of , Yes n A binary tree of nodes , If and only if each of its nodes has a depth of K From the full binary tree of 1 to n Node i of A corresponding time is called a complete binary tree . It should be noted that a full binary tree is a special kind of complete binary tree .

2.2 Properties of binary trees

1. If specified The number of layers of the root node is 1, Then a tree It's not the second of an empty binary tree i layer （ depth ） There are at most 2^i - 1 (i>0) Nodes .

2. If only The depth of the root node's binary tree is 1, be Depth is K The number of nodes in a binary tree is the largest 2^k - 1 (k>=0)

3. Any binary tree , If it The number of leaf nodes is n0, Degree is 2 The number of non leaf nodes is n2, Then there are n0＝n2＋1

4. have n The depth of a complete binary tree of nodes k by Round up

5. Those who have n Complete binary tree of nodes , If according to From top to bottom, from left to right, for all nodes 0 Numbered starting , For Serial number is  i There are ：

if i>0, Parental serial number ：(i-1)/2;i=0,i Number the root node , No parent nodes

if 2i+1<n, Left child serial number ：2i+1, Otherwise no left child

if 2i+2<n, Right child number ：2i+2, Otherwise no right child

2.3 Binary tree storage

Binary tree storage structure It is divided into ： Sequential storage and Linked storage similar to linked list

The chain storage of binary tree is referenced by nodes one by one , The common expressions are binary and trigeminal , As follows ：

//  Child representation 
class Node {
 int val; //  Data fields 
 Node left; //  Left child's quote , It often represents the whole left sub tree rooted by the left child 
 Node right; //  Right child's quote , It often represents the whole right subtree with the right child as the root 
}

//  The expression of children's parents 
class Node {
 int val; //  Data fields 
 Node left; //  Left child's quote , It often represents the whole left sub tree rooted by the left child 
 Node right; //  Right child's quote , It often represents the whole right subtree with the right child as the root 
 Node parent; //  The root node of the current node 
}

2.6 Traversal of binary tree

Traverse (Traversal) It means following a certain search route , Each node in the tree is visited once and only once . The operations done by the access node Depending on the specific application problem ( such as ： Print node content 、 Node content plus 1). Traversal is one of the most important operations on a binary tree , It is the basis of other operations on binary trees .

According to the order of traversing the root node, there are the following traversal methods ：

1. The former sequence traversal (Preorder Traversal Also called preorder traversal )—— Root node ---> The left subtree of the root ---> Right subtree of root .

2. In the sequence traversal (Inorder Traversal)—— The left subtree of the root ---> The root node ---> Right subtree of root .

3. After the sequence traversal (Postorder Traversal)—— The left subtree of the root ---> Right subtree of root ---> The root node .

  The first binary tree

 

Lesson 2 binary tree  

 

before 、 in 、 Post traversal , Using recursive methods is to print the root .

 1） The former sequence traversal

Solution 1

  void preOrder(BTNode root) {
        if(root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

  Solution 2 ： Non recursive method

void preorderNor(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        while (cur != null || stack.isEmpty()) {
            while (cur != null) {
                // Into the stack 
            stack.push(cur);
            // Put the stack elements into the sequence table 
            ret.add(cur.val);
            cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return ret;
     }

 2） In the sequence traversal

Solution 1

void inOrder(BTNode root) {
        if(root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

Solution 2 ： Non recursive method

void inorderNor(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        while (cur != null || stack.isEmpty()) {
            while (cur != null) {
                // Into the stack 
            stack.push(cur);
            
            cur = cur.left;
            }
            TreeNode top = stack.pop();
            // Put the top element of the stack into the sequence table 
            ret.add(top.val);
            cur = top.right;
        }
        return ret;
     }

3） After the sequence traversal

Solution 1

 // After the sequence traversal 
    void postOrder(BTNode root) {
        if(root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

  Solution 2 ： Non recursive method

void inorderNor(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;

        TreeNode prev = null;
        while (cur != null || stack.isEmpty()) {
            while (cur != null) {
                // Into the stack 
            stack.push(cur);
            
            cur = cur.left;
            }
            // Read the top element of the stack 
            TreeNode top = stack.peek();
            if () {
                stack.pop();
                
                ret.add(top.val);
                prev = top;
            }else {
                  cur = top.right;
            }          
        }
        return ret;
     }

Be careful ：

Know the preorder traversal and In the sequence traversal , Find the post order traversal ：

First, get the root from the front of the preorder traversal , Then take the root and find it in the sequence traversed by the middle order , To the left of the root is the left subtree , To the right of the root is the right subtree . In turn, cycle .

Know the postorder traversal and In the sequence traversal , Find the post order traversal ：

First, get the root from the back of the sequence traversal , Then take the root and find it in the sequence traversed by the middle order , To the left of the root is the left subtree , To the right of the root is the right subtree . In turn, cycle .

2.7 Sequence traversal

Let the level of the root node of the binary tree be 1, Sequence traversal starts from the root node of the binary tree , First visit the root node of the first layer , And then from From left to right, visit page 2 Nodes on the layer , Then there are the nodes of the third layer , And so on , From top to bottom , The process of accessing the nodes of the tree layer by layer from left to right is Sequence traversal .

  public List<List<Integer>> levelOrder(TreeNode root) {
    	List<List<Integer>> ret = new ArrayList<>();
    	if (root == null) return ret;

    	Queue<TreeNode> queue = new LinkedList<>();
    	queue.offer(root);
    	while (!queue.isEmpty) {
    		int size = queue.size();// How many nodes are there in the current layer 
    		List<Integer> lst = new ArrayList<>();

    		while (size != 0) {
    			TreeNode cur = queue.poll();
    			list.add(cur.val);
    			if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;
    		}
    		 ret.add(list);
    	}
    	 return ret;
    }