C++通过容器创建二叉树以及遍历（递归非递归：前、中、后、层）————附带详细代码_随笔

C++通过容器创建二叉树以及遍历（递归/非递归：前、中、后、层）————附带详细代码

文章目录

0 背景
1 生成二叉树
- 1.1 二叉树的链式存储结构
- 1.2 二叉树的创建
2 遍历代码
- 2.1 前序遍历
- - 2.1.1 递归
  - 2.2 非递归
- 2.2 中序遍历
- - 2.2.1 递归
  - 2.2.2 非递归
- 2.3 后序遍历
- - 2.3.1 递归
  - 2.3.2 非递归
- 2.4 层序遍历
3 完整的示例代码
4 关联二叉查找树的创建

0 背景

在学习二叉树的遍历时，学习了很多遍历的方式，但是想要验证遍历的代码，奈何很多书籍都没有讲如何创建二叉树，网上也查了很多资料都是需要手动输入一个一个的节点通过递归来创建，不能传一个容器过去，通过容器中的元素来生成二叉树，这样的代码生成树就会很麻烦。

于是通过网上查阅和参考了一些相关资料，自己写了通过层序遍历的方式来生成二叉树，并通过模版的方式，增加了代码的可扩展性。

1 生成二叉树

由于常用的就是int和char类型，所以就特化了这两个类型。

1.1 二叉树的链式存储结构

template 
class BiTNode {
public:
    T data;
    BiTNode* left;
    BiTNode* right;
    BiTNode():data(NULL),left(NULL),right(NULL){};
};

template <>
class BiTNode {
public:
    int data;
    BiTNode* left;
    BiTNode* right;
    BiTNode() : data(0), left(nullptr), right(nullptr) {}
    BiTNode(int x) : data(x), left(nullptr), right(nullptr) {}
    BiTNode(int x, BiTNode *left, BiTNode *right) : data(x), left(left), right(right) {}
};

template <>
class BiTNode {
public:
    char data;
    BiTNode* left;
    BiTNode* right;
    BiTNode() : data(''), left(nullptr), right(nullptr) {}
    BiTNode(char x) : data(x), left(nullptr), right(nullptr) {}
    BiTNode(char x, BiTNode *left, BiTNode *right) : data(x), left(left), right(right) {}
};

1.2 二叉树的创建

使用二级指针，以对传入的树根进行修改。

template 
void createBiTNode(BiTNode** treeNode, dequedataDeq) {//层序遍历建立二叉树
    //特殊处理根结点
    T data;
    data = dataDeq.front();
    dataDeq.pop_front();
    BiTNode * node = new BiTNode();
    *treeNode = node;
    (*treeNode)->data = data;

    deque**> nodeDeq;//用于层序建立树时访问双亲节点
    nodeDeq.push_back(treeNode);

    int index = 2;//用于判定左右孩子（左偶，右奇）
    while (!dataDeq.empty()){//当数据节点非空时，进行建树

        BiTNode** nodeParent = nodeDeq.front();
       nodeDeq.pop_front();

       for(int i = 0; i < 2;i++){
           data = dataDeq.front();
           dataDeq.pop_front();
           if(data == '#'){//适用于char
           //if(data == -1){//适用于int
               if(index%2 == 0) (*nodeParent)->left = nullptr;
               else (*nodeParent)->right = nullptr;
           }else{
               BiTNode * node = new BiTNode();
               node->data = data;
               if(index%2 == 0){
                   (*nodeParent)->left = node;
                   nodeDeq.push_back(&(*nodeParent)->left);
               }else{
                   (*nodeParent)->right = node;
                   nodeDeq.push_back(&(*nodeParent)->right);
               }
           }
           index++;
       }
    }
}


