@[TOC]

Data structure tree and binary tree

The first part Basic knowledge of tree and binary tree

1、 The definition of tree and binary tree

1.1 The definition of a tree

Trees （Tree） yes n（n≥0） A finite set of nodes , It may be an empty tree （n=0）; Or a non empty tree , For non empty trees T：

• （1） There is only one node called root ;
• （2） Except for the root node, the other nodes can be divided into m（m>0） A finite set that doesn't intersect each other T₁,T₂,...,Tm, Each of these combinations is itself a tree , And become the subtree of the root （SubTree）.

　　 　　 chart 1(A) Is a collection stored in a tree structure {A,B,C,D,E,F,G,H,I,J,K,L,M} Schematic diagram . For data A Come on , And data B、C、D It matters ; For data B Come on , and E、F It matters . This is it. “ One to many ” The relationship between . Will have “ One to many ” The data elements in the collection of relationships are shown in Figure 1（A） Storage in the form of , The whole storage shape in terms of logical structure , It's similar to a fallen tree in real life （ chart 1（B） Come back ）, So this storage structure is called “ Tree shape ” Storage structure .

1.2 The basic term for trees

（1） node ： An independent unit in the tree . Contains a data element and branches that point to its subtree , Pictured 1（A） Medium A、B、C、D etc. . （2） The degree of node ： The number of subtrees owned by a node becomes the degree of the node . for example ,A The degree of 3,C The degree of 1,F The degree of 0. （3） The degree of a tree ： The degree of a tree is the maximum degree of each node in the tree . chart 1（A） The degree of the tree shown is 3. （4） leaf ： Degree is 0 The nodes of are called non terminal nodes or branch nodes . Except for the root node , Non terminal nodes also become internal nodes . （5） Non terminal nodes ： The degree is not for 0 A node of is called a leaf or terminal node . node K、L、F、G、M、I、J Leaves from trees . （6） Parents and children ： The root of a node's subtree is called the child of the node , Accordingly , This node is called the parents of children . for example ,B My parents are A,B My children have E and F. （7） brother ： Children of the same parents call each other brothers . for example ,H、I and J Brothers to each other . （8） The ancestors ： All nodes on the branch from the root to the node . for example ,M Our ancestors are A、D and H. （9） descendants ： Any node in a subtree with a node as its root is called the descendant of the node . Such as B The descendants of E、K、L and F. （10） level ： The level of a node is defined from the root , The root is the first layer , The child of root is the second layer . The hierarchy of any node in the tree is equal to the hierarchy of parent nodes plus 1. （11） male cousins ： The nodes of parents on the same level are cousins . for example , node G And E、F、H、I、J Cousins to each other . （12） Depth of tree ： The maximum level of nodes in a tree is called the depth or height of the tree . chart 1（A） The depth of the tree shown is 4. （13） Ordered trees and unordered trees ： If we regard the subtrees of nodes in the tree as having order from left to right （ That is, it cannot be interchanged ）, The tree is called an ordered tree , Otherwise, it is called disordered tree . The root of the leftmost subtree in an ordered tree is called the first child , The one on the far right is called the last child . （14） The forest ： yes m（m≥0） A collection of mutually disjoint trees . For each node in the tree , The collection of its subtrees is the forest . thus , Trees can also be described by recursive definitions of forests and trees .

1.3 The definition of binary tree

Binary tree （Binary Tree） yes n（n≥0） A collection of nodes , It may be an empty tree （n=0）; Or a non empty tree , For non empty trees ： （1） There is only one node called root ; （2） The other nodes except the root node are divided into two disjoint subsets T₁ and T₂, Known as T The left and right subtrees of , And T₁ and T₂ Itself is a binary tree .

Binary trees have the same recursive properties as trees , The difference between a binary tree and a tree There are two main points ： （1） Each node of a binary tree has at most two subtrees （ That is, there is no greater than in the binary tree 2 The node of ）; （2） The subtree of a binary tree has left and right branches , The order cannot be reversed arbitrarily .

The recursive definition of a binary tree indicates that the binary tree is either empty , Or a root node plus two trees called left subtree and right subtree 、 Binary trees that don't want to intersect each other . Because these two subtrees are also binary trees , By the definition of binary tree , They can also be empty trees . thus , A binary tree can have 5 There are three basic forms , As shown in the figure below .

The basic terms of a tree are applicable to binary trees .

2、 Properties and storage structure of binary tree

2.1 Properties of binary trees

A binary tree has the following nature ：

Binary trees also have two special forms , Full binary tree and full binary tree .

• If there is no leaf node in a binary tree , The degree of each node is 2, Then the binary tree is called full binary tree .

• If the last node removed from the binary tree is a full binary tree , And the nodes of the last layer are distributed from left to right , This binary tree is called a complete binary tree .

2.2 Binary tree storage structure

　　 There are two storage structures of binary trees , Respectively Sequential storage and Chain store .

2.2.1 Sequential storage

　　 The sequential storage of binary trees , It refers to the use of a sequence table （ Array ） Store binary trees . It should be noted that , Sequential storage only applies to complete binary trees . let me put it another way , Only a complete binary tree can be stored in a sequence table . therefore , If we want to store ordinary binary trees in order , We need to transform the ordinary binary tree into a complete binary tree in advance .

　　 The method of transforming a normal binary tree into a complete binary tree is very simple , Just add some extra nodes to the binary tree , Put it " Put together " A complete binary tree can be formed . As shown in the figure below , On the left is a normal binary tree , On the right is the transformed complete （ full ） Binary tree .

