- 2022-03-24 13:50
*views 2*- algorithm
- data structure
- Blue Bridge Cup

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

- Java240 blogs
- Python239 blogs
- Vue112 blogs
- algorithm94 blogs
- c language90 blogs
- Flow Chart81 blogs
- MySQL71 blogs
- C++64 blogs
- more...

Daily Recommendation

© ioDraw All rights reserved

√ JavaSE - 24. How to transfer objects （ volume 2 P70）python Fun code - Fun games C language --- Simple Gobang games 【 data structure 】 Binary tree -- Heap sort number IC Hand tear code （ seven ）QFontPython—— Function design （ Narcissistic number + Fibonacci sequence ） computer network network layer RIP Working principle of protocol routing and switching 2022 Salary increase strategy (3400+ word , about 10 Read in minutes ）C Language implementation ：9400 The word takes you to play three pieces of chess