当前位置:网站首页>Binary tree of data structure

Binary tree of data structure

2020-11-10 14:46:10 Java Encyclopedia

1 Key concepts

1.1 Node concept

A binary tree is a finite set of nodes , The set is either empty , Or a root node plus two left and right subtrees
Node is the basis of data structure , It is the basic unit of complex data structure .

1.2 Tree node declaration

The nodes mentioned in this series refer to the nodes of trees . for example : node A It is shown in the figure as :

ThirdPartyImage_fa646357.png

2 Trees

2.1 Definition

Trees (Tree) yes n(n>=0) A finite set of nodes .n=0 Time is called empty tree . In any non empty tree :
1) There is and only one specific one called a root (Root) The node of ;
2) When n>1 when , The rest of the nodes can be divided into m(m>0) A finite set that doesn't intersect each other T1、T2、......、Tn, Each of these sets is itself a tree , And called the root of the subtree .

Besides , The definition of tree also needs to emphasize the following two points :
1)n>0 When the root node is unique , It is impossible to have multiple root nodes , A tree in a data structure can only have one root node .
2)m>0 when , There is no limit to the number of subtrees , But they must be disjoint .
Sample tree :
chart 2.1 For an ordinary tree :

ThirdPartyImage_6574a4f7.png

chart 2.1 Common tree

From the definition of tree, we can see that , The tree is defined recursively . Recursion plays an important role in tree learning , If you don't know much about recursion , It's suggested to have a look at [ A recursive algorithm ][Link 4]

2.2 The degree of node

The number of subtrees owned by a node is called the degree of the node .
chart 2.2 The figure is marked in 2.1 The degree of each node of the tree shown .

ThirdPartyImage_215a19ae.png

chart 2.2 Degree diagram

2.3 Node relations

The root node of the node subtree is the child node of the node . The corresponding node is called the parent node of the child node .
chart 2.2 in ,A by B The parent node of ,B by A The child node of .
The child nodes of the same parent node are called brother nodes .
chart 2.2 in , node B And nodes C They are brothers and nodes of each other .

2.4 Node level

Starting from the root , The root is the first layer , The child of root is the second layer , And so on .
chart 2.3 It shows the picture 2.1 The hierarchical relationship of the tree shown

ThirdPartyImage_64d54420.png

chart 2.3 Layer diagram

2.5 Depth of tree

The maximum number of layers of nodes in a tree is called the depth or height of the tree . chart 2.1 The depth of the tree shown is 4.

3 Binary tree

3.1 Definition

The binary tree is n(n>=0) A finite set of nodes , The set is either empty ( It's called an empty binary tree ), Or by a root node and two mutually disjoint 、 They are called the left subtree and the right subtree of the root node .
chart 3.1 It shows an ordinary binary tree :

ThirdPartyImage_bcad5b11.png

chart 3.1 Binary tree

3.2 Binary tree features

From the definition of binary tree and graphic analysis, it is concluded that binary tree has the following characteristics :
1) Each node has at most two subtrees , So the nonexistence of binary tree is greater than 2 The node of .
2) The left and right subtrees are ordered , The order cannot be arbitrarily reversed .
3) Even if there is only one subtree at a certain node in the tree , We also need to distinguish whether it is a left or right subtree .

3.3 Binary tree properties

1) On the second of the binary tree i There is a maximum of 2i-1 Nodes .(i>=1)
2) In a binary tree, if the depth is k, So at most 2k-1 Nodes .(k>=1)
3)n0=n2+1 n0 The degree is 0 Of nodes ,n2 The degree is 2 Of nodes .
4) In a complete binary tree , have n The depth of a complete binary tree of nodes is [log2n]+1, among [log2n] It's rounding down .
5) If to contain n A complete binary tree of nodes proceeds from top to bottom and from left to right 1 to n The number of , Then, for any one of the complete binary trees, the number is i The node has the following characteristics :

(1) if i=1, Then the node is the root of the binary tree , Unmarried parents , otherwise , The number is [i/2] The node of is its parent node ;
(2) if 2i>n, Then the node has no left child , otherwise , The number is 2i The node of is its left child node ;
(3) if 2i+1>n, Then the node has no right child node , otherwise , The number is 2i+1 The node of is its right child node .

3.4 Oblique tree

Oblique tree : All nodes have only the binary tree of the left subtree called the left oblique tree . All nodes are binary trees with only right subtrees called right skew trees . Both of them are collectively referred to as inclined trees .

