node order

At least one node has degree = 2

node order

The degree of the node ≤ 2 (the degree of the node can all be < 2)

Only the last layer has leaf nodes

There are no nodes with degree 1 (only nodes with degree 0/2)

Numbering starts from 1 in hierarchical order, node i

Only the last two layers have leaf nodes

There is at most one node with degree 1

Numbering starts from 1 in hierarchical order, node i

n≤⌊n/2⌋ is a branch node, i>⌊n/2⌋ (≥⌊n/2⌋ 1) is a leaf node

Can have higher search efficiency

n0 = n2 1

The i-th level of the binary tree has at most 2^(i-1) nodes.

A binary tree with height h has at most 2^h-1 nodes (full binary tree)

The height h of a complete binary tree with n (n>0) nodes <---->The level of the i-th node of the complete binary tree is

Number of nodes n--->n0,n1,n2 (complete binary tree)

root, left, right

left, root, right

left, right, root

Preorder - the node will be output when it is accessed for the first time.

In-order—The node will be output when it is accessed for the second time.

Postorder—the node will be output when it is accessed for the third time.

I. If the queue is not empty, the head node is dequeued.

II. Repeat I until the queue is empty

Root node Preorder traversal sequence of the left subtree Preorder traversal sequence of the right subtree

Preorder traversal sequence of the left subtree Root node Preorder traversal sequence of the right subtree

Preorder traversal sequence of the left subtree Preorder traversal sequence of the right subtree Root node

Root node Root node of the left subtree Root node of the right subtree

Indicates that lhlid points to the precursor

Indicates that lhlid points to the left child

Indicates that lhlid points to the successor

Indicates that lclid points to the right child

Transformation of inorder/preorder/postorder traversal algorithm

Use a pointer pre to record the predecessor node of the currently accessed node.

When a node is accessed, the clue information connecting the node to the predecessor node

The lower left node in the right subtree of p

The lower right node in the left subtree of p

If p has a left child, the left child is followed in order (root p left and right - root p (root left and right) right)

If p has no left child, the right child is followed in order (root p right - root p (root left and right))

And p is the left child (root (left and right of root p) right), then the parent node of p is its predecessor node

And p is the right child and its left brother is empty, then the parent node of p is its predecessor node.

And p is the right child and its left brother is not empty, then the predecessor of p is the subtree of its left brother. The last node to be traversed in order (p parent left (root left) (root p left))

If p is the root node, then p has no predecessor

And p is the right child ((left)(left and right root p)p parent), then the parent node of p is its successor

And p is the left child ((left and right root p)p parent), and the right brother is empty, then the parent node of p is its successor.

And p is the left child and its right brother is not empty, then the successor of p is the subtree of its right brother. The first node traversed in postorder ((left and right roots p) (left and right roots) p parent)

If p is the root node, then p has no precedence.

If p has a right child, the right child is followed in order (left and right roots p - left and right (left and right roots (p right)) p)

If p has no right child, then the left child is followed in order (left root p-left (left and right roots (p left)) p)

Node p is the left child of its parent node, and the right brother is empty

Node p is the left child of its parent node and has a right brother

Node p is the right child of its parent node, and the left brother is empty

Node p is the right child of its parent node and has a left brother