資料结構(5)

第五章 Trees

5.1 Binary Trees

A binary tree is a finite set of elements that is either empty or partitioned into three disjoint subsets. The first subset contains a single element called the root of the tree. The order two subsets are themselves binary tree, called the left and right subtrees of the original tree. A left or right subtree can be empty. Each element of binary tree is called a node of the tree.

If A is the root of a binary tree and B is the root of its left or right subtree, then A is said to be the father of B and B is said to be the left or right son of A.

The direction from the root to be the leaves is “down” and the oppsite is “up”.

If every non-leaf node in a binary tree has noneempty left or right subtrees, the tree is termed a strictly binary tree.

The level of a node in a binary tree is defined as follows:the root of the tree has level 0, and the level of any other node in the tree is more than the level of its father.

The depth of a binary of tree of depth d is the strictly binary tree all of whose leaves are at level d.

A binary tree of depth d is an almost complete binary tree if

1. Any node nd at level less than d-1 has two sons.
2. For any node nd in the tree with a right descendant at level d, nd must have a left son and every left descendant of nd is either at level d or has two sons.

The nodes of an almost complete binary tre can be numbered so that the root is assigned its father, and a right son is assigned one more than twice the number assigned its father.（root:0 left:1 right:2)

An almost complete strictly binary tree with n leaves has 2n-1 nodes, as closes any other strictly binary tree with n leaves.

There is only a single almost complete binary tree with n nodes. This tree is strictly binary if and only if n is odd.

An almost complete binary tree of depth d is intermediate between the complete binary tree tree of depth d-1, that contains 2^d-1 nodes, and the complete binary tree of depth d, which contains 2^(d+1)-1 nodes.

left(p) return pointers to the left son of nd

right(p) return pointers to the right son of nd

father(p) return pointers to the father

brother(p) return pointers to the brother.

The logical functions is left(p) and is right(p) return the value true if nd is left or right son.

//isleft

q=father(p);

if(q==null)

{

return false;

}

if(left(q) == p)

return true;

return false

brother(p)

if(father(p)==null)

return null;

if(isleft(p)

return right(father(p));

return left(father(p));

To traverse a nonempty binary tree in preorder(also know as depth-first order), we perform the following three operations:

1. Visit the root
2. Traverse the left subtree in preorder.
3. Traverse the right subtree in preorder.
   To traverse a nonempty binary tree in inorder(or symmetric order)

中左右 preorder

左中右 inorder

左右中 postordr

A binary tree that has this property is called a binary search tree. If a binary search tree is traversed inorder and the contents of each node are printed as the root is visited, the numbers are printed in ascending order.(小->大)