template <>
void createBiTNode(BiTNode** treeNode, dequedataDeq) {//层序遍历建立二叉树
    //特殊处理根结点
    char data;
    data = dataDeq.front();
    dataDeq.pop_front();
    BiTNode * node = new BiTNode();
    *treeNode = node;
    (*treeNode)->data = data;

    deque**> nodeDeq;//用于层序建立树时访问双亲节点
    nodeDeq.push_back(treeNode);

    int index = 2;//用于判定左右孩子（左偶，右奇）
    while (!dataDeq.empty()){//当数据节点非空时，进行建树

        BiTNode** nodeParent = nodeDeq.front();
        nodeDeq.pop_front();

        for(int i = 0; i < 2;i++){
            data = dataDeq.front();
            dataDeq.pop_front();
            if(data == '#'){
                if(index%2 == 0) (*nodeParent)->left = nullptr;
                else (*nodeParent)->right = nullptr;
            }else{
                BiTNode * node = new BiTNode();
                node->data = data;
                if(index%2 == 0){
                    (*nodeParent)->left = node;
                    nodeDeq.push_back(&(*nodeParent)->left);
                }else{
                    (*nodeParent)->right = node;
                    nodeDeq.push_back(&(*nodeParent)->right);
                }
            }
            index++;
        }
    }
}

template <>
void createBiTNode(BiTNode** treeNode, dequedataDeq) {//层序遍历建立二叉树
    //特殊处理根结点
    char data;
    data = dataDeq.front();
    dataDeq.pop_front();
    BiTNode * node = new BiTNode();
    *treeNode = node;
    (*treeNode)->data = data;

    deque**> nodeDeq;//用于层序建立树时访问双亲节点
    nodeDeq.push_back(treeNode);

    int index = 2;//用于判定左右孩子（左偶，右奇）
    while (!dataDeq.empty()){//当数据节点非空时，进行建树

        BiTNode** nodeParent = nodeDeq.front();
        nodeDeq.pop_front();

        for(int i = 0; i < 2;i++){
            data = dataDeq.front();
            dataDeq.pop_front();
            if(data == -1){
                if(index%2 == 0) (*nodeParent)->left = nullptr;
                else (*nodeParent)->right = nullptr;
            }else{
                BiTNode * node = new BiTNode();
                node->data = data;
                if(index%2 == 0){
                    (*nodeParent)->left = node;
                    nodeDeq.push_back(&(*nodeParent)->left);
                }else{
                    (*nodeParent)->right = node;
                    nodeDeq.push_back(&(*nodeParent)->right);
                }
            }
            index++;
        }
    }
}

2 遍历代码 2.1 前序遍历 2.1.1 递归

template 
void preOrder(BiTNode* treeNode){
    if(treeNode){
        cout<data<<" ";
        preOrder(treeNode->left);
        preOrder(treeNode->right);
    }
}

2.2 非递归

使用栈：

