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 ,

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
Daily Recommendation