常用数据结构-二叉树的链式存储、建立和遍历

╰半夏微凉° 2023-10-17 13:46 5阅读 0赞

## 1. 链式二叉树简介 ##

二叉树是数据结构——树的一种，一般定义的树是指有一个根节点，由此根节点向下分出数个分支结点，以此类推以至产生一堆结点。树是一个具有代表性的非线性数据结构，所谓的非线性，就是指不再是一对一，而是一对多，不过我觉得其实无论是线性还是非线性，无非就是指针指向的对象个数而已，毕竟双向链表中，一个结点也是指向了两个结点，这是不是也是一对多呢？由此观之，数据结构就是结点的不同组合方式而已。

二叉树是指，任意一个结点的子节点最多有两个，具体还分为满二叉树（除了最下层的结点，其余结点的度都为2）、完全二叉树（满二叉树转化而来，留左不留右）等，还具有一些计算上的性质，如计算满二叉树的结点等。二叉树也是树中最容易表达的种类，因此非二叉树、森林等都可以转化为二叉树进行存储。

用链式存储二叉树是因为二叉树某些结点可能为空，如果采用数组存储，可能造成空间的浪费，其实对于满二叉树，完全二叉树而言采用数组存储可能更好。

## 2. 链式二叉树的建立 ##

1. 二叉树的建立

1. 建立结点结构体，每个结点包括一个数据域和左右子结点的指针域

2. 建立节点的左右子结点

3. 对2中建立的子结点再重复第2步，以此类推直到结束

const int MAXSIZE = 200;
    
    template <class T>
    /*typedef struct Node
    {
        T data;
        struct Node* leftChild;
        struct Node* rightChild;
    }*BitTree, BitNode;*/
    struct Node
    {
        T data;
        struct Node<T>* leftChild;
        struct Node<T>* rightChild;
    };
    
    
    template <class T>
    class myBitTree
    {
    public:
        struct Node<T>* pRootNode;
    
        //Node<T>* rootNode;
    
        myBitTree();
        //BitNode* CreateBitTree();
        Node<T>* CreateBitTree();
        void PreOrderTraversal(Node<T>* node);
        void InOrderTraversal(Node<T>* node);
        void PostOrderTraversal(Node<T>* node);
    };
    
    template <class T>
    myBitTree<T>::myBitTree()
    {
        pRootNode = new Node<T>;
        pRootNode = CreateBitTree();
    }
    
    template <class T>
    Node<T>* myBitTree<T>::CreateBitTree()
    {
        T ch;
        cin>>ch;
        Node<T>* pNode = new Node<T>;;//产生新的结点空间
        if ('#' == ch)//录入“#”表示空结点，非空则递归循环产生子结点
        {
            pNode = nullptr;
            cout<<"Haha."<<endl;
        }
        else
        {
            //pNode = new Node<T>;
    
            pNode->data = ch;
            cout<<pNode->data;
            pNode->leftChild = CreateBitTree();
            pNode->rightChild = CreateBitTree();
        }
        return pNode;
    }

2. 二叉树的遍历

二叉树的遍历分为前序中序和后序，所谓的前中后就是根节点的遍历位置（此处的根节点是相对的），具体而言，前序遍历就是指先访问根结点，再访问根节点的左子树，最后访问根节点的右子树，其中访问左右子树的时候，依旧按照“中-左-右”的顺序访问。同理，中序遍历即“左中右”，后序遍历即“左右中”，说起来复杂，实现起来非常简单，代码如下：

template <class T>
    void myBitTree<T>::PreOrderTraversal(Node<T>* node)
    {
        if (node)
        {
            cout<<node->data<<endl;
            //cout<<"1"<<endl;
            //cout<<node->rightChild->data;
            PreOrderTraversal(node->leftChild);
            PreOrderTraversal(node->rightChild);
        }
    }
    
    template <class T>
    void myBitTree<T>::InOrderTraversal(Node<T>* node)
    {
        if (node)
        {
            InOrderTraversal(node->leftChild);
            cout<<node->data<<endl;
            //cout<<"1"<<endl;
            //cout<<node->rightChild->data;
    
            InOrderTraversal(node->rightChild);
        }
    }
    
    template <class T>
    void myBitTree<T>::PostOrderTraversal(Node<T>* node)
    {
        if (node)
        {
            PostOrderTraversal(node->leftChild);
            PostOrderTraversal(node->rightChild);
            cout<<node->data<<" ";
            //cout<<"1"<<endl;
            //cout<<node->rightChild->data;
        }
    }

## 3. 注意的问题 ##

1. 写了这个之后其实发现数据结构并不是很难的东西，稍微熟练一些就好了，毕竟不是让我去想出这些结构，而是去用现成的~

2. 二叉树的建立和遍历都用到了递归