TAG:
|
查找树是二叉树数据结构的一种应用，在这种查找树当中我们可以以O(h)的时间来进行元素的插入、删除以及查找操作。因此只要查找树的高度合适那么将获得较为优秀的性能。 查找树是这样的一种二叉树，对于一棵查找树上的每一个节点而言，以其左孩子为根节点的二叉树上的任何节点的关键值都小于货等于该节点的关键值，而以其右孩子为根节点的二叉树上任何节点的关键值都大于等于该节点的关键值。 根据这样的要求，我们需要对采用二叉链表表示的二叉树数据结构做一定的修改，因为在查找、插入喝删除节点的过程当中我们经常需要获取某个节点的父亲节点，因此我们在每个节点的数据结构上加入了一个指向其父亲节点的指针。 一、在查找树当中查找节点 根据查找树的特点，我们可以对比需要查找的关键值与当前指向查找树上节点的的关键值的大小来确定查找的走向，以此最终确定查找的路径，其具体算法的代码如下： Node *Find(const Tree &t,int key) { Node *node = t.root; while (node && node->key != key) { if (key < node->key) node = node->lChild; else node = node->rChild; } return node; } 二、向查找树当中插入节点 当我们向查找树当中插入节点时，算法首先假设插入的节点被插入到原有树的叶子节点以下。因此我们需要使用两个指针：一个指向新节点插入的位置，另一个指向新节点插入后的父亲节点，而这两个节点的定位也是根据查找树的基本性质。由于我们首先在算法当中假设了新节点被插入到原有查找树的最低处，因此在定位过程当中我们以指向插入位置的指针变为空为中止条件。具体算法如下： void Insert(Tree &t,int key) { Node *newNode = new Node; newNode->key = key; newNode->Parent = newNode->lChild = newNode->rChild = 0; Node *Parent = 0; Node *InsPos = t.root; while (InsPos) { Parent = InsPos; if (key < InsPos->key) InsPos = InsPos->lChild; else InsPos = InsPos->rChild; } if (Parent == 0) t.root = newNode; else { if (key < Parent->key) Parent->lChild = newNode; else Parent->rChild = newNode; newNode->Parent = Parent; } } 三、删除查找树当中的某个节点 当我们需要删除查找树当中的某个节点时我们需要考虑以下三种情况(如图)，对于每种情况我们首先要考虑的是确定要删除节点的位置(因为在第三种情况当中原本指向的节点并不被删除而只是更新了关键值)，然后对于删除节点的父亲和子女进行指针的修正即可，具体算法如下： void Delete(Tree &t,Node *node) { Node *DeletePos; if (node->lChild == 0 || node->rChild == 0) DeletePos = node; else { DeletePos = node->rChild; while (DeletePos->lChild) DeletePos = DeletePos->lChild; } Node *ParentPos = DeletePos->Parent; Node *ChildPos; if (DeletePos->lChild) ChildPos = DeletePos->lChild; else ChildPos = DeletePos->rChild; if (ChildPos) ChildPos->Parent = ParentPos; if (DeletePos->Parent == 0) t.root = ChildPos; else if (ParentPos->lChild == DeletePos) ParentPos->lChild = ChildPos; else ParentPos->rChild = ChildPos; if (DeletePos != node) node->key = DeletePos->key; delete DeletePos; } 
(iwgh) |