Two-forked tree, full binary tree, full binary tree

Definition

Tree node (node): contains a data element and several branches pointing to the subtree;

Child node: node The root of the subtree of a point is called the child of the node;

Parent node: Node B is the child of node A, then node A is the parent of node B;

Sibling node: child node of the same parent; cousin node: node on the same level;

ancestor node: all nodes on all branches from the root to the node Point

Descendant node: any node in the subtree rooted at a certain node is called the descendant of the node

Tree depth: in the tree The largest node level

The degree of the node: the number of node subtrees

The degree of the tree: the largest node degree in the tree.

Leaf node: also called terminal node, is a node with degree 0;

Branch node: node with degree other than 0 Point;

Binary tree

Binary tree is a finite set of n(n>=0) nodes, which may be an empty set (called empty binary tree), Or it is composed of a root node and two disjoint left subtrees and right subtrees called root nodes.

Features:

1. Each node has at most two subtrees, so there is no node with degree greater than 2 in the binary tree.

2. The left subtree and the right subtree are in order, and the order cannot be reversed arbitrarily.

Performance value:

1. There are at most 2^i-1 nodes on the i-th level of the binary tree. (I>=1)

2. If the depth of the binary tree is k, then there are at most 2^k-1 nodes. (k>=1)

3.n0=n2+1 n0 represents the number of nodes with a degree of 0, and n2 represents the number of nodes with a degree of 2. That is, leaf node = number of dual-branch nodes+1

full binary tree

in a binary tree. If all branch nodes have left and right subtrees, and all leaves are on the same level, such a binary tree is called a full binary tree.

Features:

1. The leaves can only appear on the bottom layer. It is impossible to achieve balance in other layers.

2. The degree of non-leaf nodes must be 2.

3. Leaf nodes of full binary tree = 2^k-1

Complete Binary Tree

One has n nodes The binary tree of is numbered according to the level. If the node numbered i(1<=i<=n) and the node numbered i in the full binary tree of the same depth are in the same position in the binary tree, then this binary tree is called a complete binary tree .

Features:

< p>1. Leaf nodes can only appear in the lowest and sub-lower layers.

2. The lowest leaf nodes are concentrated in the left part of the tree.

3. If there are leaf nodes in the penultimate layer, they must be in a continuous position on the right.

4. If the node degree is 1, then the node has only the left child, that is, there is no right subtree.

5. For a binary tree with the same number of nodes, a complete binary tree has the smallest depth.

Requirements: Create a complete binary tree and realize the four traversal outputs of front, middle, back and level (implemented in C language)