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 an ape sees such a program 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 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 / Recursive structure traversal of post order ： 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 ...
QQ:2186529582
Technology