为什么使用二叉树? 为什么要用到树呢?因为它通常结合了另外两种数据结构的优点:一种是有序数组，另一种是链表。在树中查找数据项的速度和在有序数组中查找一样快，并且插入数据项和删除数据项的速度也和链表一样。下面。我们先来稍微思考一下这些话题，然后再深入地研究树的细节. 在有序数组中插入数据项太慢假设数组中的所有数据项都有序的排列—这就是有序数组，本书已经讲过，用二分查找法可以在有序数组中快速地查找特定的值口它的过程是先查看数组的正中间的数据项，如果那个数据项值比要找的大，就缩小查找范围，在数组的后半段中找;如果小，就在前半段找。反复这个过程，查找数据所需的时间是O(logN)。同时也可以迅速地遍历有序数组， 按顺序访问每个数据项。 然而，想在有序数组中插入一个新数据项，就必须首先查找新数据项播入的位置，然后把所有比新数据项大的数据项向后移动一位，来给新数据项腾出空间。这样多次的移动很费时，平均来讲要移动数组中一半的数据项( Nl2次移动)口删除数据项也需要多次的移动，所以也很慢。 显而易见。如果要做很多的插入和删除操作，就不该选用有序数组。 插入一个节点 insert()方法从创建新节点开始，用提供的数据作为参数。 下一步，insert()必须先确定新节点插入的位置。这段代码与查找节点的代码大致相同，“查找"一个节点的,lava代码”这节中已经介绍过。区别是原来简单的查找节点时，遇到null(不存在)值后，表明要找的节点不存在，于是就立即返回了。现在要插入一个节点，就在返回前插入(要是必要的话，要先创建)节点。 要找的值是从参数id传入的。while循环用true作为它的条件，因为它不关心是否会遇到和id值一样的节点;它把那个有相同关键字值的节点当作关键字值比较大的节点处理。(本章后面将会讨论有重复节点的问题)。 插入节点的位置总会找到的(除非存储器溢出):找到后，新节点被接到树上，while循环从return处跳出。 下面是insert()方法的代码: 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() 这里用一个新的变量parent ( curent的父节点)，来存储遇到的{zh1}一个不是null的节点(图4.8中的50 )。必须这样做，因为c}rrc}t在查找的过程中会变成null，才能发现它查过的上一个节点没有一个对应的子节点。如果不存储parent，就会失去插入新节点的位置。 为了插入新节点，把parent遇到的{zh1}一个非null节点)中对应的子指针指向新节点。如果没找到parent的左子节点，就把新节点接到parent的左子节点处:没找到右子节点，就把新节点接到右子节点处。图4.8中，45就接到50的左子节点处。 遍历树 中序遍历实际的代码非常简单，inOrder()例程中执行上面说的三个步骤。访问节点这个步骤把节点的内容显示出来。和其他递归程序一样，它必须有一个基值情况—在此情况让程序立即返回的条件，而不会再调用自身。在inOrder()方法中，作为参数传入的节点等于null时，就是终止条件。下面就是inOrder()方法的代码: private void inOrder(node localHoot) { if(localRoot != null) { inOrder(localRoot.leftChild) ; System.out.print(localRoot.iData+ ‘ ’) ; inOrder(localHoot.rightChild); } } 开始时用根作为参数调用这个方法: inOrder(root); 之后，它就靠匀己递归调用自己，直到所有节点都被访问过为止。 |
