Data-Structure10

Before：接Data Structure 9，继续二叉链表…

PS: Today is a happy day for Jane,maybe you can guess why?

Data Structure 10 二叉链表

二叉链表类定义

首先，回顾一下《C++程序设计思想与方法》，友元函数（friend function）是一个特殊的函数，它可以访问类的私有（private）和保护（protected）成员，即使它不是该类的成员函数。

下面给出定义：

template<class T>
class binaryTree:public bTree<T>{
    friend void printTree(const binaryTree<T> &t,T flag);
private:
    struct Node{
        Node *left,right;
        T data;

        Node():left(nullptr),right(nullptr){}

        Node(T data,Node *l = nullptr,Node *r == nullptr){
            left = l;
            right = r;
            data = Data;
        }

        ~Node(){}
    };

    Node *root; // 二叉树根结点
public:
    binaryTree():root(nullptr){}
    binaryTree(T x):root(new Node(x)){}
    ~binaryTree();

    void clear();
    bool isEmpty() const;
    T Root(T flag) const;
    T lChild(T x,T flag) const;
    T rChild(T x,T flag) const;
    void delLeft(T x);
    void delRight(T x);
    void preOrder() const;
    void midOrder() const;
    void postOrder() const;
    void levelOrder() const;
    void createTree(T flag);
    T parent(T x,T flag) const{}

private:
    Node *find(T x,Node *t) const;
    void clear(Node *&t);
    void preOrder(Node *t) const;
    void midOrder(Node *t) const;
    void postOrder(Node *t) const;
};

二叉链表类的运算实现

首先是isEmpty、Root、clear和析构函数

template<class T>
bool binaryTree<T>::isEmpty() const{
    return root == nullptr;
}

template<class T>
T binaryTree<T>::Root(T flag) const{
    if(root == nullptr){
        return flag;
    }else{
        return root->data;
    }
}

template<class T>
void binaryTree<T>::clear(binaryTree<T>::Node *&t){
    if(t == nullptr){
        return;
    }
    clear(t->left);
    clear(t->right);
    delete t;
    t = nullptr;
}

template<class T>
binaryTree<T>::~binaryTree(){
    clear(root);
}

接着是遍历函数的实现

template<class T>
void binaryTree<T>::preOrder(binaryTree<T>::Node *t) const{
    if(t == nullptr){
        return;
    }
    cout << t->data;
    preOrder(t->left);
    preOrder(t->right);
}

template<class T>
void binaryTree<T>::preOrder() const{
    preOrder(root);
}

template<class T>
void binaryTree<T>::midOrder(binaryTree<T>::Node *t) const{
    if(t == nullptr){
        return;
    }
    midOrder(t->left);
    cout << t->data;
    midOrder(t->right);
}

template<class T>
void binaryTree<T>::midOrder() const{
    midOrder(root);
}

template<class T>
void binaryTree<T>::postOrder(binaryTree<T>::Node *t) const{
    if(t == nullptr){
        return;
    }
    postOrder(t->left);
    postOrder(t->right);
    cout << t->data;
}

template<class T>
void binaryTree<T>::postOrder() const{
    postOrder(root);
}

template<class T>
void binaryTree<T>::levelOrder() const{
    // 这里采用链接队列实现
    // 类似于广度优先搜索（BFS）
    linkQueue<Node *> que;
    Node *tmp;
    que.enQueue(root);

    while(!que.isEmpty()){
        tmp = que.deQueue;
        cout << tmp -> data;
        if(tmp -> left){
            que.enQueue(tmp -> left);
        }
        if(tmp -> right){
            que.enQueue(tmp -> right);
        }
    }
}

接着是find、lChild、rChild、delLeft、delRight函数实现

template<class T>
Node *binaryTree<T>::find(T x,binaryTree<T>::Node *t) const{
    Node *tmp;
    if(t == nullptr){
        return nullptr;
    }
    if(t->data == x){
        return t;
    }
    if(tmp = find(x,t->left)){
        return tmp;
    }else if(tmp = find(x,t->right)){
        return tmp;
    }else{
        return nullptr;
    }
}

template<class T>
T binaryTree<T>::lChild(T x,T flag) const{
    Node *tmp = find(x,root);
    if(tmp == nullptr){
        return flag;
    }
    if(tmp -> left == nullptr){
        return flag;
    }
    return tmp -> left -> data;
}

template<class T>
T binaryTree<T>::rChild(T x,T flag) const{
    Node *tmp = find(x,root);
    if(tmp == nullptr){
        return flag;
    }
    if(tmp -> right == nullptr){
        return flag;
    }
    return tmp -> right -> data;
}

template<class T>
void binaryTree<T>::delLeft(T x){
    Node *tmp = find(x,root);
    if(tmp == nullptr){
        return;
    }
    if(tmp -> left == nullptr){
        return;
    }
    clear(tmp -> left);
}

template<class T>
void binaryTree<T>::delRight(T x){
    Node *tmp = find(x,root);
    if(tmp == nullptr){
        return;
    }
    if(tmp -> right == nullptr){
        return;
    }
    clear(tmp -> right);
}

最后是createTree建树操作

template<class T>
void binaryTree<T>::createTree(T flag){
    linkQueue<Node *>que;
    Node *tmp;
    T x,lData,rData;
    cin >> x;
    que.enQueue(new Node(x));
    while(!que.isEmpty()){
        tmp = que.deQueue();
        cin >> lDta >> rData;
        if(lData != flag){
            que.enQueue(tmp -> left = new Node(lData));
        }
        if(rData != flag){
            que.enQueue(tmp -> right = new Node(rData));
        }
    }
}

附上友元函数打印树

void printTree(const binaryTree<T> &t,T flag){
    linkQueue<T>que;
    que.enQueue(t -> root -> data);
    
    while(!que.isEmpty()){
        T tmp = que.deQueue();
        T l = lChild(tmp,flag);
        T r = rChild(tmp,flag);
        cout << tmp << l << r << endl;
        if(l != flag){
            que.enQueue(l);
        }
        if(r != flag){
            que.enQueue(r);
        }
    }
}