二叉链表

二叉链表的实现在数据结构里不可谓不是一个难点；它对递归方法的依赖程度比较高。递归，至少是对我来说，并不是那么直观的东西；几行的代码往往需要一个初学者在他的头脑中追踪几十行才能发现它到底是怎样运作的。

我在下面给出了一种实现方式：

//bitree.cpp

#include <initializer_list>
#include <iostream>
using namespace std;

//二叉链表结点类
class Node
{
    public:
    string data;
    Node *leftChild,*rightChild;
};

//二叉链表类
class Bitree
{
    public:
    //初始化函数
    Bitree();
    //析构函数
    ~Bitree();
    //先序遍历
    void pre_show(Node*);
    //中序遍历
    void in_show(Node*);
    //后序遍历
    void post_show(Node*);
    //根结点
    Node *root;

    private:
    //初始化和新建结点使用
    void create(Node*);
    //析构和删除结点使用
    void del(Node*);
};

//初始化
inline Bitree::Bitree()
{
    create(root);
}
inline void Bitree::create(Node *tree)
{
    string data;
    cin>>data;
    if(data=="#") tree=nullptr;
    else
    {
        tree=new Node;
        tree->data=data;
        create(tree->leftChild);
        create(tree->rightChild);
    }
}

//先序、中序、后序遍历
inline void Bitree::pre_show(Node *tree)
{
    if(tree)
    {
        cout<<tree->data<<" ";
        pre_show(tree->leftChild);
        pre_show(tree->rightChild);
    }
}
inline void Bitree::in_show(Node *tree)
{
    if(tree)
    {
        pre_show(tree->leftChild);
        cout<<tree->data<<" ";
        pre_show(tree->rightChild);
    }
}
inline void Bitree::post_show(Node *tree)
{
    if(tree)
    {
        pre_show(tree->leftChild);
        pre_show(tree->rightChild);
        cout<<tree->data<<" ";
    }
}

//析构
inline void Bitree::del(Node *tree)
{
    if(tree)
    {
        if(tree->leftChild) del(tree->leftChild);
        if(tree->rightChild) del(tree->rightChild);
        delete tree;
    }
}
inline Bitree::~Bitree()
{
    del(root);
}

//主程序
int main()
{
    Bitree bitree;
    Node *root = bitree.root;
    cout<<"先序遍历:\t";
    bitree.pre_show(root);
    cout<<endl<<"中序遍历:\t";    
    bitree.in_show(root);
    cout<<endl<<"后序遍历:\t";
    bitree.post_show(root);
    cout<<endl;
}

//进行输入： A B C # # D E # G # # F # # #
//结果如下： 
//先序遍历:       A B C D E G F 
//中序遍历:       B C D E G F A 
//后序遍历:       B C D E G F A

这里有一个小陷阱。如果你照搬了这段程序并且运行了它，你会发现发生了这样的错误：

[1] 95096 segmentation fault ./bitree

这是因为这段程序的初始化部分存在问题。问题代码如下：

inline void Bitree::create(Node *tree)

当你传入 Node * 时，你所传入的其实只是该指针的一个拷贝；你在这个拷贝下创建了二叉链表的所有结点，但是对关键的根结点没有进行任何操作。明白问题所在，办法就显而易见了：一种办法是使 create(Note *) 函数返回一个指向 Node 的指针；而我选择改动少的方法，即将 Node * 改为 Node *& ，即指针的一个引用。相应的，函数的声明部分也需要进行修改。