c++经典例题之先序二叉树的构建

本篇文章小编将带大家一起回顾经典C++之构建先序二叉树，有兴趣的小伙伴一起来复习一下吧！

二叉树首先要解决构建问题，才能考虑后续的遍历，这里贴出通过先序构建二叉树，同时包含四种二叉树的遍历方法（先序，中序，后序，逐层）

第一、定义BinaryTreeNode 类

#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:};

View Code

第二、定义BinaryTree 类

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 == '#')        {            return NULL;        }        else {            int num = t - '0';            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 == '#')        {            return NULL;        }        else {            int num = t - '0';            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->getR<strong>本文来源gaodai#ma#com搞@@代~&码*网2</strong>ightNode());    }}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);//右孩子入队        }    }}

喜欢 (0)赏

[搞代码]

分享 (0)