《Discrete Mathematics II教学-华南理工》7.2 Applications of tree.pptVIP

Section 7.2 Application of Tree We will discuss three problems that can be studied using trees. How should items in a list be stored so that an item can be easily located? What series of decisions should be made to find an object with a certain property in a collection of objects of a certain type? How should a set of characters be efficiently coded by its bit strings? Introduce Binary search tree is a binary tree in which the vertices are labeled with items so that a label of a vertex is greater than the labels of all vertices in the left subtree of this vertex and is less than the labels of all vertices in the right subtrees of this vertex. Binary search trees Form a binary search tree for the words mathematics,physics,geography, zoology, meteorology, geology, psychology, and chemistry (using alphabetical order) mathematics physics geography zoology meteorology geology psychology chemistry Example A rooted tree in which each internal vertex corresponds to a decision ,with a subtree at these vertices for each possible outcome of the decision, is called a decision tree. A decision tree for locating a counterfeit coin is shown in Figure. 3(P544). Decision Trees Decision tree Decision tree Prefix: the first part of the bit string for a letter For instance, e: 0, a: 1, t: 01,then 0101: eat,tea,eaea, tt. To ensure that no bit string corresponds to more than one sequence of letters, the code of a character is never a prefix of the the code of another character. Codes with this property are called prefix codes. For instance: If e:0 , a: 10, t: 11 then 10110: ate PREFIX CODES A prefix code can be represented using a binary tree, where the characters are the labels of the leaves in the tree. The edges of the tree are labeled so that an edge leading to a left child is assigned a 0 and an edge leading to a right child is assigned a 1. The bit string used to encode a character is the sequence of labels of the edges in the unique path from the root to the