`
kmplayer
  • 浏览: 509909 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

二叉树的一些基本操作

 
阅读更多
1,这段时间看书有点多了,以前熟悉的东西反而淡忘了.
是总结下基础的时候了.
2,实例代码:
#include <iostream>
#include <stack>
#include <queue>
#include <stdexcept>
using namespace std;

template <class T>
struct BSTNode
{
    BSTNode();
    BSTNode(const T& val,BSTNode<T>* l=NULL,BSTNode<T>* r=NULL);  //成员函数只是两个构造函数
    T  key;
    BSTNode<T>* left;
    BSTNode<T>* right;

};

template <class T>
BSTNode<T>::BSTNode(const T& val,BSTNode<T>* l,BSTNode<T>* r)
:key(val),left(l),right(r)
{}

template <class T>
BSTNode<T>::BSTNode():left(NULL),right(NULL)
{}



template <class Type>
class BSTree
{
public:
    BSTree();
    ~BSTree()
    {
        destroy(root);
    }

    bool isempty()
    {
        return root==NULL;
    }
    void visit(BSTNode<Type>* p);
    void insert(Type p); //在二叉树中插入一个节点
    int height() //返回高度
    {
        return height(root);
    }
    int nodecount()
    {
        return nodecount(root);
    }
    int leafcount()
    {
        return leafcount(root);
    }
    void inorder()
    {
        inorder(root);
    }
    void preorder()
    {
        preorder(root);
    }
    void postorder()
    {
        postorder(root);
    }
    void levelorder()
    {
        levelorder(root);
    }
    BSTNode<Type>* copytree(BSTNode<Type>* p);
    BSTree& operator=(const BSTree& tr);
private:
    int height(BSTNode<Type>* p);
    int nodecount(BSTNode<Type>* p);
    int leafcount(BSTNode<Type>* p);
    void destroy(BSTNode<Type>* p);
    void preorder(BSTNode<Type>* p);
    void inorder(BSTNode<Type>* p);
    void postorder(BSTNode<Type>* p);
    void levelorder(BSTNode<Type>* p);
private:
    BSTNode<Type> * root;
};

template <class Type>
BSTree<Type>::BSTree():root(NULL)
{} //初始化NULL非常的重要,便于以后对每个节点判断是否为0

template <class Type>
void BSTree<Type>::insert(Type p)
{
    if(root==NULL)
        root=new BSTNode<Type>(p);  //注意,节点的每一个指针都保证是用new动态分配资源
    else
    {
        BSTNode<Type>* pre;
        BSTNode<Type>* tmp=root;
        while(tmp!=NULL)
        {
            pre=tmp;
            if(tmp->key==p)
            {
                return;//假设只能插入不同的节点
            }
            else if(p<tmp->key)
            {
                tmp=tmp->left;
            }
            else
            {
                tmp=tmp->right;
            }
        }
        if(p<pre->key)
            pre->left=new BSTNode<Type>(p);
        else if(p>pre->key)
            pre->right=new BSTNode<Type>(p);
    }

}

template <class Type>
int BSTree<Type>::height(BSTNode<Type>* p)
{
    if(p==NULL)
        return 0;
    else
        return 1+( height(p->left)>height(p->right)? height(p->left):height(p->right) );
}

template <class Type>
int BSTree<Type>::nodecount(BSTNode<Type>* p)
{
    if(p==NULL)
        return 0;
    else
        return 1+nodecount(p->left)+nodecount(p->right);
}

template <class Type>
int BSTree<Type>::leafcount(BSTNode<Type>* p)  //就编了这么一个出来
{
    if(p==NULL)
        return 0;
    else  if(p->left==NULL&&p->right==NULL)
        return 1;
    else
        return leafcount(p->left)+leafcount(p->right);
}

template <class Type>
void BSTree<Type>::destroy(BSTNode<Type>* p)
{
    if(p!=NULL)
    {
        destroy(p->left);
        destroy(p->right);
        delete p;
        p=NULL;
    }
}

template <class Type>
void BSTree<Type>::visit(BSTNode<Type>* p)
{
    cout<<p->key<<" ";
}

template <class Type>
void BSTree<Type>::inorder(BSTNode<Type>* p)
{
    if(p!=NULL)
    {
        inorder(p->left);
        visit(p);
        inorder(p->right);
    }
}

template <class Type>
void BSTree<Type>::preorder(BSTNode<Type>* p)
{
    if(p!=NULL)
    {
        visit(p);
        preorder(p->left);
        preorder(p->right);
    }
}
template <class Type>
void BSTree<Type>::postorder(BSTNode<Type>* p)
{
    if(p!=NULL)
    {
        postorder(p->left);
        postorder(p->right);
        visit(p);
    }
}

template <class Type>
void BSTree<Type>::levelorder(BSTNode<Type>* p)
{
    if(p==NULL)
        return;
    queue< BSTNode<Type>* > que;
    que.push(p);
    BSTNode<Type>* tmp;
    while(!que.empty())
    {
        tmp=que.front();
        visit(tmp);
        que.pop();
        if(tmp->left!=NULL)
            que.push(tmp->left);
        if(tmp->right!=NULL)
            que.push(tmp->right);
    }
}

template <class Type>
BSTNode<Type>* BSTree<Type>::copytree(BSTNode<Type>* p)
{
    if(p==NULL)
        return NULL;
    BSTNode<Type>* l=copytree(p->left);
    BSTNode<Type>* r=copytree(p->right);
    BSTNode<Type>* tree=new BSTNode<Type>(p->key,l,r);
    return tree;
}

template <class Type>
BSTree<Type>& BSTree<Type>::operator=(const BSTree& tr)
{
    if(this!=&tr)
    {
        destroy(); //释放当前的
        copytree(tr.root);
        return *this;
    }

}

int main()
{
    BSTree<char> bstchar;
    cout<<bstchar.isempty()<<endl;
    cout<<"叶子个数:"<<bstchar.leafcount()<<endl;

    BSTree<int> bstlist;
    for(int i=0;i!=15;i++)
        bstlist.insert(i); //实际上是一个但链表,
    cout<<"bstlist的高度:"<<bstlist.height()<<endl;
    cout<<"叶子个数:"<<bstlist.leafcount()<<endl;

    int val[]={5,3,7,1,4,6,8,9};
    BSTree<int> bstarray;
    for(int i=0;i<sizeof(val)/sizeof(val[0]);i++)
        bstarray.insert(val[i]); //实际上是一个但链表,

    cout<<"bstarray的高度:"<<bstarray.height()<<endl;
    cout<<"递归中序遍历的结果:";
    bstarray.inorder();
    cout<<endl;
    cout<<"递归先序遍历的结果:";
    bstarray.preorder();
    cout<<endl;
    cout<<"递归后序遍历的结果:";
    bstarray.postorder();
    cout<<endl;
    cout<<"水平遍历的结果:";
    bstarray.levelorder();
    cout<<endl;
    cout<<"节点个数:"<<bstarray.nodecount()<<endl;
    cout<<"叶子个数:"<<bstarray.leafcount()<<endl;
    return 0;
}
分享到:
评论

相关推荐

    二叉树的基本操作的源代码

    二叉树的基本操作源代码 二叉树是一种重要的数据结构,在计算机科学中有广泛的应用,本文将对二叉树的基本操作进行详细的介绍和分析。 一、实验目的 本实验的目的是为了熟悉二叉树的结构和基本操作,掌握对二叉树...

    数据结构实验-二叉树的基本操作

    运用二叉链表实现二叉树的基本操作,包括:创建二叉树的存储结构、复制已有的二叉树、计算已有的二叉树的深度、先根序序列、中根序序列、后根序序列等。 输入格式:AB#C##D## 二、实验目的 掌握二叉链表及二叉树的...

    数据结构实验:二叉树的基本操作

    南邮数据结构实验使用C++描述,二叉树的基本操作

    数据结构二叉树的基本操作实验报告

    在本实验报告中,我们探讨了二叉树的基本操作,主要涉及了二叉树的构建以及遍历。二叉树是一种特殊的数据结构,每个节点最多有两个子节点,通常分为左子节点和右子节点。本实验的目标是使用二叉链表作为存储结构,...

    实验五 二叉树的基本操作实现

    二叉树基本操作实现 二叉树是一种基本的数据结构,它广泛应用于计算机科学和软件工程中。在本实验中,我们将学习二叉树的基本操作,包括二叉树的建立、遍历、结点数统计、深度计算和叶子结点个数统计。 一、实验...

    《数据结构课程设计》二叉树基本操作实验程序(10种基本操作)

    在这个《数据结构课程设计》项目中,我们专注于二叉树的基本操作,通过两个源文件(file1.cpp 和 file2.cpp)以及一个头文件(head.h)实现了一系列的二叉树操作。以下是这些操作的详细说明: 1. **创建二叉树**:...

    平衡二叉树的基本操作

    下面我们将详细探讨平衡二叉树的基本操作。 1. 插入操作: 在平衡二叉树中插入一个新节点,首先需要像普通二叉搜索树那样进行操作,找到合适的位置插入。如果插入导致某子树高度失衡,需要通过旋转操作来重新平衡...

    二叉树的基本操作实现及其应用

    设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1. 按先序次序建立一个二叉树 ,用#表示某结点的左右子树是否为空,用于表示该结点是否...

    二叉树的基本操作java代码

    以上就是关于二叉树基本操作的Java实现。理解这些操作对于理解和编写涉及数据结构的算法至关重要,因为二叉树在搜索、排序和许多其他应用中都有广泛的应用。通过实际的代码练习,你可以更好地掌握这些概念并提升编程...

    二叉树的基本操作代码

    二叉树的先序遍历,判断二叉树是否为空,深度的计算,结点多少的计算

    设计程序实现二叉树结点的类型定义和对二叉树的基本操作

    ### 二叉树基本操作知识点解析 #### 一、实验目的 在本实验中,学习者将通过实际编程练习来加深对二叉树这一数据结构的理解,并熟练掌握其基本操作。具体目标包括: 1. **熟悉二叉树结点的结构和对二叉树的基本...

    二叉树的基本操作

     建立一棵用二叉链表方式存储的二叉树(以先序来建立),并实现下列操作: 先序遍历二叉树; 2.中序遍历二叉树;3.后序遍历二叉树。 算法思想: 算法中主要用到的函数如下:  ①void main() //主函数  ②void ...

    c++二叉树的基本操作

    递归二叉树的基本操作,递归创建,递归先序遍历、中序遍历、后序遍历,求树的高度,求叶子结点的个数,交换树的左右孩子

    数据结构课程设计-二叉树的基本操作

    数据结构课程设计-二叉树的基本操作 本资源摘要信息是关于数据结构课程设计的,主题是二叉树的基本操作。该设计报告的主要内容包括创建二叉树、以先序、中序、后序遍历二叉树、查找子节点元素等操作。 一、 创建...

    二叉树的基本操作及哈夫曼编码译码系统的实现

    目的:1、掌握二叉链表上实现二叉树基本操作。 2、学会设计基于遍历的求解二叉树应用问题的递归算法。 3、理解哈夫曼树的构造算法,学习设计哈夫曼编码和译码系统 要求:能成功演示二叉树的有关算法,运算完毕后能...

    C++二叉树基本操作

    以下是对C++实现的二叉树基本操作的深入分析。 ### 二叉树节点定义 在代码中,二叉树节点`BiNode`被定义为一个结构体,包含三个成员:`data`存储节点的数据,`lchild`指向左子节点,`rchild`指向右子节点。这个...

    数据结构二叉树的基本操作

    本节我们将深入探讨二叉树的基本操作,包括递归与非递归的先序、中序、后序遍历,以及计算叶子数目和树的高度。 首先,我们来看**先序遍历**。先序遍历的顺序是:根节点 -&gt; 左子树 -&gt; 右子树。递归实现的方法是,...

    实验四 二叉树基本操作的实现

    在本实验中,我们将深入探讨数据结构中的一个重要概念——二叉树,并实现其基本操作。二叉树是一种非线性的数据结构,它由一个有限集合的节点构成,每个节点最多有两个子节点,通常称为左子节点和右子节点。这个实验...

Global site tag (gtag.js) - Google Analytics