　　 The problem of binary tree transformation is solved , Next, let's learn how to sequentially store complete （ full ） Binary tree . Sequential storage of complete binary trees , Just start with the root node , Store the nodes in the tree in order .

　　 for example , Store the complete binary tree shown in the figure above , The storage status is shown in the figure below ：

　　 thus , We have realized the sequential storage of complete binary tree .

2.2.2 Chain store

　　 In fact, binary trees are not suitable for array storage , Because not every binary tree is a complete binary tree , There is a waste of space when ordinary binary trees use sequential tables to store . Next, we introduce the chain storage structure of binary tree .

　　 The picture above shows an ordinary binary tree , If we use chain storage , Just start at the root node of the tree , Each node and its left and right children can be stored in a linked list . therefore , The corresponding chain storage structure is shown in the figure below ：

　　 It can be seen from the above figure , When using chain storage binary tree , Its node structure consists of 3 Part of the form ：

• 　　 Pointer to the left child node （Lchild）;
• 　　 Data stored by nodes （data）;
• 　　 Pointer to the right child node （Rchild）;

　　 Actually , The chain storage structure of binary tree is far more than the above figure The one shown . for example , In some practical scenarios , May do " Find the parent node of a node " The operation of , At this time, you can add another pointer field in the node structure , Used for each node to point to its parent node , Here's the picture Shown ：

　　 Use the trigeminal linked list shown in the figure above , We can easily find the parent node of each node . therefore , When solving practical problems , Store the binary tree with an appropriate linked list structure , Can achieve twice the result with half the effort .

2.3 Traversing the binary tree

　　 In some applications of binary trees , It is often required to find nodes with certain characteristics in the tree , Or all nodes in the tree are processed one by one , This raises a problem of traversing binary trees . Traversing the binary tree （traversing binary tree） It refers to visiting each node in the tree according to a certain search path , Each node is accessed once , And only once . The meaning of access is very broad , You can do all kinds of processing on nodes , Including the information of the output node , Operation and modification of nodes, etc . Traversing a binary tree is the most basic operation of a binary tree , It is also the basis of other operations of binary tree , The essence of traversal is the process of linearization of binary tree , That is, the result of traversal is to arrange the nodes in the tree with nonlinear structure into a linear sequence . Because each node of a binary tree may have two subtrees , So we need to find a law , So that the nodes on the binary tree can be arranged in a linear queue , So as to facilitate traversal . 　　 　　 Binary tree has ３ It's made up of three basic units ： The root node 、 Left subtree and right subtree . therefore , If you can traverse these three parts in turn , Is traversing the entire binary tree . If Ｌ、Ｄ、Ｒ Respectively represent traversal left subtree 、 Access the root node and traverse the right subtree , There may be DLR、LDR、LRD、DRL、RDL、RLD this 6 A scheme of traversing binary tree . If the limit is left first and then right , Only the front 3 Medium condition , They are called respectively First （ root ） Order traversal 、 in （ root ） Sequence traversal and post （ root ） Order traversal . 　　 　　 Recursive definition based on binary tree , The following definition of recursive algorithm for traversing binary tree can be obtained . 　　 Traversing a binary tree in order The operation of is defined as follows ： 　　 If binary tree is empty , Empty operation ; otherwise 　　（１） Access the root node ; 　　（２） The order traverses the left subtree ; 　　（３） The order traverses the right subtree . 　　 Middle order ergodic binary tree The operation is defined as follows ： 　　 If binary tree is empty , Empty operation ; otherwise 　　（１） The middle order traverses the left subtree ; 　　（２） Access the root node ; 　　（３） The middle order traverses the right subtree . 　　 Post order traversal binary tree The operation of is defined as follows ： 　　 If binary tree is empty , Empty operation ; otherwise 　　（１） The latter traverses the left subtree ; 　　（２） The latter traverses the right subtree ; 　　（３） Access the root node .

for example , The binary tree in the figure above represents the expression ：a+b*（c-d）-e/f

• If you traverse the binary tree first , We can get the of binary tree Sequence first by ：-+a*b-cd/ef
• Similarly , Traverse the binary tree in middle order , We can get the of this binary tree Middle order sequence by ：a+b*c-d-e/f
• After traversing the binary tree , We can get the of this binary tree Subsequent sequence by ：abcd-*+ef/-

Big assignment one ： The basic operation of binary tree

Building a binary tree （ Traverse the list and insert the values in the binary tree in order ）, use Python Programming is complete , And do the following ：（ Including but not limited to , You can continue to expand according to your ability ）

• Recursive preorder traversal binary tree
• Non recursive preorder traversal binary tree
• Recursively traverses the binary tree in order
• Non recursive traversal of binary trees in middle order
• Recursive postorder binary tree
• Non recursive traversal of binary tree
• Returns the depth of the binary tree
• Returns the number of nodes in a binary tree
• Duplicate binary tree

The final output result requires ：

　　 Input list of test cases by ［'A','B','C','#','#','D','E','#','G','#','#','F','#','#','#'］, The output traversal results are shown in the figure below .

【 notes 】： The generation of binary tree , You need to use the values in the above input list ; For non recursive traversal , Need to use Stack .

