Hard working programmers knock code in their dreams , 

The so-called people lie in bed , Natural rise of Technology ,

This issue will take you to dream programming ,

Content abstraction , Please get your pillow ready .

catalogue :

1. Concept and structure of binary tree

2. Implementation of binary tree chain structure

1. Concept and structure of binary tree  

① concept : A binary tree is a finite set of nodes , The collection is either empty , Or it is composed of a root node and two binary trees called left subtree and right subtree .

② Characteristics of binary tree :

* Each node has at most two subtrees , That is, the nonexistence degree of binary tree is greater than 2 Node of .( Degrees up to 2)
* The subtree of a binary tree can be divided into left and right , The order of its subtrees cannot be reversed .
 ③ Binary tree in reality :

  When an ordinary person sees such a tree , You might think : A good standard tree

When a programmer sees such a tree , You might think : Like a binary tree in a data structure , And it's still a binary tree

 ④ Binary tree in data structure :

notes : A binary tree can have up to two degrees  

⑤ Special binary tree : 

* Full binary tree : A binary tree , If the number of nodes in each layer reaches the maximum , Then the binary tree is 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
, Then it is a full binary tree .
* Complete binary tree : Complete binary tree is an efficient data structure , A complete binary tree is derived from a full binary tree . yes
At depth K of , have n Binary tree with two nodes , If and only if each node is connected to the depth K Number in full binary tree from 1 to n When the nodes of are one-to-one corresponding, it is called a complete binary tree .
It should be noted that full binary tree is a special kind of complete binary tree tree . 

 ⑥ Storage structure of binary tree : Binary trees can generally be stored in two structures , A sequential structure , A chain structure .

 ⑦ Properties of binary tree :

* If the specified number of layers of the root node is 1, Then the second part of a non empty binary tree i At most on the floor 2^(i-1) Nodes .
* If the specified number of layers of the root node is 1, Then the depth is h The maximum number of nodes in a binary tree is 2^h- 1.
* For any binary tree , If the degree is 0 The number of leaf nodes is n0, Degree is 2 The number of branch nodes is n2, Then there n0=n2 +1
* If the specified number of layers of the root node is 1, have n The depth of a full binary tree of nodes ,h=log₂n+1

⑧ Exercises   

 

  2. Implementation of binary tree chain structure

  ① Traversal of binary tree chain structure :

So called ergodic (Traversal) It refers to following a search route , Each node in the tree is accessed once and only once in turn . interview The operation of the query node depends on the specific application topic .
Traversal is one of the most important operations on binary trees , It is carried out on a binary tree Basis of other operations .

  Preamble / Middle order / Postorder recursive structure traversal : It is named according to the location where the access node operation occurs

* Preamble ( First root ): Access the root node first , Then access the left subtree , Finally, access the right subtree
* Middle order ( Middle root ): Access the left node first , Then access the root node , Finally, access the right subtree  
* Post order ( Posterior root ): Access the left node first , Then access the right subtree , Finally, access the root node

  Define a structure type first :
typedef char BTDataType; typedef struct BinarytreeNode { BTDataType data;
struct BinarytreeNode* left; struct BinarytreeNode* right; }BTNode;
  Preamble :
void Preamble(BTNode* p)// Preamble { if (p == NULL) { printf("NULL "); return; }
printf("%c ", p->data); Preamble(p->left); Preamble(p->right); }
  Middle order :
void Morder(BTNode* p)// Middle order { if (p == NULL) { printf("NULL "); return; }
Morder(p->left); printf("%c ", p->data); Morder(p->right); }
Post order :
void Porder(BTNode* p)// Post order { if (p == NULL) { printf("NULL "); return; }
Porder(p->left); Porder(p->right); printf("%c ", p->data); }
  Find the number of binary tree nodes :
int treeSize(BTNode* p)// Number of nodes { return p == NULL ? 0 : treeSize(p->left) +
treeSize(p->right)+1; }
Find the number of leaf nodes :
int treeLeafSize(BTNode* p)// Number of leaf nodes { if (p == NULL) { return 0; } if (p->left
== NULL&&p->right == NULL) { return 1; } return treeLeafSize(p->left) +
treeLeafSize(p->right); }

  That's all for this issue ...

Technology
©2019-2020 Toolsou All rights reserved,
C++ of string of compare usage MySQL Basics Commonly used sentence ( Add / delete / modify query )C Language of a Gobang game implementation QT5.9 Use of learning notes QSqlQuery Method of Qt Getting Started tutorial 【 Basic controls 】QCalendarWidget calendar control java Polymorphic array of web Front end signature plug-in _signature_pad Plug in implements electronic signature function centos7 install RabbitMqspringboot use redis Experiment 4 Automated test tools - software test