数据结构与算法学习笔记——树 C++实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法学习笔记——树 C++实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4094字，纯文字阅读大概需要6分钟。

内容图文

数据结构与算法学习笔记——树 C++实现

• 1 特点
• 2 遍历的方法
• • 前序遍历
  • 后序遍历
  • 层序遍历
• 3 实现

1 特点

树形结构，每个结点（除了根结点）具有唯一的前驱，可以有多个后继

树是递归定义的：一个非空的树，有一个根结点、以及0个或若干个非空子树，子树与根结点由一条边相连（子树中又有自己的根结点并可以有子结点、甚至子树的子树）

由于树是递归定义的，因此树的建立、删除、遍历以及后面BST ADT的一些操作都可以用遍历的方式实现

关于树的概念：子结点和父结点、叶子结点、兄弟、路径和路径长度、（一结点的）深度和高度、（一结点的）祖先和后代

2 遍历的方法

在二叉树的实现（下一篇介绍）中还有中序遍历

前序遍历

先访问根结点，再访问其每一个孩子

后序遍历

先访问每一个孩子再访问根结点

层序遍历

先访问第n层，再访问第n+1层。可以利用队列实现

应用较少

3 实现

这里结点的两个指针分别指向第一个孩子和下一个兄弟，在二叉树的实现（下一篇介绍）中还有指向左孩子和右孩子的方式

树的创建用前序遍历的方式，树的删除用后续遍历的方式（要在删除父结点之前删除子结点）

注意这里的层序遍历的实现是有问题的，真正的实现方法可以利用队列实现，贴出来这个有问题的实现方法是为了和前序遍历后序遍历对比，加深（主要是对递归的）理解

Tree.h

#include <iostream>
const int nullnum = -1;     // 这里用data与nullnum比较，条件相符则表示空结点
template <typename T>       // 结点的指针变量指向第一个孩子和下一个兄弟
struct TreeNode
{
    T data;
    TreeNode *firstChild;
    TreeNode *nextSibling;
};

template <typename T>
class Tree
{
public:
    Tree();
    ~Tree();
    void PreTravel();
    void PostTravel();
    void LevelorderTravel();
private:
    TreeNode<T> *_root = NULL;
    TreeNode<T> *_CreateTree(); 
    void _DeleteTree(TreeNode<T> *);
    void _PreTravel(TreeNode<T> *);
    void _PostTravel(TreeNode<T> *);
    void _LevelorderTravel(TreeNode<T> *);
protected:
};

Tree.cpp

#include "Tree.h"

/*
 * 在构造函数中调用创建树的函数
 */ 
template <typename T>
Tree<T>::Tree()
{
    std::cout << "Please input the node's data:" << std::endl;
    _root = Tree<T>::_CreateTree();
}
/*
 * 在析构函数中调用删除树的函数
 */ 
template <typename T>
Tree<T>::~Tree()
{
    Tree<T>::_DeleteTree(_root);
}
/*
 * 按照前序遍历的方式创建一个树
 * 注意这里有递归调用，所以没有直接把函数体写在构造函数中，后面删除树类似
 * 判断结点是否为空用的是判断data==nullnum的方式，其实这种方式不适合实型变量
 */ 
template <typename T>
TreeNode<T> *Tree<T>::_CreateTree()
{
    TreeNode<T> *root = NULL;
    T data;    
    std::cin >> data;
    if(data == T(nullnum))
    {
        return NULL;
    }
    else
    {
        root = new TreeNode<T>;
        root->data = data;
        root->firstChild = _CreateTree();
        root->nextSibling = _CreateTree();
    }
    return root;
}
/*
 * 按照后序遍历的方式删除一个树
 */ 
template <typename T>
void Tree<T>::_DeleteTree(TreeNode<T> *tree)
{
    if(tree)
    {
        _DeleteTree(tree->firstChild);
        TreeNode<T> *nextSibling = tree->nextSibling;
        delete tree;
        tree = NULL;
        _DeleteTree(nextSibling);
    }
}
/*
 * 前序遍历内部方法
 */ 
template <typename T>
void Tree<T>::_PreTravel(TreeNode<T> *tree)
{
    if(tree)
    {
        std::cout << tree->data << '\t';
        _PreTravel(tree->firstChild);
        _PreTravel(tree->nextSibling);
    }
}
/*
 * 前序遍历
 */ 
template <typename T>
void Tree<T>::PreTravel()
{
    if(_root)
        _PreTravel(_root);
    else
        std::cout << "this tree is null";
    std::cout << std::endl;
}
/*
 * 后序遍历内部方法
 */
template <typename T>
void Tree<T>::_PostTravel(TreeNode<T> *tree)
{
    if(tree)
    {
        _PostTravel(tree->firstChild);
        std::cout << tree->data << '\t';
        _PostTravel(tree->nextSibling);
    }
}
/*
 * 后序遍历
 */
template <typename T>
void Tree<T>::PostTravel()
{
    if(_root)
        _PostTravel(_root);
    else
        std::cout << "this tree is null";
    std::cout << std::endl;
}
/*
 * （伪）层序遍历内部方法
 * 为什么说是伪层序遍历呢，因为这里实现的方法不能保证同一层结点元素是从左到右顺序遍历的
 * 如何实现真正的层序遍历呢，可以利用队列实现，参考图的广度优先搜索算法
 */ 
template <typename T>
void Tree<T>::_LevelorderTravel(TreeNode<T> *tree)
{
    if(tree)
    {
        std::cout << tree->data << '\t';
        _LevelorderTravel(tree->nextSibling);
        _LevelorderTravel(tree->firstChild);
    }
}
/*
 * （伪）层序遍历
 */ 
template <typename T>
void Tree<T>::LevelorderTravel()
{
    if(_root)
        _LevelorderTravel(_root);
    else
        std::cout << "this tree is null";
    std::cout << std::endl;
}

template class Tree<int>;

main.cpp

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

int main()
{
    Tree<int> tree1;
    tree1.PreTravel();
    tree1.PostTravel();
    tree1.LevelorderTravel();
    return 0;
}

运行结果：
实现了如下图所示的树:

内容总结

以上是互联网集市为您收集整理的数据结构与算法学习笔记——树 C++实现全部内容，希望文章能够帮你解决数据结构与算法学习笔记——树 C++实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---