Code thinking （ For reference only , Unlimited ideas ）： 　　 The generation of binary tree ： 　　１、 Build node class , Build a binary tree class 　　２、 Enter a list , Then get the data from the list , Recursively insert values in the order of precedence , That is, create the root node first , And then zuozhu , Re right subtree . 　　３、 First enter a character , Judge whether it is ＃, No ＃ Create the root node , The numeric field of the node is the character , Continue to recursively generate the left subtree ,　　 Enter the second character , Judge whether it is ＃, No ＃ A node is generated , yes ＃ Will return the previous level of recursion , This judgment recursively generates a binary tree . 　　 Traversal of binary tree ： According to the first order 、 Middle preface 、 You can output characters in the order of post order traversal , Mainly non recursive traversal needs the help of stack , take The idea of non recursive algorithm for middle order traversal For example ： Define an empty stack , Access... From the root node , If the current node is not empty , Then stack the node and access its left subtree , Loop execution , Until the current node is empty , Take the top element of the stack, access and pop the stack , Then visit its right subtree , Repeat the above operation , Until the pointer to the traversal node is empty and the stack is empty .

Code （ Recursive writing ）：

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/8/18 8:16 
# @Author : vaxtiandao
# @File : Binary tree.py

class Tree():
    def __init__(self, item):
        self.item = item
        self.l = None
        self.r = None

    def llink(self, other):  #  Left connected child node 
        self.l = other

    def rlink(self, other):  #  Right connect child nodes 
        self.r = other

    # def __repr__(self):
    # return str(self.item)+' '+str(self.l)+' '+str(self.r)
    def get_depth(self):  #  Get depth （ recursive ）
        if self.l == None:
            l_depth = 0
        else:
            l_depth = self.l.get_depth()
        if self.r == None:
            r_depth = 0
        else:
            r_depth = self.r.get_depth()
        return max(l_depth, r_depth) + 1

    def get_len(self):  #  Get the number of nodes （ recursive ）
        if self.l == None:
            l_len = 0
        else:
            l_len = self.l.get_len()
        if self.r == None:
            r_len = 0
        else:
            r_len = self.r.get_len()
        return l_len + r_len + 1

    def show_first(self):  #  The first sequence traversal （ recursive ）
        print(self.item, end=' ')
        if self.l != None:
            self.l.show_first()
        if self.r != None:
            self.r.show_first()

    def show_mid(self):  #  In the sequence traversal （ recursive ）
        if self.l != None:
            self.l.show_mid()
        print(self.item, end=' ')
        if self.r != None:
            self.r.show_mid()

    def show_last(self):  #  After the sequence traversal （ recursive ）
        if self.l != None:
            self.l.show_last()
        if self.r != None:
            self.r.show_last()
        print(self.item, end=' ')

    def copy(self):  #  Copy node 
        c_result = Tree(self.item)
        c_result.llink(self.l)
        c_result.rlink(self.r)
        return c_result

    def copy_deep(self):  #  Deep copy the entire tree below the node 
        c_result = Tree(self.item)
        if self.l != None:
            c_result.llink(self.l.copy())
        if self.r != None:
            c_result.rlink(self.r.copy())
        return c_result


def create(x):  #  Create a binary tree from the list 
    try:
        tmp = next(x)
        if tmp == '#':
            return
        root = Tree(tmp)
        root.llink(create(x))
        root.rlink(create(x))
        return root
    except:
        pass


tree_list = ['A', 'B', 'C', '#', '#', 'D', 'E', '#', 'G', '#', '#', 'F', '#', '#', '#']
it = iter(tree_list)
root = create(it)

#  The first sequence traversal 
print(root.show_first())
#  In the sequence traversal 
print(root.show_mid())
#  After the sequence traversal 
print(root.show_last())
 Copy code 

Realization effect ：

Code （ Non recursive , Borrowing stack ）：

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/8/18 8:43 
# @Author : vaxtiandao
# @File : Binary tree2.py

#  Define node class , Contains two members ： Node element value and pointer to the next node 
class SingleNode():
    #  Node class initialization 
    def __init__(self, item):
        self.item = item  # item Store the value of the node 
        self.next = None  #  The next pointer points to 


#  Define chain stack 
class LinkStack():
    #  initialization 
    def __init__(self):
        self.top = None

    #  Determine whether it is null 
    def is_empty(self):
        if self.top == None:
            return True
        else:
            return False

    #  Back to top of stack element 
    def get_element(self):
        if self.is_empty():
            return None
        else:
            return self.top.item

    #  Returns the stack length 
    def get_length(self):
        tmp = self.top
        if tmp == None:
            return 0
        i = 0
        while tmp != None:
            tmp = tmp.next
            i += 1
        return i

    #  Into the stack 
    def add_stack(self, element):
        node = SingleNode(element)
        node.next = self.top  #  Pointer transformation 
        self.top = node

    #  Out of the stack 
    def remove_stack(self):
        if self.is_empty():
            raise IndexError(" Stack empty , Can't get out of the stack ")
        else:
            node = self.top
            self.top = self.top.next
            return node.item

    #  Empty stack 
    def clear_stack(self):
        self.top = None