template 
void preOrder2(BiTNode* treeNode){
    stack*> s;
    BiTNode* p = treeNode;
    while(p || !s.empty()){
        if(p){
            cout<data<<" ";
            s.push(p);
            p = p->left;
        }else{
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
}

2.2 中序遍历 2.2.1 递归

template 
void inOrder(BiTNode* treeNode){
    if(treeNode){
        inOrder(treeNode->left);
        cout<data<<" ";
        inOrder(treeNode->right);
    }
}

2.2.2 非递归

使用栈：

template 
void inOrder2(BiTNode* treeNode){
    stack*> s;
    BiTNode* p = treeNode;
    while(p || !s.empty()){
        if(p){
            s.push(p);
            p = p->left;
        }else{
            p = s.top();
            cout<data<<" ";
            s.pop();
            p = p->right;
        }
    }
}

2.3 后序遍历 2.3.1 递归

template 
void postOrder(BiTNode* treeNode){
    if(treeNode){
        postOrder(treeNode->left);
        postOrder(treeNode->right);
        cout<data<<" ";
    }
}

2.3.2 非递归

template 
void postOrder2(BiTNode* treeNode){
    stack*> s;
    BiTNode *p = treeNode, *r = nullptr;
    while(p || !s.empty()){
        if(p){
            s.push(p);
            p = p->left;
        }else{
            p = s.top();
            if(p->right && p->right != r){//有右孩子且没有访问过
                p = p->right;
            }else{
                cout<data<<" ";
                s.pop();
                r = p;
                p = nullptr;
            }
        }
    }
}

2.4 层序遍历

template 
void levelOrder(BiTNode* treeNode) {
    queue*> nodeQue;
    BiTNode* p = treeNode;
    nodeQue.push(p);
    while(!nodeQue.empty()){
        p = nodeQue.front();
        nodeQue.pop();
        cout<data<<" ";
        if(p->left) nodeQue.push(p->left);
        if(p->right) nodeQue.push(p->right);
    }
}

3 完整的示例代码

#include 
#include 
#include 
#include 
using namespace std;

template 
class BiTNode {
public:
    T data;
    BiTNode* left;
    BiTNode* right;
    BiTNode():data(NULL),left(NULL),right(NULL){};
};

template <>
class BiTNode {
public:
    int data;
    BiTNode* left;
    BiTNode* right;
    BiTNode() : data(0), left(nullptr), right(nullptr) {}
    BiTNode(int x) : data(x), left(nullptr), right(nullptr) {}
    BiTNode(int x, BiTNode *left, BiTNode *right) : data(x), left(left), right(right) {}
};

template <>
class BiTNode {
public:
    char data;
    BiTNode* left;
    BiTNode* right;
    BiTNode() : data(''), left(nullptr), right(nullptr) {}
    BiTNode(char x) : data(x), left(nullptr), right(nullptr) {}
    BiTNode(char x, BiTNode *left, BiTNode *right) : data(x), left(left), right(right) {}
};


template 
void createBiTNode(BiTNode** treeNode, dequedataDeq) {//层序遍历建立二叉树
    //特殊处理根结点
    T data;
    data = dataDeq.front();
    dataDeq.pop_front();
    BiTNode * node = new BiTNode();
    *treeNode = node;
    (*treeNode)->data = data;

    deque**> nodeDeq;//用于层序建立树时访问双亲节点
    nodeDeq.push_back(treeNode);

    int index = 2;//用于判定左右孩子（左偶，右奇）
    while (!dataDeq.empty()){//当数据节点非空时，进行建树

        BiTNode** nodeParent = nodeDeq.front();
       nodeDeq.pop_front();

       for(int i = 0; i < 2;i++){
           data = dataDeq.front();
           dataDeq.pop_front();
           if(data == '#'){//适用于char
           //if(data == -1){//适用于int
               if(index%2 == 0) (*nodeParent)->left = nullptr;
               else (*nodeParent)->right = nullptr;
           }else{
               BiTNode * node = new BiTNode();
               node->data = data;
               if(index%2 == 0){
                   (*nodeParent)->left = node;
                   nodeDeq.push_back(&(*nodeParent)->left);
               }else{
                   (*nodeParent)->right = node;
                   nodeDeq.push_back(&(*nodeParent)->right);
               }
           }
           index++;
       }
    }
}


template <>
void createBiTNode(BiTNode** treeNode, dequedataDeq) {//层序遍历建立二叉树
    //特殊处理根结点
    char data;
    data = dataDeq.front();
    dataDeq.pop_front();
    BiTNode * node = new BiTNode();
    *treeNode = node;
    (*treeNode)->data = data;

    deque**> nodeDeq;//用于层序建立树时访问双亲节点
    nodeDeq.push_back(treeNode);

    int index = 2;//用于判定左右孩子（左偶，右奇）
    while (!dataDeq.empty()){//当数据节点非空时，进行建树

        BiTNode** nodeParent = nodeDeq.front();
        nodeDeq.pop_front();

        for(int i = 0; i < 2;i++){
            data = dataDeq.front();
            dataDeq.pop_front();
            if(data == '#'){
                if(index%2 == 0) (*nodeParent)->left = nullptr;
                else (*nodeParent)->right = nullptr;
            }else{
                BiTNode * node = new BiTNode();
                node->data = data;
                if(index%2 == 0){
                    (*nodeParent)->left = node;
                    nodeDeq.push_back(&(*nodeParent)->left);
                }else{
                    (*nodeParent)->right = node;
                    nodeDeq.push_back(&(*nodeParent)->right);
                }
            }
            index++;
        }
    }
}

template <>
void createBiTNode(BiTNode** treeNode, dequedataDeq) {//层序遍历建立二叉树
    //特殊处理根结点
    char data;
    data = dataDeq.front();
    dataDeq.pop_front();
    BiTNode * node = new BiTNode();
    *treeNode = node;
    (*treeNode)->data = data;

    deque**> nodeDeq;//用于层序建立树时访问双亲节点
    nodeDeq.push_back(treeNode);

    int index = 2;//用于判定左右孩子（左偶，右奇）
    while (!dataDeq.empty()){//当数据节点非空时，进行建树

        BiTNode** nodeParent = nodeDeq.front();
        nodeDeq.pop_front();

        for(int i = 0; i < 2;i++){
            data = dataDeq.front();
            dataDeq.pop_front();
            if(data == -1){
                if(index%2 == 0) (*nodeParent)->left = nullptr;
                else (*nodeParent)->right = nullptr;
            }else{
                BiTNode * node = new BiTNode();
                node->data = data;
                if(index%2 == 0){
                    (*nodeParent)->left = node;
                    nodeDeq.push_back(&(*nodeParent)->left);
                }else{
                    (*nodeParent)->right = node;
                    nodeDeq.push_back(&(*nodeParent)->right);
                }
            }
            index++;
        }
    }
}

template 
void inOrder(BiTNode* treeNode){
    if(treeNode){
        inOrder(treeNode->left);
        cout<data<<" ";
        inOrder(treeNode->right);
    }
}

template 
void preOrder(BiTNode* treeNode){
    if(treeNode){
        cout<data<<" ";
        preOrder(treeNode->left);
        preOrder(treeNode->right);
    }
}

template 
void postOrder(BiTNode* treeNode){
    if(treeNode){
        postOrder(treeNode->left);
        postOrder(treeNode->right);
        cout<data<<" ";
    }
}

template 
void preOrder2(BiTNode* treeNode){
    stack*> s;
    BiTNode* p = treeNode;
    while(p || !s.empty()){
        if(p){
            cout<data<<" ";
            s.push(p);
            p = p->left;
        }else{
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
}

template 
void inOrder2(BiTNode* treeNode){
    stack*> s;
    BiTNode* p = treeNode;
    while(p || !s.empty()){
        if(p){
            s.push(p);
            p = p->left;
        }else{
            p = s.top();
            cout<data<<" ";
            s.pop();
            p = p->right;
        }
    }
}

template 
void postOrder2(BiTNode* treeNode){
    stack*> s;
    BiTNode *p = treeNode, *r = nullptr;
    while(p || !s.empty()){
        if(p){
            s.push(p);
            p = p->left;
        }else{
            p = s.top();
            if(p->right && p->right != r){//有右孩子且没有访问过
                p = p->right;
            }else{
                cout<data<<" ";
                s.pop();
                r = p;
                p = nullptr;
            }
        }
    }
}

template 
void levelOrder(BiTNode* treeNode) {
    queue*> nodeQue;
    BiTNode* p = treeNode;
    nodeQue.push(p);
    while(!nodeQue.empty()){
        p = nodeQue.front();
        nodeQue.pop();
        cout<data<<" ";
        if(p->left) nodeQue.push(p->left);
        if(p->right) nodeQue.push(p->right);
    }
}

int main() {
    //使用字符串
    deque treeVec{'a', 'b', 'c', 'd', 'e', '#', '#'};
    BiTNode* tree = new BiTNode();
    createBiTNode(&tree, treeVec);
    //使用数值
//    deque treeVec{1, 2, 3, 4, 5, -1, -1};
//    BiTNode* tree = new BiTNode();
//    createBiTNode(&tree, treeVec);
    //遍历
    levelOrder(tree);
    cout< 
4 关联二叉查找树的创建 
博文链接					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5699590.html

C++通过容器创建二叉树以及遍历（递归非递归：前、中、后、层）————附带详细代码

发表评论

评论列表（0条）