 # 二叉树的性质

• 在二叉树的第i层，至多有2^(i-1)个结点
• 深度为k的二叉树至多有：(2^k)-1个结点，其实这个结果就是一个等比数列的求和得到的。
• 对任意一颗二叉树，如果其叶子结点数量为：n0,度为2的结点数为：n2，则：n0=n2+1

# 二叉树的数据结构

C++实现二叉树时，有很多数据结构，具体采用哪种数据结构，需要根据问题具体选择。

• 数组存储：此种存储方式一般是按照前序后序或中序输入，求出另一种遍历的输出
• 链表存储，链表存储一般采用struct结构，具体如下，l, r分别是当前节点左孩子和右孩子的id值

# 实例

## PAT 1115 Counting Nodes in a BST (30 分)

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

• The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Insert a sequence of numbers into an initially empty binary search tree. Then you are supposed to count the total number of nodes in the lowest 2 levels of the resulting tree.

### Input Specification

Each input file contains one test case. For each case, the first line gives a positive integer  () which is the size of the input sequence. Then given in the next line are the  integers in  which are supposed to be inserted into an initially empty binary search tree.

### Output Specification

For each case, print in one line the numbers of nodes in the lowest 2 levels of the resulting tree in the format:

where n1 is the number of nodes in the lowest level, n2 is that of the level above, and n is the sum.

## PAT 1135 Is It A Red-Black Tree

There is a kind of balanced binary search tree named red-black tree in the data structure. It has the following 5 properties:

• (1) Every node is either red or black.
• (2) The root is black.
• (3) Every leaf (NULL) is black.
• (4) If a node is red, then both its children are black.
• (5) For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

For example, the tree in Figure 1 is a red-black tree, while the ones in Figure 2 and 3 are not. For each given binary search tree, you are supposed to tell if it is a legal red-black tree.

### Input Specification

Each input file contains several test cases. The first line gives a positive integer K (30) which is the total number of cases. For each case, the first line gives a positive integer N (30), the total number of nodes in the binary tree. The second line gives the preorder traversal sequence of the tree. While all the keys in a tree are positive integers, we use negative signs to represent red nodes. All the numbers in a line are separated by a space. The sample input cases correspond to the trees shown in Figure 1, 2 and 3.

### Output Specification

For each test case, print in a line “Yes” if the given tree is a red-black tree, or “No” if not.

## PAT 1110 Complete Binary Tree (25 分)

Given a tree, you are supposed to tell if it is a complete binary tree.

### Input Specification

Each input file contains one test case. For each case, the first line gives a positive integer  () which is the total number of nodes in the tree — and hence the nodes are numbered from 0 to . Then  lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a - will be put at the position. Any pair of children are separated by a space.

### Output Specification

For each case, print in one line YES and the index of the last node if the tree is a complete binary tree, or NO and the index of the root if not. There must be exactly one space separating the word and the number.

## PAT 1102 Invert a Binary Tree (25 分)

The following is from Max Howell @twitter:

Now it’s your turn to prove that YOU CAN invert a binary tree!

### Input Specification

Each input file contains one test case. For each case, the first line gives a positive integer  () which is the total number of nodes in the tree — and hence the nodes are numbered from 0 to . Then  lines follow, each corresponds to a node from 0 to , and gives the indices of the left and right children of the node. If the child does not exist, a - will be put at the position. Any pair of children are separated by a space.

### Output Specification

For each test case, print in the first line the level-order, and then in the second line the in-order traversal sequences of the inverted tree. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.

## PAT 1099 Build A Binary Search Tree (30 分)

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
• Both the left and right subtrees must also be binary search trees.

Given the structure of a binary tree and a sequence of distinct integer keys, there is only one way to fill these keys into the tree so that the resulting tree satisfies the definition of a BST. You are supposed to output the level order traversal sequence of that tree. The sample is illustrated by Figure 1 and 2. ### Input Specification

Each input file contains one test case. For each case, the first line gives a positive integer  () which is the total number of nodes in the tree. The next  lines each contains the left and the right children of a node in the format left_index right_index, provided that the nodes are numbered from 0 to , and 0 is always the root. If one child is missing, then  will represent the NULL child pointer. Finally  distinct integer keys are given in the last line.

### Output Specification

For each test case, print in one line the level order traversal sequence of that tree. All the numbers must be separated by a space, with no extra space at the end of the line.