class Tree():
    def __init__(self,item):
        self.item=item
        self.l=None
        self.r=None
    def llink(self,other): # Left connected child node 
        self.l=other
    def rlink(self,other): # Right connect child nodes 
        self.r=other
    # def __repr__(self):
    # return str(self.item)+' '+str(self.l)+' '+str(self.r)
    def get_depth(self): # Get depth （ recursive ）
        if self.l==None:
            l_depth=0
        else:
            l_depth=self.l.get_depth()
        if self.r==None:
            r_depth=0
        else:
            r_depth=self.r.get_depth()
        return max(l_depth,r_depth)+1
    def get_len(self): # Get the number of nodes （ recursive ）
        if self.l==None:
            l_len=0
        else:
            l_len=self.l.get_len()
        if self.r==None:
            r_len=0
        else:
            r_len=self.r.get_len()
        return l_len+r_len+1
    def show_first(self): # The first sequence traversal （ recursive ）
        print(self.item,end=' ')
        if self.l !=None:
            self.l.show_first()
        if self.r !=None:
            self.r.show_first()
    def show_mid(self): # In the sequence traversal （ recursive ）
        if self.l !=None:
            self.l.show_mid()
        print(self.item,end=' ')
        if self.r !=None:
            self.r.show_mid()
    def show_last(self): # After the sequence traversal （ recursive ）
        if self.l !=None:
            self.l.show_last()
        if self.r !=None:
            self.r.show_last()
        print(self.item,end=' ')
    def copy(self): # Copy node 
        c_result=Tree(self.item)
        c_result.llink(self.l)
        c_result.rlink(self.r)
        return c_result
    def copy_deep(self): # Deep copy the entire tree below the node 
        c_result=Tree(self.item)
        if self.l!=None:
            c_result.llink(self.l.copy())
        if self.r!=None:
            c_result.rlink(self.r.copy())
        return c_result

def create(x): # Create a binary tree from the list 
    try:
        tmp=next(x)
        if tmp=='#':
            return
        root=Tree(tmp)
        root.llink(create(x))
        root.rlink(create(x))
        return root
    except:
        pass


def show_first(tree):  #  Non recursive preorder traversal （ Utilization stack ）
    if tree == None:  #  If the tree is empty , Returns an empty 
        return None
    stack = LinkStack()  #  If the tree is not empty , Use the stack to traverse 
    tmp = tree  # tmp The pointer points to the root node 
    stack.add_stack(tmp)  #  Root node stack 
    while not stack.is_empty():  #  When the stack is not empty , Keep coming out of the stack 
        tmp = stack.remove_stack()
        print(tmp.item, end=' ')  #  Access and print the contents of the current node 
        if tmp.r != None:  #  Stack the child nodes of the current node （ To ensure that the left tree is accessed first , First enter the right node of the stack ）
            stack.add_stack(tmp.r)
        if tmp.l != None:
            stack.add_stack(tmp.l)


def show_mid(tree):  #  Non recursive middle order traversal 
    if tree == None:
        return None
    stack = LinkStack()
    tmp = tree  #  Define pointer 
    while tmp != None or (not stack.is_empty()):  #  Pointer is not null or stack is not null 
        while tmp != None:  #  Stack the current node , And find the leftmost end of the left tree 
            stack.add_stack(tmp)
            tmp = tmp.l
        if not stack.is_empty():  #  Find the leftmost end of the left tree , One node out of the stack , This node is the leftmost node 
            tmp = stack.remove_stack()
            print(tmp.item, end=' ')  #  Access current node 
            tmp = tmp.r  #  The pointer points to the right node 


def show_last(tree):  #  Non recursive postorder traversal （ utilize 2 Stack , In reverse order DRL After visiting the whole tree , Use the second stack to save and reverse the results , You can get the following sequence LRD The results of the visit ）
    if tree == None:
        return None
    stack = LinkStack()
    out_stack = LinkStack()
    tmp = tree
    stack.add_stack(tmp)
    while not stack.is_empty():
        tmp = stack.remove_stack()
        out_stack.add_stack(tmp)  #  Access the stack where the node is merged into the stack and the result is saved 
        if tmp.l != None:
            stack.add_stack(tmp.l)  #  Other parts are similar to the preamble , However, the stacking order of the left and right child nodes needs to be reversed 
        if tmp.r != None:
            stack.add_stack(tmp.r)
    while not out_stack.is_empty():  #  Stack the results , Achieve the reverse order effect 
        print(out_stack.remove_stack().item, end=' ')


tree_list=['A','B','C','#','#','D','E','#','G','#','#','F','#','#','#']
it=iter(tree_list)
root=create(it)

#  The first sequence traversal 
print(root.show_first())
#  In the sequence traversal 
print(root.show_mid())
#  After the sequence traversal 
print(root.show_last())

croot=root.copy()
droot=root.copy_deep()

print(root,root.l,root.r)
print(croot,croot.l,croot.r)
print(droot,droot.l,droot.r)

 Copy code 

Realization effect ：

2.4 Clue binary tree

2.4.1 The concept of threaded binary trees

problem ： Why study clue binary trees ？ 　　 When a binary linked list is used as the storage structure of a binary tree , You can easily find the left and right children of a node ; But generally , The predecessor and successor nodes of this node in some traversal sequence cannot be found directly .

Raise questions ： 　　 How to find the precursors and successors of binary tree nodes in a specific traversal sequence ？

The solution ： 　　１、 Find... By traversing —— Time consuming 　　２、 Add a precursor 、 Subsequent pointer fields —— Increased storage burden . 　　３、 Use the empty finger needle field in the binary chain list .

review ： The number of empty pointer fields in a binary linked list ： 　　 have ｎ In a binary list of nodes , Altogether 2n A pointer to a domain ; because n There are... In nodes n-1 A child , namely 2n In a pointer field , Yes n-1 Two left and right children used to indicate nodes , rest n+1 Pointer fields are null .