ThirdPartyImage_962be54f.png

chart 3.2 Left oblique tree

ThirdPartyImage_47947998.png

chart 3.3 Right slant tree

3.5 Full binary tree

Full binary tree : In a binary tree . If all branch nodes have left and right subtrees , And all the leaves are on the same layer , Such a binary tree is called a full binary tree .
Full binary trees are characterized by :
1) Leaves can only appear on the bottom layer . It's impossible to strike a balance in other layers .
2) The degree of a non leaf node must be 2.
3) In a binary tree of the same depth , The full binary tree has the most nodes , Most leaves .

ThirdPartyImage_0df2a0a9.png

chart 3.4 Full binary tree

3.6 Perfect binary tree

Perfect binary tree : For one with n The binary tree of nodes is numbered by layer , If the number is i(1<=i<=n) The node of the tree and the full binary tree of the same depth are numbered i The nodes of are exactly the same in the binary tree , This binary tree is called a complete binary tree .
chart 3.5 Show a complete binary tree

ThirdPartyImage_d251633f.png

chart 3.5 Perfect binary tree

characteristic :
1) Leaf nodes can only appear in the lowest and second lower layers .
2) The lowest leaf nodes are concentrated on the left side of the tree .
3) If there are leaf nodes in the penultimate layer , It must be in the right consecutive position .
4) If the node degree is 1, Then this node has only the left child , There is no right subtree .
5) A binary tree with the same number of nodes , The depth of a complete binary tree is the smallest .
notes : A full binary tree must be a complete binary tree , But it doesn't have to be the other way around .

3.7 Binary tree storage structure

3.7.1 Sequential storage

The sequential storage structure of binary tree is to use one-dimensional array to store nodes in binary tree , And the storage location of the node , It's the subscript index of the array .

ThirdPartyImage_b049c1c9.png

chart 3.6

chart 3.6 A complete binary tree shown here is stored in order , Pictured 3.7 Express :

ThirdPartyImage_b464bbf9.png

chart 3.7 Sequential storage

From the figure 3.7 It can be seen that , When a binary tree is a complete binary tree , The number of nodes just fills the array .
So when a binary tree is not a complete binary tree , How about sequential storage ? for example : For Graphs 3.8 Description of the binary tree :

ThirdPartyImage_f15ccb85.png

chart 3.8.png

The light colored node indicates that the node does not exist . Then the figure 3.8 The sequential storage structure of the binary tree shown in Fig 3.9 Shown :

ThirdPartyImage_a1872fd9.png

chart 3.9

among ,∧ Indicates that there is no storage node at this position in the array . Now you can see , There has been a waste of space in the sequential storage structure .
So for graphs 3.3 The sequence storage structure corresponding to the extreme case of the right slanted tree is shown in the figure 3.10 Shown :

ThirdPartyImage_ec864751.png

chart 3.10

From the figure 3.10 It can be seen that , For this extreme case of right slanted trees , Using sequential storage is a waste of space . therefore , Sequential storage is generally applicable to complete binary trees .

3.7.2 Binary list

Since sequential storage can not meet the storage requirements of binary tree , So consider chain storage . From the definition of binary tree, we can see that , Each node of a binary tree has at most two children . therefore , The node data structure can be defined as one data and two pointer fields . The representation is shown in the figure 3.11 Shown :

ThirdPartyImage_5367bc9a.png

chart 3.11

Define node code :

