Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Faculty of Computer Science and Engineering Department of Computer Science LAB SESSION 3 RECURSION on BINARY TREE 1. OBJECTIVE The objectives of Lab 3 are (1) to introduce an implementation of binary tree in C++ and (2) to practice recursion algorithms to manipulate a tree. 2. FILE-LEVEL SEPARATION of INTERFACE and IMPLEMENTATION Class interface and implementation In Lab 2, we have learnt about the concept of separation between the interface and the implementation of a class. In practice, the separation is implemented as the file-level, i.e. we store the interface and the implementation in different files, whose extensions are respectively. | Faculty of Computer Science and Engineering Department of Computer Science LAB SESSION 3 RECURSION on BINARY TREE 1. OBJECTIVE The objectives of Lab 3 are 1 to introduce an implementation of binary tree in C and 2 to practice recursion algorithms to manipulate a tree. 2. FILE-LEVEL SEPARATION of INTERFACE and IMPLEMENTATION Class interface and implementation In Lab 2 we have learnt about the concept of separation between the interface and the implementation of a class. In practice the separation is implemented as the file-level i.e. we store the interface and the implementation in different files whose extensions are respectively .h and .cpp. Listing 1 and Listing 2 illustrate the contents of two files so-called tree.h and tree.cpp corresponding to the interface and implementation of a binary tree. Please notice the red-colored statement include Tree.h in the file Tree.cpp. It is very important to make the Tree.cpp understand what are declared in Tree.h. Please refer to manuals of the C language if you truly want to know the real meaning of the directive include. this is the content of tree.h struct Node int data Node left right class Tree public Tree Tree protected Node root void destroy Node Listing 1 this is the content of tree.cpp include Tree.h Tree Tree root NULL 1 3 Faculty of Computer Science and Engineering Department of Computer Science _ II-------------------------------------- Tree Tree destroy root root NULL II-------------------------------------- Tree destroy Node root if root NULL destroy root- left destroy root- right delete root Listing 2 3. RECURSION in BINARY TREE Recursion is an unavoidable technique to handle many operations in a binary tree. In Listing 2 an example is given to illustrate how to use recursion to collect garbage when a tree is deleted. Basically to construct an algorithm for a tree binary we should do the following steps - Process the stop condition think the simplest case i.e. an empty tree and what we should do in this case.