Use the empty finger needle field in the binary chain list ： 　　 If the left child of a node is empty , Change the empty left child pointer field to Pointing to its precursors ; If the left child of a node is empty , Change the empty right child pointer field to Point to its successor —— The pointer to which this change points is called “ clue ”, A binary tree with clues is called Clue binary tree （Threaded BinaryTree）.

Try the following rules ： 　　 If the node has a left subtree , Then lchild The field indicates its left child , Otherwise the lchild Domain indicates its precursor ; If a node has a right subtree , Then rchild Field indicates its right child , Otherwise the rchild Domain indicates its successor . To avoid confusion , The node structure needs to be changed , Add two flag fields , The node form is shown in the figure below .

2.4.2 Construct clue binary tree

　　 Because the essence of clue binary tree construction is to change the null pointer in the binary list to point to the precursor or subsequent clue , The precursor or successor information can only be obtained when traversing , Therefore, the process of cueing is the process of modifying the null pointer in the process of traversal , Recursive algorithms are available . Cue the binary tree according to different traversal order , You can get different clues binary tree , Including preorder clue binary tree 、 Middle order threaded binary tree and post order threaded binary tree .

　　 The binary linked list composed of the above node structure is used as the storage structure of the binary tree , It's called a clue list , Where the pointer to the precursor and successor of the node , It's called a clue . A binary tree with clues is called a clue binary tree （Threaded BinaryTree）. The process of traversing a binary tree in some order to make it a clue binary tree is called Clue . 　　（１）** Preordered threaded binary trees 　**

　　（２） Middle order clue binary tree

　　（３） A postorder threaded binary tree

　　 See the picture below （ａ） As shown in the for Middle order clue binary tree , The corresponding middle order clue list is shown in the figure （ｂ） Shown . Where the solid line is the pointer （ Point left 、 Right subtree ）, The dotted line is the clue （ Point to precursors and successors ）. For convenience , Imitate the storage structure of linear table , In the binary tree clue linked list also added a Head node , And make it lchild The pointer of the domain points to the root of the binary tree , Its rchild The pointer of the domain points to the last node accessed during the middle order traversal ; meanwhile , Let the of the first node in an ordered sequence in a binary tree lchild Domain pointer and last node rchild Pointers to fields refer to the head node . This is like building a two-way clue linked list for a binary tree , It can be traversed from the first node , You can also traverse the precursor from the last node .

2.4.3 Traversing the threaded binary tree

　　 With the precursor and successor information of the node , Therefore, the traversal of clue binary tree and the precursor and successor algorithms of finding nodes in the specified order become simple , And no longer need to use the stack . If you need to often find the precursors and successors of nodes in the traversed linear sequence , The clue linked list is used as the storage structure .

Homework two ： Threaded binary tree and traversing threaded binary tree

Building a binary tree （ Build a binary tree by manually entering nodes ）, And do the following ：

• Middle order cue binary tree and traverse
• Preorder cues the binary tree and traverses
• Post order cue binary tree and traverse 　

The final output result requires ：

　 In order to ensure the correctness of the final clue result , Can be in a class Join the traversal of an unthreaded binary tree To verify .

Code thinking （ For reference only , Unlimited ideas ）： 　　 　　 We manually enter nodes to build a binary tree , Mainly to better test whether the cueing is successful . 　　 The generation of binary tree ： Create node class , Generate ｎ A root node , Then use the relationship of nodes to create a binary tree （ Such as ｔ The left child of ｆ,ｔ My right child is ｇ,ｇ My left child is ｈ）. 　　 　　 Class of clue binary tree ： The clue process is to modify the null pointer in the process of traversal , Such as The process of middle order cueing , That is, cue the left subtree first , 　　（１） Handle the predecessor node of the current node , If the left child node of the current node is empty , Then let the left pointer of the current node point to the predecessor node , And modify the left pointer type of the current node to １ 　　（２） Handle the successor nodes of the current node , If the precursor node exists , And the right child node of the current node is empty , Then let the right pointer of the predecessor node point to the current node , The pointer type of the modified precursor node is １ 　　 After each node is processed , Let the current node be the precursor node of the next node . 　　 Recursive cued right subtree .

　　 Traversing the threaded binary tree ：（ Take the middle order traversal as an example ） Loop to find the first left pointer of type １ The node of , Print the node , If the right pointer of the current node points to the subsequent node , Then keep outputting , If the right pointer type of the current node is １, Then get the successor node of the node , Make its subsequent nodes continue to traverse .

Code ：

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/8/18 9:03 
# @Author : vaxtiandao
# @File : Clue binary tree.py

#  Define node class , Contains two members ： Node element value and pointer to the next node 
class SingleNode():
    #  Node class initialization 
    def __init__(self, item):
        self.item = item  # item Store the value of the node 
        self.next = None  #  The next pointer points to 


#  Define chain stack 
class LinkStack():
    #  initialization 
    def __init__(self):
        self.top = None

    #  Determine whether it is null 
    def is_empty(self):
        if self.top == None:
            return True
        else:
            return False

    #  Back to top of stack element 
    def get_element(self):
        if self.is_empty():
            return None
        else:
            return self.top.item

    #  Returns the stack length 
    def get_length(self):
        tmp = self.top
        if tmp == None:
            return 0
        i = 0
        while tmp != None:
            tmp = tmp.next
            i += 1
        return i

    #  Into the stack 
    def add_stack(self, element):
        node = SingleNode(element)
        node.next = self.top  #  Pointer transformation 
        self.top = node

    #  Out of the stack 
    def remove_stack(self):
        if self.is_empty():
            raise IndexError(" Stack empty , Can't get out of the stack ")
        else:
            node = self.top
            self.top = self.top.next
            return node.item

    #  Empty stack 
    def clear_stack(self):
        self.top = None


