使用链表实现二叉树

柔光的暖阳◎ 2022-05-27 07:37 198阅读 0赞

Node.h

#pragma once
    
    class Node { 
    public:
        int index;
        int data;
        Node *pLChild;
        Node *pRChild;
        Node *pParent;
    
        Node(int index,int data);
        ~Node();
        void deleteNode();
        Node *search(int index);
        void preTraversal(); //前序遍历
        void inTraversal(); //中序遍历
        void postTraversal(); //后序遍历
    
    };

Node.cpp

#include "Node.h"
    #include <iostream>
    using namespace std;
    
    Node::Node(int index, int data) {
        this->data = data;
        this->index = index;
    }
    
    Node::~Node() {
    
    }
    
    void Node::deleteNode() {
    
        if (this->pLChild != NULL) {
            pLChild->deleteNode();
        }
    
        if (this->pRChild != NULL) {
            pRChild->deleteNode();
        }
    
        if (this->pParent->pLChild == this) {
            this->pParent->pLChild = NULL;
        }
    
        if (this->pParent->pRChild == this) {
            this->pParent->pRChild = NULL;
        }
        delete this;
    
    }
    
    Node * Node::search(int index) {
        if (this->index == index) return this;
        if (this->pLChild != NULL && this->pLChild->index == index) return this->pLChild;
        if (this->pRChild != NULL && this->pRChild->index == index) return this->pRChild;
        return NULL;
    }
    
    void Node::preTraversal() {
        cout << data << endl;
        if (this->pLChild != NULL) {
            this->pLChild->preTraversal();
        }
        if (this->pRChild != NULL) {
            this->pRChild->preTraversal();
        }
    }
    void Node::inTraversal() {
    
        if (this->pLChild != NULL) {
            this->pLChild->inTraversal();
        }
        cout << data << endl;
        if (this->pRChild != NULL) {
            this->pRChild->inTraversal();
        }
    }
    void Node::postTraversal() {
        if (this->pLChild != NULL) {
            this->pLChild->postTraversal();
        }
        if (this->pRChild != NULL) {
            this->pRChild->postTraversal();
        }
        cout << data << endl;
    }

Tree.h

#pragma once
    #include "Node.h"
    class Tree {
    private:
        Node *m_pRoot;
        int m_iSize;
    public:
        Tree(int size, Node *pRoot);
        ~Tree();
        Node *search(int index);
        bool deleteNode(int index);
        bool addNode(int index,int direction,Node *pNode);
        void preTraversal(); //前序遍历
        void inTraversal(); //中序遍历
        void postTraversal(); //后序遍历
    
    };

Tree.cpp

#include "Tree.h"
    #include <iostream>
    
    Tree::Tree(int size, Node *pRoot) {
        this->m_iSize = size;
        this->m_pRoot = pRoot;
        m_pRoot->pLChild = NULL;
        m_pRoot->pRChild = NULL;
        m_pRoot->pParent = NULL;
    }
    Tree::~Tree() {
        this->m_pRoot->deleteNode();
    }
    Node *Tree::search(int index) {
        return m_pRoot->search(index);
    }
    bool Tree::deleteNode(int index) {
        Node * temp = search(index);
        if (NULL == temp) return false;
        temp->deleteNode();
    }
    bool Tree::addNode(int index, int direction, Node *pNode) {
        Node * temp = search(index);
        if (NULL == temp) return false;
    
        Node *newNode = new Node(pNode->index,pNode->data);
        newNode->pParent = temp;
        if (direction == 0) {
            temp->pLChild = newNode;
        }
        else {
            temp->pRChild = newNode;
        }
        return true;
    }
    
    void Tree::preTraversal() {
        m_pRoot->preTraversal();
    }
    void Tree::inTraversal() {
        m_pRoot->inTraversal();
    }
    void Tree::postTraversal() {
        m_pRoot->postTraversal();
    }

测试：

#include "Tree.h"
    #include <iostream>
    using namespace std;
    int main() {
    
        Node node1(0, 0);
        Node node2(1, 1);
        Node node3(2, 2);
        Node node4(3, 3);
        Node node5(4, 4);
        Node node6(5, 5);
        Node node7(6, 6);
    
        Tree *ptree = new Tree(10, &node1);
        ptree->addNode(0, 0, &node2);
        ptree->addNode(0, 1, &node3);
        ptree->addNode(1, 0, &node4);
        ptree->addNode(1, 1, &node5);
        ptree->addNode(2, 0, &node6);
        ptree->addNode(2, 1, &node7);
        cout << "前序遍历" << endl;
        ptree->preTraversal();
        cout << "中序遍历" << endl;
        ptree->inTraversal();
        cout << "后序遍历" << endl;
        ptree->postTraversal();
    
        ptree->deleteNode(1);
        cout << "删除1节点前序遍历" << endl;
        ptree->preTraversal();
        system("pause");
        return 0;
    }