南京大学：《计算机问题求解》课程教学资源（课件讲稿）树及搜索树

计算机问题求解 -论题2-14 树及搜索树 2016年05月26日

计算机问题求解 – 论题2-14 - 树及搜索树 2016年05月26日

如何去定义表达如下结构的“树”数据结构？ 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)吗？ procedure initialise (var T:tree); B (This procedure returns an empty tree * function empty (T:tree):boolean; (If T is empty a true value is returned,otherwise a false B value is returned * function root (T:tree):node; (If T is empty,this function returns a null node.For non-empty trees T, S the root node of the tree T will be returned * function retrieve(N:node):elemtype; (This function returns the element stored in node N*) B function parent (N:node):node; (This function returns the parent node of N. S If N has no parent,a null node will be returned *

你能说清楚以下定义在树中元素上的操作哪些 是基本操作(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 returned 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 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 B/S

procedure insert_child (P:node;E:elemtype); (This procedure is defined for constructing trees in a top-down manner. B A node containing element E will be created and it will be made the right-most child of node P * procedure delete (var T:tree); B (This procedure deletes all the nodes of the tree T,and T will be made an empty tree.The tree T should not be a subtree of another tree * procedure assign(T1:tree;var T2:tree); (This procedure copies the entire tree T1 and asigns it to T2 * S/B 你能够从你的判断中得到一个一般 性的规律吗： 当你定义一个数据结构时，哪些操 作是必须的，哪些操作是特定的？

B B S/B 你能够从你的判断中得到一个一般 性的规律吗： 当你定义一个数据结构时，哪些操 作是必须的，哪些操作是特定的？

你有没有感觉到，在树这样的数据结构中，递 归如呼吸般自然？ ways.These are known as tree walkings or tree traversals.In a tree with the root N and subtrees T1,T2,...,Tn we define: pre-order traversal:visit the root node N,then visit all the nodes in T in pre-order,then visit all the nodes in T2 in pre-order, and so on until all the nodes in Tn are visited in pre-order. post-order traversal:visit the nodes of T1,T2,...,Tn in post-order (in that order);then visit the root node

你有没有感觉到，在树这样的数据结构中，递 归如呼吸般自然？

将一棵树赋值给另一棵树，原来也很简单 procedure assign(T1 tree;var T2:tree); var P,Q:tree; begin if T1 nil then T2 :ni1 else 你的第一想 begin 法是循环还 assign(T1T.left_most,P); assign(Tlf.right_sib,Q); 是递归？ new(T2); 你最终的做 T21.element :T1f.element; 法是循环还 T21.left_most :P; 是递归？ T2↑，right._sibt=Q end end;

将一棵树赋值给另一棵树，原来也很简单 你的第一想 法是循环还 是递归？ 你最终的做 法是循环还 是递归？

你能从下图的一般的树的链表实现中，设计一 个二叉树的链表实现吗？ type node inode_cell node_cel】=record element elmtype, element left_most,right_sib node end; tree÷node; left_most right_sib B ©-o·□形 777

你能从下图的一般的树的链表实现中，设计一 个二叉树的链表实现吗？

class Node { int iData; /data used as key value float fData; /other data node leftChild; /this node's left child node rightChild; /this node's right child public void displayNode() //(see Listing 8.1 for method body)