数据结构(本)课程辅导与练习-第6章（Data structure (the) course guidance and practice - Chapter Sixth）.docVIP

数据结构(本)课程辅导与练习-第6章（Data structure (the) course guidance and practice - Chapter Sixth） Programming skills! Data structure (course) tutorial and exercise - Chapter Sixth Sixth chapter tree and two branch tree Tree is an important nonlinear structure. From a logical point of view, the relationship between data elements is one to many, and all the problems with hierarchical relations can be described by trees. I. related terms Two trees, tree roots, tree, tree, orderly and disorderly, the number of forest, terminal nodes (leaves), non terminal nodes, node degree, node level, the depth of the tree, with two tree, two tree, two fork tree, ideal children, parents, children left and right children and the first traversal, in order traversal, postorder traversal and level traversal, Huffman tree, optimal two tree, path, path length, weight, weighted path length, Huffman encoding. Two, the concept of trees Tree definition Recursive definition of trees: The tree is n (Tree) (n = 0) a finite set of T nodes, T is empty, called the empty tree, otherwise it satisfies the following two conditions: (1) there is only one particular node called the root (Root); (2) the rest of the nodes can be divided into m (M = 0) disjoint subsets of Tl, T2, Tm,..., in which each subset is itself a tree, and called for the root of the subtree (Subree). Be careful： The recursive definition tree depicts the inherent characteristics of the tree: a non empty tree is composed of a plurality of seed tree, and can be composed of several sub sub tree smaller. Three, two fork tree definition Two fork tree is an important type of tree structure. Abstract data structure out of many practical problems are often the two fork tree form, even if the common trees can be simply converted to two binary tree storage structure and algorithm, and the two fork tree are relatively simple, so the two tree is particularly important. (1) two fork tree is different from unordered tree In the two branch tree, each node can hav