Trees
A tree is not the kind of tree we usually see growing in the soil, but rather a structure in computer languages.
A tree is a simple non-linear structure
- Parent node
- In a tree structure, every node has only one predecessor, which is called that node’s parent node; there is exactly one node with no predecessor, and it is called the root node of the tree, or simply the root of the tree
- Child nodes and leaf nodes
- In a tree structure, every node can have multiple successors, which are called that node’s child nodes. A node with no successors is called a leaf node
- Degree
- In a tree structure, the number of successors that each node has is called that node’s degree, and the largest degree among all nodes is called the degree of the tree
- Depth
- The level where the root node of a tree sits is defined as 1, and the level of any other node equals the level of its parent node plus 1. The maximum level in the tree is called the depth of the tree
- Subtree
- In a tree, the tree formed with one of a node’s child nodes as its root is called a subtree of that node
- Parent node
In a tree, the number of nodes in the tree equals the sum of the degrees of all nodes in the tree plus 1
Binary Tree
Characteristics
- A binary tree can be empty; an empty binary tree has no nodes, and a non-empty binary tree has exactly one root node
- Each node has at most two subtrees, that is, there is no node with a degree greater than 2 in a binary tree
- The subtrees of a binary tree are distinguished as left and right, and their order cannot be arbitrarily reversed
Properties
- On the k-th level of a binary tree there are at most $ 2 ^{k-1}(k \geq 1)$ nodes
- In a binary tree with depth m there are at most $ 2 ^{m}-1$ nodes
- For any binary tree, the number of nodes with degree 0 (that is, leaf nodes) is always one more than the number of nodes with degree 2
- A binary tree with n nodes has a depth of at least $[log{2}n]+1$, where $[log{2}n]$ means taking the integer part of $log_{2}n$
- A complete binary tree with n nodes has a depth of $[log_{2}n]+1$
Full binary trees and complete binary trees
- Full binary tree
- A full binary tree is a binary tree in which every node on every level except the last one has two child nodes
- Complete binary tree
- A complete binary tree is a binary tree in which the number of nodes on every level except the last one reaches the maximum, and on the last level only a number of nodes on the right are missing
- Full binary tree
- A full binary tree is always a complete binary tree, while a complete binary tree is generally not a full binary tree
- Characteristics of a complete binary tree
- Leaf nodes can only appear on the last two levels
- For any node, if the depth of its right subtree is m, then the depth of that node’s left subtree is m or m+1
- A binary tree uses a linked storage structure. The storage node used to hold an element in a binary tree consists of two parts: a data field and a pointer field
- In the storage structure of a binary tree, every storage node has two pointer fields, so the linked storage structure of a binary tree is also called a binary linked list. Full binary trees and complete binary trees can be stored sequentially by level
Traversing a Binary Tree
Pre-order traversal
- Visit the root node first, then traverse the left subtree, and finally traverse the right subtree; and when traversing the left subtree and the right subtree, you still visit the root node first, then traverse the left subtree, and finally traverse the right subtree
In-order traversal
- Traverse the left subtree first, then visit the root node, and finally traverse the right subtree. And when traversing the left subtree and the right subtree, you still traverse the left subtree first, then visit the root node, and finally traverse the right subtree
Post-order traversal
- Traverse the left subtree first, then traverse the right subtree, and finally visit the root node; and when traversing the left subtree and the right subtree, you still traverse the left subtree first, then traverse the right subtree, and finally visit the root node
- If the pre-order traversal sequence and the in-order traversal sequence of a binary tree are known, the binary tree can be uniquely determined; if the post-order traversal sequence and the in-order traversal sequence of a binary tree are known, the binary tree can also be uniquely determined. However, if only the pre-order traversal sequence and the post-order traversal sequence of a binary tree are known, the binary tree cannot be uniquely determined
