计算机问题求解 -论题2-13 树及搜索树 2020年05月21日
计算机问题求解 – 论题2-13 - 树及搜索树 2020年05月21日
如何定义这样一个“树”数据结构？ University Faculty of Faculty of Faculty of Science Engineering Social Studies Department Department Department Department Department of Computer of Physics of Chemistry of Electronic of Civil Science Engineering Engineering 动态集合中元素、元素之间的关系 这种集合上的基本操作及特殊操作
如何定义这样一个“树”数据结构？ 动态集合中元素、元素之间的关系 这种集合上的基本操作及特殊操作
树中元素及元素之间的关系 A tree is a recursive abstract data type which is a collection of zero or more nodes each containing an element of type elemtype with the following hierarchi- cal structure: either (a)The empty structure(with no nodes) or (b)A node N containing element E with a finite number (zero or more)of associated disjoint tree structures (that is,they have no common nodes).These trees are known as subtrees of N.N is called the root of the tree. 你如何理解这两个概念：层次结构、递归ADT?
树中元素及元素之间的关系 你如何理解这两个概念：层次结构、递归ADT？
树中元素上应该有哪些操作？基本操作B)？特 殊操作(S)? B B S B S
树中元素上应该有哪些操作？基本操作(B)？特 殊操作(S)？ B B B S S
function left_most_child (N node):node; (This function returns the left-most child of the node N. S If there are no children,a null node will be returned * function right_sibling (N:node):node; (If node N has a sibling node,it will be retured as the value of this S function.Otherwise,a null node will be returned * function null_node (N:node):boolean; (This function returns a true value if and only if N is a null node * B/S function cons_treen (E:elemtype;T1,T2,...,Tn:tree):tree; (This function constructs a tree with a node N as its root containing element E and the trees T1,T2,...,Tn as its children,in that order. B/S The trees T1,T2,...,Tn should not be used again after this operation to construct other trees.If copies of these subtrees are required,they can be constructed using the assign(T,T)operation.This is meant for space-efficiency so that this function need not copy these subtrees in order to make a new tree *
S S B/S B/S