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 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.
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.
1. There are at most 2i-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 2k-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.
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 = 2k-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 .
< 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.