C++ classic example: construction of pre-order binary tree-C#.Net Tutorial-php.cn

C++ classic example: construction of pre-order binary tree

little bottle

Release： 2019-04-20 17:31:36

forward

3301 people have browsed it

The editor of this article will take you to review the classic C method of building a pre-order binary tree. Friends who are interested can review it together!

The construction problem of a binary tree must first be solved before subsequent traversal can be considered. Here is a post on building a binary tree through preorder, which also includes four binary tree traversal methods (preorder, inorder, postorder, layer by layer)

First, define the BinaryTreeNode class

#include <iostream>
#include <string>
#include <queue>
using namespace std;

template<typename T >class BinaryTree;
template <typename T> class BinaryTreeNode {
public:
    friend class BinaryTree<T>;
    BinaryTreeNode() {
        data = NULL;
        lChild = rChild = NULL;
    }
    BinaryTreeNode(T newdata) {
        this->data = newdata;
        lChild = rChild = NULL;
    }
    T getData() {
        return data;
    }
    BinaryTreeNode<T> * getLeftNode() {
        return lChild;
    }
    BinaryTreeNode<T> * getRightNode() {
        return rChild;
    }
    T data;
    BinaryTreeNode<T>* lChild;
    BinaryTreeNode<T>* rChild;
private:

};

Copy after login

View Code

Second, Define BinaryTree class

template <typename T> class BinaryTree {
public:
    BinaryTreeNode<T> *root;
    char* p;
    BinaryTree() { root = NULL; }
    BinaryTree(T data) {
        root = new BinaryTreeNode<T>(data);
        root->lChild = NULL;
        root->rChild = NULL;
    }
    ~BinaryTree() {
        delete root;
    }

    //构建二叉树并返回
    BinaryTreeNode<T>* CreateTree() {
        BinaryTreeNode<int>* bt = NULL;
        char t;
        cin >> t;
        if (t == &#39;#&#39;)
        {
            return NULL;
        }
        else {
            int num = t - &#39;0&#39;;
            bt = new BinaryTreeNode<T>(num);
            bt->lChild = CreateTree();
            bt->rChild = CreateTree();
        }
        return bt;
    }

    //先序构建二叉树
    BinaryTreeNode<T>* PreCreateTree() {
        BinaryTreeNode<int>* bt = NULL;
        if (this->root == NULL)
        {
            cout << "请输入根节点（#代表空树）:";
        }
        else {
            cout << "请输入节点（#代表空树）:";
        }
        char t;
        cin >> t;
        if (t == &#39;#&#39;)
        {
            return NULL;
        }
        else {
            int num = t - &#39;0&#39;;
            bt = new BinaryTreeNode<T>(num);
            if (this->root == NULL)
            {
                this->root = bt;
            }
            cout << bt->data << "的左孩子";
            bt->lChild = PreCreateTree();

            cout << bt->data << "的右边孩子";
            bt->rChild = PreCreateTree();
        }
        return bt;
    }   

    void preOderTraversal(BinaryTreeNode<T> *bt);  //先序遍历
    void inOrderTraversal(BinaryTreeNode<T> *bt);  //中序遍历
    void postOrderTraversal(BinaryTreeNode<T> *bt);//后序遍历
    void levelTraversal(BinaryTreeNode<T> *bt);    //逐层遍历

private:

};

template <typename T>
void BinaryTree<T>::preOderTraversal(BinaryTreeNode<T> *bt) {
    if (bt)
    {
        cout << bt->data;
        BinaryTree<T>::preOderTraversal(bt->getLeftNode());
        BinaryTree<T>::preOderTraversal(bt->getRightNode());
    }
}

template <typename T>
void BinaryTree<T>::inOrderTraversal(BinaryTreeNode<T> *bt) {
    if (bt)
    {
        BinaryTree<T>::inOrderTraversal(bt->getLeftNode());
        cout << bt->data;
        BinaryTree<T>::inOrderTraversal(bt->getRightNode());
    }
}

template <typename T>
void BinaryTree<T>::postOrderTraversal(BinaryTreeNode<T> *bt) {
    if (bt)
    {
        BinaryTree<T>::postOrderTraversal(bt->getLeftNode());
        BinaryTree<T>::postOrderTraversal(bt->getRightNode());
        cout << bt->data;
    }
}

template <typename T>
void BinaryTree<T>::levelTraversal(BinaryTreeNode<T> *bt) {

    queue<BinaryTreeNode<T>*> que;
    que.push(bt);
    while (!que.empty())
    {
        BinaryTreeNode<T>* proot = que.front();
        que.pop();
        cout << proot->data;

        if (proot->lChild != NULL)
        {
            que.push(proot->lChild);//左孩子入队
        }
        if (proot->rChild != NULL)
        {
            que.push(proot->rChild);//右孩子入队
        }
    }
}

Copy after login

View Code

Third, run the main program

#include "pch.h"
#include <iostream>
#include "BinaryTree.h"

int main()
{
    //场景测试2
    BinaryTree<int> btree;
    btree.PreCreateTree();//先序构建二叉树
    cout << "先序遍历:";
    btree.preOderTraversal(btree.root); cout << endl;//先序遍历    
    cout << "中序遍历:";
    btree.inOrderTraversal(btree.root); cout << endl;//中序遍历
    cout << "后序遍历:";
    btree.postOrderTraversal(btree.root); cout << endl;//后序遍历
    cout << "逐层序遍历:";
    btree.levelTraversal(btree.root);

}

Copy after login

View Code

Final test run screenshot