数据结构与算法—创建一颗二叉树

用于示例的主函数main.cpp

#include <iostream>
#include <string>
#include "tree.h"

using std::string;
using std::stack;

int main()
{
    BiTree<string> strBiTree;

    string strArr[] = 
    {
                          "0",
                "1",                  "2", 
           "3",      "4",       "5",        "6", 
        "7", "8", "9", "10", "11", "12", "13", "14"
    };

    int size = sizeof(strArr)/sizeof(strArr[0]);
	//数组strArr用于待生成二叉树
	//0为数组元素索引的初始值
	//size为数组元素个数
    strBiTree.creatBiTree(strArr, 0, size);
    
    return(0);
}

包含生成树的头文件tree.h

#ifndef __TREE_H__
#define __TREE_H__
#include <queue>

using std::queue;

template <typename T>
class BTNode{
public:
    T el;  //节点的值
    BTNode<T> *left, *right;  //左和右孩子节点
    BTNode(){
        left = right = NULL;
    }
    BTNode(const T& e, BTNode<T> *l = NULL, BTNode<T> *r = NULL){
        el = e; left = l; right = r;
    }
};

template <typename T>
class BiTree{
protected:
    BiTree<T> *root;
public: 
    BiTree(){
        root = NULL;
    }
    ~BiTree(){
    }
    BTNode<T>* creatBiTree(T* arr, int index, 
                           int arrSize);
};

/***************************************************************
* Description : 创建一颗二叉树，使用递归法
*               递归停止条件: 数组元素的索引值不超过数组元素个数
*               递归函数个数：2个,分别进行左树和右树的递归
* Input : 用于创建二叉树的数组，数组索引，数组元素个数
* Output: 返回当前创建的头结点的地址，作为上一节点的左或右孩子
***************************************************************/
template <typename T>
BTNode<T>* BiTree<T>::creatBiTree(T* arr, int index, int arrSize){
    BTNode<T>* root = NULL;
    if(index < arrSize){
        root = new BTNode<T>(arr[index]);
        std::cout << "第 " << index << " 个元素：" \
            << root->el << '\n';

        index++;
        root->left = creatBiTree(arr, (2*index-1), arrSize);
        root->right= creatBiTree(arr, (2*index), arrSize);
    }
    return(root);
}
#endif

输出

备注

这里用于示例的数组strArr对元素的个数右要求，就是说应当输入完全二叉树，若数组元素不构成完全二叉树，则可以自己对代码进行修改。