class Ttree():  #  Clue binary tree class 
    def __init__(self, item):
        self.item = item
        self.l = None
        self.r = None
        self.ltag = 0
        self.rtag = 0

    def llink(self, other):
        self.l = other
        self.ltag = 0

    def rlink(self, other):
        self.r = other
        self.rtag = 0

    def __repr__(self):
        if self.l == None:
            l_item = 'NA'
        else:
            l_item = str(self.l.item)
        if self.r == None:
            r_item = 'NA'
        else:
            r_item = str(self.r.item)
        return str(self.item) + ' id:' + str(id(self)) + ' ltag:' + str(self.ltag) + ' l:' + l_item + \
               ' rtag:' + str(self.rtag) + ' r:' + r_item

    def get_depth(self):
        if self.ltag == 1 or self.l == None:
            l_depth = 0
        else:
            l_depth = self.l.get_depth()
        if self.rtag == 1 or self.r == None:
            r_depth = 0
        else:
            r_depth = self.r.get_depth()
        return max(l_depth, r_depth) + 1

    def get_len(self):
        if self.ltag == 1 or self.l == None:
            l_len = 0
        else:
            l_len = self.l.get_len()
        if self.rtag == 1 or self.r == None:
            r_len = 0
        else:
            r_len = self.r.get_len()
        return l_len + r_len + 1

    def show_first(self):
        print(self.item, end=' ')
        if self.l != None and self.ltag != 1:
            self.l.show_first()
        if self.r != None and self.rtag != 1:
            self.r.show_first()

    def show_mid(self):
        if self.l != None and self.ltag != 1:
            self.l.show_mid()
        print(self.item, end=' ')
        if self.r != None and self.rtag != 1:
            self.r.show_mid()

    def show_last(self):
        if self.l != None and self.ltag != 1:
            self.l.show_last()
        if self.r != None and self.rtag != 1:
            self.r.show_last()
        print(self.item, end=' ')


def create(x):
    try:
        tmp = next(x)
        if tmp == '#':
            return
        root = Ttree(tmp)
        root.llink(create(x))
        root.rlink(create(x))
        return root
    except:
        pass


def thread_first(tree):  #  Preorder cueing 
    pre = None  #  Previous node 
    tmp = tree  #  Current node 

    def thread(a):  #  Define recursive preorder access functions 
        if a.l != None and a.ltag != 1:  #  If the left node exists , Access the root node of the left tree 
            nonlocal pre
            nonlocal tmp
            pre = tmp
            tmp = a.l

            if tmp.l == None or tmp.ltag == 1:  #  If the left node of the current node does not exist , It refers to the forward node , And will tag Marked as 1
                tmp.l = pre
                tmp.ltag = 1
            if pre.r == None or pre.rtag == 1:  #  If the front node and the right node do not exist , Points to the current node , And will tag Marked as 1
                pre.r = tmp
                pre.rtag = 1
            thread(tmp)  #  Recursive cued subtree 
        if a.r != None and a.rtag != 1:  #  The right node is similar to 
            pre = tmp
            tmp = a.r
            if tmp.l == None or tmp.ltag == 1:
                tmp.l = pre
                tmp.ltag = 1
            if pre.r == None or pre.rtag == 1:
                pre.r = tmp
                pre.rtag = 1
            thread(tmp)

    thread(tree)


def thread_mid(tree):  #  Middle order cueing 
    pre = None
    tmp = None

    def thread(a):
        nonlocal pre
        nonlocal tmp
        if a.l != None and a.ltag != 1:
            thread(a.l)
        pre = tmp
        tmp = a
        if tmp != None:
            if tmp.l == None or tmp.ltag == 1:
                tmp.l = pre
                tmp.ltag = 1
        if pre != None:
            if pre.r == None or pre.rtag == 1:
                pre.r = tmp
                pre.rtag = 1
        if tmp.r != None and tmp.rtag != 1:
            thread(tmp.r)

    thread(tree)


def thread_last(tree):  #  Post order cueing 
    pre = None
    tmp = None

    def thread(a):
        nonlocal pre
        nonlocal tmp
        if a.l != None and a.ltag != 1:
            thread(a.l)
        if a.r != None and a.rtag != 1:
            thread(a.r)
        pre = tmp
        tmp = a
        if tmp != None:
            if tmp.l == None or tmp.ltag == 1:
                tmp.l = pre
                tmp.ltag = 1
        if pre != None:
            if pre.r == None or pre.rtag == 1:
                pre.r = tmp
                pre.rtag = 1

    thread(tree)


tree_list = ['A', 'B', 'C', '#', '#', 'D', 'E', '#', 'G', '#', '#', 'F', '#', '#', '#']


def travel_first(tree, action):  #  The first sequence traversal 
    tmp = tree
    while tmp != None:
        while tmp.l != None and tmp.ltag != 1:
            action(tmp)
            tmp = tmp.l
        action(tmp)
        tmp = tmp.r


