那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

二叉查找树的解析与实现

二叉查找树是二叉树的一个特化,它具有的特殊性质是:对于树中的任何一个结点,它的左子树的所有结点的关键字都小于此结点的关键字,而右子树的所有结点的关键字都大于此结点的关键字.

二叉查找树的这种特殊性质使得它在查找元素的时候特别的方便,每一次查找都可以去掉一半的元素,因此查找的时间是O(logN).

二叉查找树的插入和查找算法也是很简单的,就是与当前结点的关键字作比较决定在右边还是左边继续操作.

二叉查找树最复杂的算法就是删除结点的算法了,根据所要删除的结点有两个子结点还是只有一个或者没有子结点会有不同的处理.有两个子结点的情况一般的处理是找到右子树中值最小的一个结点,将它的值替代当前的结点值,然后再把这个值最小的结点删除,也就是说有两个子结点的情况是用最小的一个大于当前结点关键字的结点替代了当前的结点(很拗口,但愿我说清楚了:)在只有一个或者没有子结点的情况就比较的简单了,如果还有子结点就把子结点的位置往上挪,然后把当前结点删除.

实现如下:
1)BSTree.h
/********************************************************************
    created:    2006/07/28
    filename:     BSTree.h
    author:        李创
                
http://www.cppblog.com/converse/

    purpose:    二叉查找树的实现代码
********************************************************************
*/


#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

#include 
<stdio.h>

template
<typename T>
struct BTreeNode
{
    T    Data;
    BTreeNode
* pLeft;
    BTreeNode
* pRight;
    BTreeNode
* pParent;

    BTreeNode(    T data 
= T(), BTreeNode<T>* Parent = NULL, 
                BTreeNode
<T>* Left = NULL, BTreeNode<T>* Right = NULL)
                : Data(data), pLeft(Left), pRight(Right), pParent(Parent)
    
{
    }

}
;

template
<typename T>
class BSTree
{
protected:
    BTreeNode
<T>*    m_pRootNode;

public:
    BSTree(BTreeNode
<T>* pRoot = NULL) 
        : m_pRootNode(pRoot)
    
{
    }

    
~BSTree();

    
void            Display();
    BTreeNode
<T>*    Insert(const T& data);
    BTreeNode
<T>*    Find(const T& data);
    BTreeNode
<T>*    FindMin();
    BTreeNode
<T>*    FindMax();
    BTreeNode
<T>*    Delete(const T& data);

private:
    
void            Display(BTreeNode<T>* p);
    BTreeNode
<T>*    Insert(const T& data, BTreeNode<T>* p);
    BTreeNode
<T>*    Find(const T& data, BTreeNode<T>* p);
    BTreeNode
<T>*    FindMin(BTreeNode<T>* p);
    BTreeNode
<T>*    FindMax(BTreeNode<T>* p);
    BTreeNode
<T>*    Delete(const T& data, BTreeNode<T>* p);

    
void            DestructImpl(BTreeNode<T>* p);
}
;

#endif

2)BSTree.cpp
/********************************************************************
    created:    2006/07/28
    filename:     BSTree.cpp
    author:        李创
                
http://www.cppblog.com/converse/

    purpose:    二叉查找树的实现代码
********************************************************************
*/


#include 
<iostream>
#include 
"BSTree.h"

template
<typename T>
BSTree
<T>::~BSTree()
{
    DestructImpl(m_pRootNode);
}


template
<typename T>
void BSTree<T>::DestructImpl(BTreeNode<T>* p)
{
    
if (NULL == p)
        
return;

    DestructImpl(p
->pLeft);
    DestructImpl(p
->pRight);
    p
->pLeft = NULL;
    p
->pRight = NULL;
    p
->pParent = NULL;
    delete p;
    p 
= NULL;
}


template
<typename T>
void BSTree<T>::Display()
{
    Display(m_pRootNode);
}


// 中序打印出树中的元素,这样应该是从小到大的顺序
template<typename T>
void BSTree<T>::Display(BTreeNode<T>* p)
{
    
if (NULL == p)
        
return;

    Display(p
->pLeft);
    std::cout 
<< "Node = " << p->Data << std::endl;
    Display(p
->pRight);
}


template
<typename T>
BTreeNode
<T>* BSTree<T>::Insert(const T& data)
{
    
return Insert(data, m_pRootNode);
}


template
<typename T>
BTreeNode
<T>* BSTree<T>::Insert(const T& data, BTreeNode<T>* p)
{
    
if (NULL == p)
    
{
        p 
= new BTreeNode<T>(data);

        
if (NULL == p)
        
{
            
return NULL;
        }

        
else if (NULL == m_pRootNode)
        
{
            m_pRootNode 
= p;
        }

    }

    
else if (data > p->Data)
    
{
        p
->pRight = Insert(data, p->pRight);
        
if (NULL != p->pRight)
        
{
            p
->pRight->pParent = p;
        }

    }

    
else
    
{
        p
->pLeft = Insert(data, p->pLeft);
        
if (NULL != p->pLeft)
        
{
            p
->pLeft->pParent = p;
        }

    }


    
return p;
}


template
<typename T>
BTreeNode
<T>* BSTree<T>::Find(const T& data)
{
    
return Find(data, m_pRootNode);
}


template
<typename T>
BTreeNode
<T>* BSTree<T>::Find(const T& data, BTreeNode<T>* p)
{
    
if (NULL == p)
    
{
        
return NULL;
    }

    
else
    
{
        
if (data == p->Data)
        
{
            
return p;
        }

        
else if (data > p->Data)
        
{
            
return Find(data, p->pRight);
        }

        
else
        
{
            
return Find(data, p->pLeft);
        }

    }

}


