(transformation) tree, binary tree and forest transformation principle

Tree to binary tree

The rule that a tree becomes a binary tree ： The left pointer of each node points to its first child node . The right pointer points to its adjacent sibling nodes in the tree . 

That is to say ： Left child right brother . 

No brothers at all , So the converted tree has no right subtree .

Specific operation ：

• Connecting between brothers
• For each node , Only keep it with the first child node （ eldest son ） Connection of , All connections with other child nodes are erased .
• Take the root of the tree as the axis , Clockwise rotation 45 degree .

 

A binary tree becomes a tree

Rules for binary tree to tree ： Is the inverse process of a tree becoming a binary tree . ask ： Binary trees can be transformed into all kinds of trees , Why is this the only tree ？ It is only assumed that the binary tree is derived from the above transformation algorithm , Then the process is reversible . So for a binary tree with a right subtree , You can't turn it into a tree in this way .

• Add lines . If a node has a left child , So take this left child's right child , The right child of the right child , Go straight down to the right , All connected to this node . In this algorithm, the correspondence tree becomes a binary tree, and the connection with the node other than the eldest child is erased , Now I want to find all my sons .
• Off line . Delete the connections between all nodes in the tree and these right children . I found my son , No one is allowed to have anything to do with them .
• Level adjustment .

 

Binary tree into forest

The rules ：

• Recursive export ： If the binary tree is not empty , Then the root of the binary tree and its left subtree are taken as the binary tree form of the first tree .
• recursive ： Operate on the right subtree of a binary tree . That is, after removing a tree , Do the same for the rest of the binary tree , Until there is no right subtree .

Cut into a pile of binary trees , It's not over yet , The point is not binary tree , It's a tree , Therefore, use the above binary tree algorithm to turn the tree into a forest .

 

The forest becomes a binary tree

The rule is :

• First, turn each tree into a binary tree
• The root of the first tree is the root of the transformed binary tree
• The left subtree of the first tree is the left subtree of the root of the transformed binary tree
• The second tree is the right subtree of the binary tree
• The third tree is the right subtree of the right subtree of the binary tree
• …

The main points used here are ： After converting to binary tree , This binary tree has no right subtree , So free your right hand to pick up a new tree , Therefore, it can connect many binary trees transformed from trees .

Compare this algorithm to the binary tree to forest , It's easy to understand , First cut down the root and its left subtree as a whole , Do the same for the rest of the section .