數(shù)據(jù)結(jié)構(gòu)樹的操作實(shí)驗(yàn)報(bào)告.doc

*實(shí)踐教學(xué)* 蘭州理工大學(xué)算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題 目： 二叉樹操作 專業(yè)班級(jí)： 08級(jí)計(jì)算機(jī)科學(xué)與技術(shù)（5）班 姓 名： 金文鑫 學(xué) 號(hào)： 08240511 指導(dǎo)教師： 李睿 成 績(jī)： _一、實(shí)驗(yàn)?zāi)康模豪斫舛鏄涮貏e是完全二叉樹的性質(zhì)，掌握二叉樹的存儲(chǔ)結(jié)構(gòu)（二叉鏈表）；熟練掌握二叉樹的常用操作算法（初始化、插入結(jié)點(diǎn)、刪除結(jié)點(diǎn)、遍歷等）；初步掌握二叉樹的應(yīng)用。二、實(shí)驗(yàn)內(nèi)容：要求采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，完成二叉樹的建立，前序、中序和后序遍歷的操作，求所有葉子及結(jié)點(diǎn)總數(shù)的操作等。具體要求如下：給出基于二叉鏈表的二叉樹類的定義；給出二叉樹初始化（構(gòu)造函數(shù)）的實(shí)現(xiàn)；給出二叉樹三種遍歷算法的遞歸實(shí)現(xiàn)；二叉樹先序遍歷的非遞歸算法實(shí)現(xiàn)；利用二叉樹的遍歷算法求二叉樹的結(jié)點(diǎn)數(shù)、二叉樹的葉結(jié)點(diǎn)數(shù)、二叉樹的高度；二叉樹的撤銷刪除三、實(shí)驗(yàn)步驟：1、需求分析：本演示程序用JAVA編寫，完成樹的生成，任意位置的插入、刪除，以及遍歷二叉樹中的結(jié)點(diǎn)，查找和修改樹中元素的值。 輸入的形式和輸入值的范圍：插入元素時(shí)需要輸入插入的位置和元素的值；刪除元素時(shí)輸入刪除元素的位置；遍歷時(shí)采用三種遍歷方法中的一種遍歷方法；修改操作時(shí)需要輸入的元素的值；查找操作時(shí)，需要找到要查找元素的位置。在所有輸入中，元素的值都是整數(shù)。 輸出的形式：在所有四種操作中都顯示操作是否正確以及操作后樹中的內(nèi)容。其中刪除操作后顯示刪除的元素的值，遍歷二叉樹中的元素，查找操作、修改操作后顯示修改的值。 程序所能達(dá)到的功能：完成樹的生成（通過(guò)插入操作）、插入、刪除、遍歷、查找、修改操作。 測(cè)試數(shù)據(jù)：A 樹中已有以50,25,75,12,37,43,30,33,87,93,97為關(guān)鍵字的結(jié)點(diǎn)B 插入操作中依次輸入10，20，30，40，50，60，70，80，90，100十個(gè)數(shù)C 刪除操作中輸入10刪除值為10的元素D 查找操作中輸入20，30，40，50返回這個(gè)元素在樹中的位置2概要設(shè)計(jì)：1）為了實(shí)現(xiàn)上述程序功能，需要定義樹的抽象數(shù)據(jù)類型：public int iData; public double dData;public Node leftChild;public Node rightChild; private Node root;int value; private Node getSuccessor；基本操作：Tree ()操作結(jié)果：構(gòu)造一個(gè)空的二叉樹insert ()初始條件：是否存在一個(gè)空二叉樹操作結(jié)果：往二叉樹中插入數(shù)值delete ()初始條件：存在一非空的二叉樹操作條件：將二叉樹中的元素刪除displayTree ()初始條件：存在一非空的樹操作條件：顯示非空樹中的所有元素的值getString ()初始條件：存在一非空的二叉樹操作結(jié)果：返回整個(gè)字符串的數(shù)值getChar ()初始條件：存在一非空的二叉樹操作結(jié)果：返回字符型的數(shù)值getInt ()初始條件：存在一非空的二叉樹操作結(jié)果：返回整型的數(shù)值find ()初始條件：存在一非空二叉樹操作結(jié)果：從二叉樹中查找某一元素traverse ()初始條件：存在一非空的二叉樹操作結(jié)果：對(duì)二叉樹中的元素進(jìn)行遍歷preorder ()初始條件：存在一非空的二叉樹操作結(jié)果：對(duì)二叉樹中的元素進(jìn)行先根遍歷inOrder ()初始條件：存在一非空的二叉樹操作結(jié)果：對(duì)二叉樹中的元素進(jìn)行中根遍歷postOrder ()初始條件：存在一非空的二叉樹操作結(jié)果：對(duì)二叉樹中的元素進(jìn)行后根遍歷DisplayNode ()初始條件：存在一非空的二叉樹操作結(jié)果：顯示出二叉樹中的整形數(shù)值和雙精度浮點(diǎn)型數(shù)值public static void main操作結(jié)果：調(diào)用主函數(shù)2）本程序包含14個(gè)函數(shù)：main()displayNode()postorder()delete()tree()insert()preorder()getInt()displayTree()inorder()getChar()find()traverse()getString()3詳細(xì)設(shè)計(jì)實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有的數(shù)據(jù)類型，對(duì)每個(gè)操作給出java算法。對(duì)主程序和其他模塊也都需要寫出java算法。1) 結(jié)點(diǎn)類型和指針類型public int iData; public double dData; public Node leftChild; public Node rightChild; private Node root; 2)樹的基本操作一、插入操作：public void insert(int id, double dd) Node newNode = new Node(); / make new node newNode.iData = id; / insert data newNode.dData = dd; if(root=null) / no node in root root = newNode; else / root occupied Node current = root; / start at root Node parent; while(true) / (exits internally) parent = current; if(id current.iData) / go left? current = current.leftChild; if(current = null) / if end of the line, / insert on left parent.leftChild = newNode; return; / end if go left else / or go right? current = current.rightChild; if(current = null) / if end of the line / insert on right parent.rightChild = newNode; return; / end else go right / end while / end else not root / end insert()首先判斷根節(jié)點(diǎn)是否為空，若為空，則新輸入一個(gè)根節(jié)點(diǎn)。若不為空，則進(jìn)行比較。如果插入的數(shù)據(jù)是整型，則將二叉樹里的整型數(shù)值和當(dāng)前要插入的整型數(shù)值比較，若idcurrent.iData，則將指針指向該節(jié)點(diǎn)的右孩子(current= current.rightChild)，再進(jìn)行比較。此時(shí)，如果存在右孩子，和上述比較方法一樣。如果沒(méi)有右孩子，則將要插入的數(shù)值作為剛才比較過(guò)的父母節(jié)點(diǎn)的右孩子(parent.rightChild = newNode)。然后，返回。二、刪除操作：public boolean delete(int key) / delete node with given key / (assumes non-empty list) Node current = root; Node parent = root; boolean isLeftChild = true; while(current.iData != key) / search for node parent = current; if(key current.iData) / go left? isLeftChild = true; current = current.leftChild; else / or go right? isLeftChild = false; current = current.rightChild; if(current = null) / end of the line, return false; / didnt find it / end while / found node to delete / if no children, simply delete it if(current.leftChild=null & current.rightChild=null) if(current = root) / if root, root = null; / tree is empty else if(isLeftChild) parent.leftChild = null; / disconnect else / from parent parent.rightChild = null; / if no right child, replace with left subtree else if(current.rightChild=null) if(current = root) root = current.leftChild; else if(isLeftChild) parent.leftChild = current.leftChild; else parent.rightChild = current.leftChild; / if no left child, replace with right subtree else if(current.leftChild=null) if(current = root) root = current.rightChild; else if(isLeftChild) parent.leftChild = current.rightChild; else parent.rightChild = current.rightChild; else / two children, so replace with inorder successor / get successor of node to delete (current) Node successor = getSuccessor(current); / connect parent of current to successor instead if(current = root) root = successor; else if(isLeftChild) parent.leftChild = successor; else parent.rightChild = successor; / connect successor to currents left child successor.leftChild = current.leftChild; / end else two children / (successor cannot have a left child) return true; / success / end delete()做刪除時(shí)，首先，先查找樹是否有左孩子和右孩子。如果沒(méi)有，則查找是否是存在根節(jié)點(diǎn)。如果存在根節(jié)點(diǎn)，則將根節(jié)點(diǎn)置為空。如果是左孩子，則將父母節(jié)點(diǎn)的左孩子置為空 (parent.leftChild = null)。如果是右孩子，則將右孩子置為空(parent.rightChild = null)。三、遍歷操作public void traverse(int traverseType) switch(traverseType) case 1: System.out.print(nPreorder traversal: ); preOrder(root); break; case 2: System.out.print(nInorder traversal: ); inOrder(root); break; case 3: System.out.print(nPostorder traversal: ); postOrder(root); break; System.out.println(); 進(jìn)行遍歷操作，通過(guò)switch 操作選擇遍歷的方式：先根遍歷、中根遍歷、后跟遍歷。四、查找操作public Node find(int key) / find node with given key / (assumes non-empty tree) Node current = root; / start at root while(current.iData != key) / while no match, if(key current.iData) / go left? current = current.leftChild; else / or go right? current = current.rightChild; if(current = null) / if no child, return null; / didnt find it return current; / found it / end find()首先，將當(dāng)前指針指向樹的根節(jié)點(diǎn)(Node current = root)。然后，當(dāng)查找元素時(shí)，先比較要找的元素與當(dāng)前找到的元素的數(shù)值大小關(guān)系，如果比當(dāng)前找到的元素?cái)?shù)值小(key current.iData)，則指針就接著找此節(jié)點(diǎn)的左孩子節(jié)點(diǎn)繼續(xù)尋找(current = c