20120919-二叉树 数据结构《数据结构与算法分析》

简介:

又是一次的毕业季,羡慕嫉妒啊....

二叉查找树类的框架:

复制代码
 1 template <typename Comparable>
 2 class BinarySearchTree
 3 {
 4 public:
 5     BinarySearchTree();
 6     BinarySearchTree(const BinarySearchTree & rhs)
 7     ~BinarySearchTree();
 8 
 9     const Comparable & findMin() const;
10     const Comparable & findMax() const;
11 
12     bool contains(const Comparable & x ) const;
13     bool isEmpty() const;
14     void printTree() const;
15 
16     void makeEmpty();
17     void insert(const Comparable & x);
18     void remove(const Comparable & x);
19 
20     const BinarySearchTree & operator = (const BinarySearchTree & rhs);
21 
22 private:
23     struct BinaryNode
24     {
25         Comparable element;
26         BinaryNode *left;
27         BinaryNode *right;
28 
29         BinaryNode(const  Comparable & theElement,BinaryNode *lt,BinaryNode *rt):element(theElement),left(lt),right(rt){}
30     };
31 
32     BinaryNode *root;
33 
34     void insert (const Comparable & x,BinaryNode * & t) const;
35     void remove (const Comparable & x ,BinaryNode * & t) const;
36     BinaryNode * findMin(BinaryNode *t) const;
37     BinaryNode * findMax(BinaryNode *t) const;
38     bool contains( const Comparable & x,BinaryNode * t) const;
39     void makeEmpty( BinaryNode * & t);
40     void printTree(BinaryNode *t) const;
41     BinaryNode * clone(BinaryNode *t) const;
42 };
复制代码

contains    insert   remove三种操作递归列表:

复制代码
bool contains (const Comparable & x) const
{
    return contains(x,root)
}
void insert(const Comparable & x)
{
    insert (x,root);
}
void remove(const Comparable & x)
{
    remove(x,root);
}
复制代码

二叉查找树的contains操作:

复制代码
 1 bool contains(const Comparable & x,BinaryNode * t) const
 2 {
 3     if( t == NUll )
 4         return false;
 5     else if ( x < t->element )
 6         return contains(x,t->left );
 7     else if (t->element < t)
 8         return contains(x,t->right);
 9     else
10         return true;
11 }
复制代码

 

使用函数对象 实现 二叉查找树:

复制代码
template <typename Object,typename Comparator = less<Object>>
class BinarySearchTree
{
    public:
    private:
        BinaryNode * root;
        Comparable isLessThan;

        bool contains( const Object & x,BinaryNode *t ) const
        {
            if(t == NULL)
                return false;
            else if (isLessThan(x,t->element))
                return contains(x,t->left);
            else if (isLessThan(t->element,x))
                return contains(x,t->right);
            else
                return true;
        }
};
复制代码

findMin方法的递归实现:

复制代码
1 BinaryNode * findMin( BinaryNode * t) const
2 {
3     if( t == NULL)
4         return NULL;
5     if(t->left == NULL)
6         return t;
7     return findMin(t->left);
8 }
复制代码

findMax方法的递归实现:

复制代码
1 BinaryNode * findMax(BinaryNode * t) const
2 {
3     if(t != NULL)
4         while( t ->right !=NULL)
5             t = t->right;
6     return t;
7 }
复制代码

二叉查找树插入操作:

复制代码
 1 void insert( const Comparable & x,BinaryNode * & t )
 2 {
 3     if( t== NULL)
 4         t = new BinaryNode(x,NULL,NULL);
 5     else if (x<t->element)
 6         insert(x,t->left);
 7     else if (t->element < x)
 8         insert(x,t->right);
 9     else
10         ;
11 }
复制代码

二叉查找树 删除操作:

复制代码
 1 void remove (const Comparable & x,BinaryNode * & t)
 2 {
 3     if( t == NULL)
 4         return;
 5     if( x <  t->element)
 6         remove( x,t->left);
 7     else if ( t->element < x)
 8         remove(x,t->right);
 9     else if (t->left != NULL && t->right!=NULL )
10     {
11         t->element = findMin( t->right)->element;
12         remove(t->element , t->right);
13     }
14     else
15     {
16         BinaryNode *oldNode = t;
17         t = ( t->left !=NULL) ? t->left : t->right;
18         delete oldNode;
19     }
20 }
复制代码

析构函数递归实现makeEmpty

复制代码
~BinarySearchTree()
{
    makEmpty();
}
void makeEmpty(BinaryNode * & t)
{
    if( t != NULL)
    {
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
    }
    t = NULL;
}
复制代码

operator= 递归实现clone:

复制代码
 1 const BinarySearchTree & operator=( const BianrySearchTree & rhs)
 2 {
 3     if(this != &rhs)
 4     {
 5         makeEmpty();
 6         root = clone(rhs.root);
 7     }
 8     return *this;
 9 }
10 
11 BinaryNode * clone( BinaryNode * t) const
12 {
13     if( t == NULL)
14         return NULL;
15     return new BinaryNode ( t->element,clone(t->left),clone(t->right));
16 }
复制代码
本文转自博客园xingoo的博客,原文链接:20120919-二叉树 数据结构《数据结构与算法分析》,如需转载请自行联系原博主。
相关文章
|
12天前
|
存储 机器学习/深度学习
【数据结构】二叉树全攻略,从实现到应用详解
本文介绍了树形结构及其重要类型——二叉树。树由若干节点组成,具有层次关系。二叉树每个节点最多有两个子树,分为左子树和右子树。文中详细描述了二叉树的不同类型,如完全二叉树、满二叉树、平衡二叉树及搜索二叉树,并阐述了二叉树的基本性质与存储方式。此外,还介绍了二叉树的实现方法,包括节点定义、遍历方式(前序、中序、后序、层序遍历),并提供了多个示例代码,帮助理解二叉树的基本操作。
38 13
【数据结构】二叉树全攻略,从实现到应用详解
|
9天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
9天前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构,其中节点的度为其分支数量,树的度为树中最大节点度数。二叉树是一种特殊的树,其节点最多有两个子节点,具有多种性质,如叶子节点数与度为2的节点数之间的关系。此外,还介绍了二叉树的不同形态,包括满二叉树、完全二叉树、二叉排序树和平衡二叉树,并探讨了二叉树的顺序存储和链式存储结构。
|
9天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
|
1月前
|
算法
【初阶数据结构篇】二叉树算法题
二叉树是否对称,即左右子树是否对称.
|
1月前
|
存储
【初阶数据结构篇】实现链式结构二叉树(二叉链)下篇
要改变root指针的指向,将本来指向根节点的root指针改为空,所以传二级指针(一级指针也可以,只不过在调用完记得把root置为空)。
|
1月前
|
存储 测试技术
【初阶数据结构篇】实现链式结构二叉树(二叉链)上篇
先构建根结点,再对左右子树构建,每次需要时申请一个结点空间即可,否则返回空指针。
|
1月前
|
存储 算法 测试技术
【初阶数据结构篇】实现顺序结构二叉树(堆的实现方法)
注意传过去的参数是插入的位置,即插入前的size,在调整完后再将size++
|
1月前
|
算法 索引
【初阶数据结构篇】单链表算法题进阶
深拷贝应该正好由 n 个全新节点组成,其中每个新节点的值都设为其对应的原节点的值。
|
1月前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点,然后把后半部分逆置,最近前后两部分一一比对,如果节点的值全部相同,则即为回文。