Shulou(Shulou.com)06/03 Report--

We have learned the relevant knowledge of the general tree before, so the structure of the general tree is relatively complex, is there a relatively simple tree? We used the parent-child representation in the previous general tree structure, each node has a pointer to its parents, and each node has several pointers to its child. The structure is shown in the following figure

Then there is another tree structure model-the child brother representation. Each node has a pointer to its first child, and each node has a pointer to its first right brother. The structure is shown in the following figure

The characteristics of the child sibling representation are as follows: 1, it can represent any tree structure; 2, each node contains a data member and two pointer members; 3, the child node pointer and the sibling node pointer constitute the "tree branch".

Let's take a look at the definition of a binary tree: a binary tree is a finite set of n (n > = 0) nodes, which is either empty or consists of a root node plus two disjoint binary trees called the left subtree and the right subtree. The binary tree has the following five forms

Let's take a look at two special binary trees: full binary tree (Full Binary Tree) and complete binary tree (Complete Binary Tree).

1. Full binary tree: if the degree of all branch nodes in a binary tree is 2 and the leaf nodes are on the same level, then this kind of binary tree is called full binary tree.

2. Complete binary tree: if a binary tree with height K with n nodes, each node corresponds to the node numbered 1-n in the full binary tree with height K. The binary tree is called a complete binary tree (numbered from top to bottom, left to right).

The related characteristics of the complete binary tree: a > the height of the complete binary tree is the smallest; b > the leaf node of the complete binary tree only appears in the bottom two layers: the lowest leaf node must appear on the left. the leaf node of the penultimate layer must appear on the right, and the middle node of the complete binary tree has only the left child. As shown in the following figure

Let's take a look at several properties of binary trees:

1. There are at most 2i-1 nodes in the I layer of the binary tree (I > = 1).

The first layer has at most 21-1 = 1 node.

The second layer pair has 22-1 = 2 nodes.

The third layer has at most 23-1 = 4 nodes.

.

2. The binary tree with height k has at most 2k-1 nodes (k > = 0).

If there is a layer, there are at most 1 = 21-1 = 1 node

If there are two layers, there are at most 1 = 22-1 = 3 nodes.

If there are three layers, there are at most 1 = 23-1 = 7 nodes

.

3. For any binary tree, if there are n 0 leaf nodes and n 2 non-leaf nodes with degree 2, then there is n 0 = n 2 + 1.

It is proved that if there are N1 nodes and n total nodes in the middle 1 of the binary tree, then: n = n0 + N1 + N2

Suppose that the edge between the parent node and the child node in the binary tree is e, then: e = N1 + 2n2 = n-1

So: N0 = N2 + 1

4. The height of a complete binary tree with n nodes is [log2n] + 1. ([X] represents the largest integer not greater than X).

It is proved that if the height of the complete binary tree composed of these n nodes is k, then: 2k-1-1 < n

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.