template
<typename T>
BTreeNode
<T>* BSTree<T>::FindMin()
{
    
return FindMin(m_pRootNode);
}


template
<typename T>
BTreeNode
<T>* BSTree<T>::FindMin(BTreeNode<T>* p)
{
    
if (NULL == p)
    
{
        
return NULL;
    }


    
if (NULL != p->pLeft)
    
{
        
return FindMin(p->pLeft);
    }

    
else
    
{
        
return p;
    }

}


template
<typename T>
BTreeNode
<T>* BSTree<T>::FindMax()
{
    
return FindMax(m_pRootNode);
}


template
<typename T>
BTreeNode
<T>* BSTree<T>::FindMax(BTreeNode<T>* p)
{
    
if (NULL == p)
    
{
        
return NULL;
    }


    
if (NULL != p->pRight)
    
{
        
return FindMax(p->pRight);
    }

    
else
    
{
        
return p;
    }

}


template
<typename T>
BTreeNode
<T>* BSTree<T>::Delete(const T& data)
{
    
return Delete(data, m_pRootNode);
}


template
<typename T>
BTreeNode
<T>* BSTree<T>::Delete(const T& data, BTreeNode<T>* p)
{
    
if (NULL == p)
    
{
        
return NULL;
    }

    
else if (data < p->Data)
    
{
        p
->pLeft = Delete(data, p->pLeft);
    }

    
else if (data > p->Data)
    
{
        p
->pRight = Delete(data, p->pRight);
    }

    
else if (NULL != p->pLeft && NULL != p->pRight)
    
{
        
// 找到结点且有两个子结点
        BTreeNode<T>* pNode;
        
// 找到右子树中最小的结点,把它的值替换当前结点值,然后删除找到的那个结点
        pNode = FindMin(p->pRight);
        p
->Data = pNode->Data;
        p
->pRight = Delete(p->Data, p->pRight);
    }

    
else
    
{
        
// 找到结点但是只有一个或没有子结点
        
// 如果有子结点就用子结点代替当前结点,然后删除当前结点
        BTreeNode<T>* pNode = p;
        
if (NULL == p->pLeft)
        
{
            p 
= p->pRight;
        }

        
else if (NULL == p->pRight)
        
{
            p 
= p->pLeft;
        }

        delete pNode;
        pNode 
= NULL;
    }


    
return p;
}



3)Main.cpp
#include "BSTree.h"
#include 
<stdlib.h>
#include 
<time.h>

// 创建一个数组,元素值随机设置
void CreateNewArray(int array[], int length)
{
    
for (int i = 0; i < length; i++)
    
{
        array[i] 
= rand() % 256;
    }

}


int main()
{
    
int array[10];
    srand(time(NULL));

    CreateNewArray(array, 
10);
    BSTree
<int> tree;
    
for (int i = 0; i < 10++i)
    
{
        tree.Insert(array[i]);
    }

    tree.Display();
    
if (NULL != tree.Find(array[7]))
    
{
        std::cout 
<< "Find!\n";
    }


    BTreeNode
<int>* pNode;

    
if (NULL != (pNode = tree.FindMin()))
    
{
        std::cout 
<< "Min = " << pNode->Data << std::endl;
    }


    
if (NULL != (pNode = tree.FindMax()))
    
{
        std::cout 
<< "Max = " << pNode->Data << std::endl;
    }


    tree.Delete(array[
7]);
    std::cout 
<< "\nafter delete " << array[7<< std::endl;
    tree.Display();

    system(
"pause");
    
return 0;
}

需要说明一点:上面做测试用的Main.cpp如果单独写在一个文件中就会在链接的时候报错,报的错误是:
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::Insert(int const &)" (?Insert@?$BSTree@H@@QAEPAU?$BTreeNode@H@@ABH@Z) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: __thiscall BSTree<int>::~BSTree<int>(void)" (??1?$BSTree@H@@QAE@XZ) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::Delete(int const &)" (?Delete@?$BSTree@H@@QAEPAU?$BTreeNode@H@@ABH@Z) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::FindMax(void)" (?FindMax@?$BSTree@H@@QAEPAU?$BTreeNode@H@@XZ) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::FindMin(void)" (?FindMin@?$BSTree@H@@QAEPAU?$BTreeNode@H@@XZ) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::Find(int const &)" (?Find@?$BSTree@H@@QAEPAU?$BTreeNode@H@@ABH@Z) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: void __thiscall BSTree<int>::Display(void)" (?Display@?$BSTree@H@@QAEXXZ) referenced in function _main

所以没有办法,我只能将main.cpp中的内容copy到BSTree.cpp中才能链接过去.

如果哪位朋友知道如何解决上面因为采用了模板类出现的链接错误,我不胜感激,谢谢!

posted on 2006-07-29 00:33 那谁 阅读(6589) 评论(2)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: 二叉查找树的解析与实现  回复  更多评论   

实际上,模板的实现应该和它的声明都放在头文件中,这样就可以将main.cpp单独实现出来了。
目前标准cpp中有一个关键字export可以让模板的实现和声明分开在头文件和.cpp文件中,但是目前只有一个编译器实现了改功能(据我所知),而且即使分开了来实现,模板的.cpp实现也是必须要客户端可见的(这和普通的.cpp文件那种将具体实现屏蔽的特性不一样),而且export关键字引入给cpp带来了很多麻烦的事情,大家目前对如何使用export也没有什么经验。
2006-08-27 14:58 | wb

# re: 二叉查找树的解析与实现  回复  更多评论   

我觉得你的display函数,中的<<操作符应重载后再使用,既然使用了模板,就有可能会出现<<并不支持的类型。
2008-03-25 23:13 | cndx100

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理