数据结构--简单二叉树(无序)

本次来简单总结下简单二叉树(无序)，前面欠的债有点多，最近在疯狂追赶课程进度，简单记录下自己对简单二叉树的一些理解

binary tree

the main structure

const int Max = 100;

template <class DataType>
struct BiNode {
    DataType data;
    BiNode *leftChild, *rightChild;    
};

template <class DataType>
class BiTree {
    public:
     BiTree() { root = Create(); }
     ~BiTree() { Release(root); }
     void PreOrder() { PreOrder(root); }
     void InOrder() { InOrder(root); }
     void LevelOrder();
     int leafNum(BiNode*);
     BiNode* getRoot() { return root; }
    
    private:
     BiNode* root;
     BiNode* Create();
     void Release(BiNode* bt);
     void PreOrder(BiNode* bt);
     void InOrder(BiNode* bt);
     void PostOrder(BiNode* bt);
};

Create()

template <class DataType>
BiTree::BiTree() {
    BiNode* bt;
    DataType ch;
    cout << "enter a binary node: ";
    cin >> ch;
    if (ch == '#') {
        return NULL;
    } else {
        bt = new BiNode;
        bt->data = ch;
        bt->leftChild = Create();
        bt->rightchild = Create();
        // 不断套娃递归
    }
}

Release()

template <class DataType>
BiTree::Release(BiNode* bt) {
    if (bt == NULL) {
        return;
    } else {
        Release(bt->leftChild);
        Release(bt->rightChild);
        delete bt;
    }
}

PreOrder

template <class DataType>
void BiTree::PreOrder(BiNode* bt) {
    if (bt == NULL) {
        return;
    } else {
        cout << bt->data << ' ';
        PreOrder(bt->leftChild);
        PreOrder(bt->rightChild);
    }
}

InOrder()

template <class DataType>
void BiTree::InOrder(BiNode* bt) {
    if (bt == NULL) {
        return;
    } else {
        InOrder(bt->leftChild);
        cout << bt->data << ' ';
        InOrder(bt->rightChild);
    }
}

PostOrder()

template <class DataType>
void BiTree::PostOrder(BiNode* bt) {
    if (bt == NULL) {
        return;
    } else {
        PostOrder(bt->leftChild);
        PostOrder(bt->rightChild);
        cout << bt->data << ' ';
    }
}

LevelOrder()

template <class DataType>
void BiTree::LevelOrder() {
    BiNode *queue[Max], *ptr = NULL;
    int front = -1, rear = -1;
    if (root == NULL) 
        return;    
    queue[++rear] = root; // 根节点入队
    while (front != rear) {
        ptr = queue[++front]; // 把根节点赋给临时指针ptr
        cout << ptr->data << ' '; // 输出当前结点的内容       
        if (ptr->leftChild != NULL)
            queue[++rear] = ptr->leftChild;
        if (ptr->rightChild != NULL)
            queue[++rear] = ptr->rightChild;
        // 这里依次遍历左右左右孩子节点并添加入列
    }
}

leafNum()

template <class DataType>
int BiTree::leafNum(BiNode* bt){
    if (bt == NULL)
        return 0;
    if (bt->leftChild == NULL && bt->rightChild == NULL) 
        return 1;
    int left = leafNum(bt->leftChild);
    int right = leafNum(bt->rightChild);
    return left + right;
}

Complete code

#include <bits/stdc++.h>
using namespace std;
const int Max = 100;

template <class DataType>
struct BiNode {
    DataType data;
    BiNode *leftChild, *rightChild;
};

template <class DataType>
class BiTree {
    public:
     BiTree() { root = Create(); }
     ~BiTree() {Release(root); }
     void PreOrder() { PreOrder(root); }
     void InOrder() { InOrder(root); }
     void PostOrder() { PostOrder(root); }
     void LevelOrder();
     int leafNum(BiNode*);
     BiNode* getRoot() { return root; }
    
    private:
     BiNode* root;
     BiNode* Create();
     void Release(BiNode*);
     void PreOrder(BiNode*);
     void InOrder(BiNode*);
     void PostOrder(BiNode*);
};

template <class DataType>
BiNode* BiTree::Create() {
    BiNode* bt;
    DataType ch;
    cout << "enter a node data: ";
    cin >> ch;
    if (ch != '#') {
        bt->data = ch;
        bt->leftChild = Create();
        bt->rightChild = Create();
        return bt;
    }
}

template <class DataType>
void BiTree::Release(BiNode* bt) {
    if (bt == NULL) {
        return;
    } else {
        Release(bt->leftChild);
        Release(bt->rightChild);
        delete bt;
    }
}

template <class DataType>
void BiTree::PreOrder(BiNode* bt) {
    if (bt == NULL) {
        return;
    } else {
        cout << bt->data << ' ';
        PreOrder(bt->leftChild);
        PreOrder(bt->rightChild);
    }
}

template <class DataType>
void BiTree::InOrder(BiNode* bt) {
    if (bt == NULL) {
        return;
    } else {
        InOrder(bt->leftChild);
        cout << bt->data << ' ';
        InOrder(bt->rightChild);
    }
}

template <class DataType>
void BiTree::PostOrder(BiNode* bt) {
    if (bt == NULL) {
        return;
    } else {
        PostOrder(bt->leftChild);
        PostOrder(bt->rightChild);
        cout << bt->data << ' ';
    }
}

template <class DataType>
void BiTree::LevelOrder() {
    BiNode* queue[Max], ptr = NULL;
    int front = -1, rear = -1;
    if (root == NULL)
        return;
	queue[++rear] = root;
    while (front != rear) {
        ptr = queue[++front];
        cout << ptr->data << ' ';
        if (ptr->leftChild != NULL)
            queue[++rear] = ptr->leftChild;
        if (ptr->rightChild != NULL)
            queue[++rear] = ptr->rightChild;
    }
}

template <class DataType>
int BiTree::leafNum(BiNode* bt) {
    if (bt == NULL)
        return 0;
    if (bt->leftChild == NULL && bt->rightChild == NULL)
        return 1;
    int left = leafNum(bt->leftChild);
    int right = leafNum(bt->rightChild);
    return left + right;    
}

int main() {
    BiTree tree;
    cout << "---PreOrder---\n";
    tree.PreOrder();
    cout << endl;
    cout << "---InOrder---\n";
    tree.InOrder();
    cout << endl;
    cout << "---PostOrder---\n";
    tree.PostOrder();
    cout << endl;
    cout << "---LevelOrder---\n";
    tree.LevelOrder();
    cout << endl;
    cout << "the num of the leaves: ";
    cout << tree.leafNum(tree.getRoot());
}