def travel_mid(tree, action):  #  In the sequence traversal 
    def lfirst(node):
        tmp = node
        while tmp.l != None and tmp.ltag != 1:
            tmp = tmp.l
        return tmp

    def next(node):
        if node.rtag == 0 and node.r != None:
            return lfirst(node.r)
        else:
            return node.r

    tmp = lfirst(tree)
    while tmp != None:
        action(tmp)
        tmp = next(tmp)


def travel_last(tree, action):  #  After the sequence traversal 
    tmp = tree
    stack = LinkStack()
    while tmp != None:
        while tmp.r != None and tmp.rtag != 1:
            stack.add_stack(tmp)
            tmp = tmp.r
        stack.add_stack(tmp)
        tmp = tmp.l
    while not stack.is_empty():
        action(stack.remove_stack())


root = create(iter(tree_list))
thread_first(root)

print(root.show_first())

print(travel_first(root, print))

root = create(iter(tree_list))
thread_mid(root)
print(root.show_mid())

print(travel_mid(root, print))

root = create(iter(tree_list))
thread_last(root)
print(root.show_last())

print(travel_last(root, print))

 Copy code 

Realization effect ：

3、 Trees and forests

3.1 The storage structure of the tree

3.1.1 Parenting

　　 In this representation , The nodes of the tree are stored in a continuous set of storage units , Every node except Data fields data Outside , There is also a parent Domain Used to indicate the location of its parent node , The node form is shown in the left figure . The right figure shows the storage structure of a tree and its parents .

　　 This storage structure makes use of each node （ Besides the root ） The nature of having only one parent . In this storage structure , It is very convenient to find the parents of the node , It's also easy to find the root of the tree , But when seeking the child of the node, you need to traverse the whole structure .

3.1.2 Child representation

　　 The child representation stores common trees using " The order sheet + Linked list " The combined structure of , The stored procedure is ： Start at the root of the tree , Use the order table to store the nodes in the tree in turn , It should be noted that , Unlike parenting , The child representation gives each node a linked list , The child node used to store each node is located in the order table . If the node has no children （ leaf node ）, The linked list of this node is empty .

3.1.3 Children's brotherhood

　　 Also known as binary tree representation , Or binary list representation , That is, the binary list is used as the storage structure of the tree . The two chain fields of a node in the linked list point to the of the node respectively The first child node and the next brother node , Named as firstchild Domain and nextsibing Domain , The node form is shown in the figure below .

　　 In the tree structure , Nodes on the same layer are brothers to each other . for example , Common tree in child representation , node A、B and C Be brothers to each other , And node D、E and F They are brothers to each other . The result of storing it in the child brother representation is shown in the figure below .

3.2 The forest is converted into a binary tree

　　 From the definition of the binary list representation of the tree , Any binary tree corresponding to a tree , The right subtree of its root node must be empty . If the root node of the second tree in the forest is regarded as the brother of the root node of the first tree , Then the corresponding relationship between forest and binary tree can also be derived . This one-to-one correspondence shows that forests or trees and binary trees can be transformed into each other .

　　 Tree to binary tree The step is ： 　　（１） Take the root node of the tree directly as the root node of the binary tree 　　（２） Take the first child node of the root node of the tree as the left son of the root node , If the child node has siblings , The first sibling node of the child node （ Direction from left to right ） As the right son of the child node 　　（３） Set the remaining nodes in the tree as in the previous step , Add to the binary tree in order , Until all the nodes in the tree are in the binary tree

　　 The forest is converted into a binary tree The step is ： 　　（1） First, turn each tree into a binary tree ; 　　（2） The first binary tree doesn't move , Start with the second tree , Take the root node of the last binary tree as the right child node of the root node of the previous binary tree , Connect with wires . When all the binary trees are connected, the binary tree is the binary tree transformed from forest .

Homework three ： Convert trees and forests into binary trees

operation １： Ordinary tree to binary tree

　　 For ordinary trees to binary trees , Remember 6 A word formula ： Left son , Right brother ; 　　 The implementation is roughly step That's true ： 　　（1） Take the root node of the tree directly as the root node of the binary tree 　　（2） Take the first child node of the root node of the tree as the left son of the root node , If the child node has siblings , The first sibling node of the child node （ Direction from left to right ） As the right son of the child node 　　（3） Set the remaining nodes in the tree as in the previous step , Add to the binary tree in order , Until all the nodes in the tree are in the binary tree 　 Tips ： Four classes are needed here , Queue class , Ordinary tree node class , Binary tree node class , The class from ordinary tree to binary tree ;

operation １ Test cases ：（ On the left is an ordinary tree , On the right is a binary tree ） （ Case study １）

（ Running results ）

（ Case study ２）

（ Running results ）

（ Case study ３） （ Running results ）

operation ２： The forest is converted into a binary tree

　　 　　 The above task has realized the transformation of ordinary tree into binary tree , The forest is composed of many ordinary trees , Therefore, it can also be transformed into a binary tree , The transformation method is ： 　　（1） First, all ordinary trees in the forest are transformed into binary trees ; 　　（2） Take the root of the first tree in the forest as the root of the whole forest , The root node of other trees is regarded as the brother node of the root node of the first tree , Join all the trees using the child brother representation ;（ This is similar to the transformation function from ordinary tree to binary tree , There's no more explanation here , My friends think for themselves ）

operation ２ Test cases ：（ Above is the forest , The following is the binary tree to be finally implemented ） （ Case study ） （ Running results ）