typedef struct BiTNode{
    TElemType data;// data  struct BiTNode *lchild, *rchild;// Left and right child pointer  } BiTNode, *BiTree;

Plan 3.6 The binary tree shown here can use graph 3.12 Express .

ThirdPartyImage_62821f53.png

chart 3.12

chart 3.12 A linked list structure is used to store the binary tree , This list is called a binary list .

3.8 Binary tree traversal

The traversal of binary tree is a key knowledge point .

3.8.1 Definition

The traversal of binary tree means starting from the root node of binary tree , Access all nodes in the binary tree in a certain order , Make each node be visited once , And only visited once .
The access order of binary tree can be divided into four kinds :

The former sequence traversal
In the sequence traversal
After the sequence traversal
Sequence traversal

3.8.2 The former sequence traversal

Generally speaking, preorder traversal starts from the root node of a binary tree , The node data is output when it reaches the node for the first time , Go left first and then right .

ThirdPartyImage_b03b5ebf.png

3.13

chart 3.13 The binary tree access shown is as follows :

Starting from the root node , Then it reaches the node for the first time A, Therefore, the output A;
Continue to visit left , The first time you visit a node B, Therefore, the output B;
According to the same rules , Output D, Output H;
When we reach the leaf node H, Back to D, This is the second time we have arrived D, So it's not output D, And then to D Right subtree access ,D The right subtree is not empty , Then visit I, Arrive for the first time I, The output I;
I For leaf nodes , Then go back to D,D The left and right subtrees have been visited , Then go back to B, And then to B Right subtree , Arrive for the first time E, Therefore, the output E;
towards E The left subtree , Therefore, the output J;
According to the same access rules , Continue to output C、F、G;

be 3.13 The output of the preorder traversal of the binary tree shown is :
ABDHIEJCFG

3.8.3 In the sequence traversal

The middle order traversal starts from the root node of the binary tree , When it reaches the node for the second time, it outputs the node data , Go left first and then right .

chart 3.13 The binary tree is shown as follows :

Starting from the root node , Then it reaches the node for the first time A, No output A, Continue to visit left , The first time you visit a node B, No output B; Continue to arrive D,H;
arrive H,H The left subtree is empty , Then go back to H, At this point, the second visit H, Therefore, the output H;
H The right subtree is empty , Go back to D, At this point, the second arrival D, Therefore, the output D;
from D Go back to B, A second arrival B, Therefore, the output B;
Follow the same rules to continue to visit , Output J、E、A、F、C、G;

be 3.13 The output of the middle order traversal of the binary tree is :
HDIBJEAFCG

3.8.4 After the sequence traversal

The post order traversal starts from the root node of the binary tree , When it reaches the node for the third time, it outputs the node data , Go left first and then right .

chart 3.13 The binary tree is shown as follows :

Starting from the root node , Then it reaches the node for the first time A, No output A, Continue to visit left , The first time you visit a node B, No output B; Continue to arrive D,H;
arrive H,H The left subtree is empty , Then go back to H, At this point, the second visit H, No output H;
H The right subtree is empty , Go back to H, This is the third time we arrive H, Therefore, the output H;
from H Go back to D, A second arrival D, No output D;
Continue to visit I,I Left and right subtrees are empty , So the third visit I when , Output I;
Go back to D, This is the third time we arrive D, Therefore, the output D;
Follow the same rules to continue to visit , Output J、E、B、F、G、C,A;

Plan 3.13 The output of the post order traversal of the binary tree shown is :
HIDJEBFGCA
Although the traversal process of binary tree seems tedious , But because a binary tree is a recursively defined structure , So the code of traversing the binary tree recursively is very simple .

3.8.5 Level traversal

Hierarchical traversal is to traverse the binary tree from top to bottom according to the tree hierarchy . For Graphs 3.13 The hierarchical traversal result of the binary tree shown is :
ABCDEFGHIJ

3.8.6 Go through the usual exam sites

There is a typical question type for traversing a binary tree .
1) We know the preorder traversal sequence and the middle order traversal sequence , Identify a binary tree .
Example : If the preorder traversal of a binary tree is ABCDEF, The middle order traversal is CBAEDF, Please draw the binary tree .
analysis : The first output node of preorder traversal is the root node , so A Is the root node . In the early middle order traversal, the root node is in the middle of the left and right subtree nodes , So the node A In the left subtree of, there are CB, The nodes in the right subtree have EDF.
Pictured 3.14 Shown :

ThirdPartyImage_848922a9.png

chart 3.14

In the same way , Yes A To divide the left and right subtrees of , Finally, the shape of binary tree is shown in the figure 3.15 Shown :

ThirdPartyImage_992decf4.png

chart 3.15.png

2) We know the sequence of post order traversal and the sequence of middle order traversal , Identify a binary tree .
In the post order traversal, the last visited node is the root node , So you can do the same thing , After finding the root node, it is divided into two subtrees , Then continue to find the root node of the subtree , Step by step, determine the shape of the binary tree .
notes : We know preorder traversal sequence and postorder ergodic sequence , You can't uniquely identify a binary tree .

4 summary

Through the above introduction , We have a preliminary understanding of binary trees . This article introduces the basic knowledge, hope readers can firmly grasp , And be able to model a binary tree in your mind , Lay a good foundation for the follow-up study .

Official account :java Treasure
a

版权声明
本文为[Java Encyclopedia]所创,转载请带上原文链接,感谢