【 notes 】： Partners must use the above test cases , In order to facilitate the operation, it is necessary to unify , It's a little more difficult , I believe you can , Origie ！

Code thinking （ For reference only , Unlimited ideas ）：

（1） First, according to the left figure of the case provided by the tree to binary tree , Create a normal tree , The child nodes of an ordinary tree are stored in a list （ Then ordinary tree node initialization function implementation , such as self.chidren = [node1, node2, node3]）; （2） Then define a binary tree node class and a class from ordinary tree to binary tree , Create an empty binary tree object , Take the root node of an ordinary tree as the root node of a binary tree ; （3） Next is the key conversion function , Here we use queues , First define two queues , A node that stores ordinary trees , A node that stores a binary tree , Then store the determined root nodes in , The rest is loop traversal , The traversal idea is as follows ; （4） Take out the first element in the normal tree node queue , Traverse its child nodes , Then put the child nodes in the queue , Then traverse the child nodes in turn , Until there is no node traversal ; Each time, the node is taken from the queue first , See if there are children , If there is , Then add it to the normal tree node queue , If not, do not perform the following for loop , Until all the nodes in the queue are taken out ,while The cycle stops ！ Here's to say , If there are children , According to the index position of the node , Determine whether it is the first node or the following node , Then, according to this, the binary tree nodes are generated in turn and put into the binary tree object ;（ It's not easy here , Little friends must understand the principle , Read more relevant information ）　　

Code ：

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/8/18 9:08 
# @Author : vaxtiandao
# @File : Tree2BTree.py

class Otree():  #  General tree objects 
    def __init__(self, item, child=None):
        self.item = item  #  Root node value 
        if child == None:  #  Child node 
            self.child = []
        else:
            self.child = child

    def add_child(self, *other):  #  Add child nodes 
        for i in other:
            self.child.append(i)

    def __repr__(self):
        return str(self.item) + ':' + str(self.child)


class Tree():
    def __init__(self, item):
        self.item = item
        self.l = None
        self.r = None

    def llink(self, other):  #  Left connected child node 
        self.l = other

    def rlink(self, other):  #  Right connect child nodes 
        self.r = other

    # def __repr__(self):
    # return str(self.item)+' '+str(self.l)+' '+str(self.r)
    def get_depth(self):  #  Get depth （ recursive ）
        if self.l == None:
            l_depth = 0
        else:
            l_depth = self.l.get_depth()
        if self.r == None:
            r_depth = 0
        else:
            r_depth = self.r.get_depth()
        return max(l_depth, r_depth) + 1

    def get_len(self):  #  Get the number of nodes （ recursive ）
        if self.l == None:
            l_len = 0
        else:
            l_len = self.l.get_len()
        if self.r == None:
            r_len = 0
        else:
            r_len = self.r.get_len()
        return l_len + r_len + 1

    def show_first(self):  #  The first sequence traversal （ recursive ）
        print(self.item, end=' ')
        if self.l != None:
            self.l.show_first()
        if self.r != None:
            self.r.show_first()

    def show_mid(self):  #  In the sequence traversal （ recursive ）
        if self.l != None:
            self.l.show_mid()
        print(self.item, end=' ')
        if self.r != None:
            self.r.show_mid()

    def show_last(self):  #  After the sequence traversal （ recursive ）
        if self.l != None:
            self.l.show_last()
        if self.r != None:
            self.r.show_last()
        print(self.item, end=' ')

    def copy(self):  #  Copy node 
        c_result = Tree(self.item)
        c_result.llink(self.l)
        c_result.rlink(self.r)
        return c_result

    def copy_deep(self):  #  Deep copy the entire tree below the node 
        c_result = Tree(self.item)
        if self.l != None:
            c_result.llink(self.l.copy())
        if self.r != None:
            c_result.rlink(self.r.copy())
        return c_result


def create(x):  #  Create a binary tree from the list 
    try:
        tmp = next(x)
        if tmp == '#':
            return
        root = Tree(tmp)
        root.llink(create(x))
        root.rlink(create(x))
        return root
    except:
        pass


def O2B(otree):  #  Ordinary tree to binary tree 
    if otree.child == []:  #  If there are no child nodes , Directly return a binary tree object 
        return Tree(otree.item)
    else:  #  Has child nodes , Recursively create a binary tree 
        root = Tree(otree.item)  #  Create a binary tree root node based on the current node data 
        for i in range(len(otree.child)):  #  For its child nodes 
            if i == 0:  #  The first child node is created as the left child tree 
                child_cur = O2B(otree.child[i])  #  Recursively create a binary tree 
                root.llink(child_cur)
            else:  #  Other child nodes are created as the right tree of the previous child node in turn 
                child_pre = child_cur  # pre The pointer moves back 
                child_cur = O2B(otree.child[i])  #  Create a binary tree recursively according to the next child node 
                child_pre.rlink(child_cur)  #  The newly created binary tree is used as the right tree of the previous node 
        return root


#  Create a normal tree 
B = Otree('B')
C = Otree('C')
D = Otree('D')
A = Otree('A')
A.add_child(B, C, D)
print(A)

tree = O2B(A)
print(tree.show_first())

#  Second example 
for i in list('ABCDEFGHIJKL'):
    exec('%s=Otree("%s")' % (i, i))
B.add_child('E', 'F')
D.add_child('G')
A.add_child('B', 'C', 'D')
print(A)

 Copy code 

Realization effect ：