树与二叉树——数据结构系列教程(c++版)

#ifndef ARRAYBINARYTREE_H_INCLUDED
#define ARRAYBINARYTREE_H_INCLUDED

#include<queue>
#include<stack>

//************************************************************************************************************************************************************************
//
//      类名：数组二叉树(ArrayBinaryTree)
//
//      概述：一个可复用的数组二叉树，存储结构采用数组实现，支持任意类型数据（模板泛型）。
//
//      说明：默认二叉树的最大容量为100
//
//************************************************************************************************************************************************************************

#define MAXSIZE 100  // 二叉树的最大容量


//========================================================================================================================================================================
//
//                                                                 数组二叉树结构体(ArrayBinaryTree)
//
//========================================================================================================================================================================
template <typename T>
struct ArrayBinaryTree{
    // ------------------------------------------------------------------------------------------------------
    //                                          私有成员
    // 注：私有成员只能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)不能访问调用）
    //------------------------------------------------------------------------------------------------------
    private:

        //---------------声明私有成员变量---------------

        T tree[MAXSIZE];   // 存储二叉树数据，支持任意类型
        int qty;         // 用于跟踪二叉树中的元素数量
        T valNull = T(); // 空节点标识（模板化）

        //---------------声明私有成员函数---------------

        //辅助函数
        int findRootIndex(const T inTree[], int start, int end, const T rootVal); // 查找根节点在中序序列中的索引
        int isInRange(const T val, const T inOrder[], int start, int end); // 检查元素是否在中序的指定范围内（用于筛选层序中的子树节点）
        int filterLevelNodes(const T levelOrder[], int levelLen, const T inOrder[], int inStart, int inEnd, T subLevel[]);// 筛选层序数组中属于指定中序范围的节点，生成子层序数组

    // ------------------------------------------------------------------------------------------------------
    //                                          公共成员
    // 注：公共成员能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)也能访问调用）
    //------------------------------------------------------------------------------------------------------
    public:

        //---------------声明公共成员函数---------------

        // 构造函数：外部通过该结构体定义(实例化)变量(对象)时，自动执行该函数(主要用于初始化成员变量的值)
        ArrayBinaryTree() {
            qty = 0;
            for(int i=0;i < MAXSIZE;i++) { tree[i] = T(); }
        }

        //功能函数
        void buildTreeByPre(const T preTree[], int preStart, int preEnd, const T inTree[], int inStart, int inEnd, int nodeNum, int treeSize);// 根据前序和中序列建立二叉树
        void buildTreeByPost(const T postTree[], int postStart, int postEnd, const T inTree[], int inStart, int inEnd, int nodeNum, int treeSize);// 根据后序和中序列建立二叉树
        void buildTreeByLevel(const T levelTree[], int levelLen, const T inTree[], int inStart, int inEnd, int nodeNum, int treeSize);// 根据层序和中序列建立二叉树
        void deleteTree(int index);// 删除二叉树

        //递归遍历
        void preOrder(int index);// 前序遍历（根 → 左 → 右）
        void inOrder(int index);// 中序遍历（左 → 根 → 右）→ 升序输出
        void postOrder(int index);// 后序遍历（左 → 右 → 根）

        //迭代遍历
        void preOrderIter(int index);// 前序遍历（根 → 左 → 右）
        void inOrderIter(int index);// 中序遍历（左 → 根 → 右）→ 升序输出
        void postOrderIter(int index);// 后序遍历（左 → 右 → 根）
        void levelOrderIter(int index);// 层序遍历（从上到下、从左到右）

        // 析构函数：自动销毁队列，避免内存泄漏
        ~ArrayBinaryTree() {
        }
};

#endif // ARRAYBINARYTREE_H_INCLUDED
                

7.2 ArrayBinaryTree.cpp 程序代码

#include <iostream>
#include "ArrayBinaryTree.h"

//---------------实现私有成员函数---------------


// 查找根节点在中序序列中的索引
template <typename T>
int ArrayBinaryTree<T>::findRootIndex(const T inTree[], int start, int end, const T rootVal) {
    for (int i = start; i <= end; i++) {
        if (inTree[i] == rootVal) {
            return i;
        }
    }
    return -1;  // 未找到（理论上不会出现）
}

// 检查元素是否在中序的指定范围内（用于筛选层序中的子树节点）
template <typename T>
int ArrayBinaryTree<T>::isInRange(const T val, const T inOrder[], int start, int end) {
    for (int i = start; i <= end; i++) {
        if (inOrder[i] == val) {
            return 1;
        }
    }
    return 0;
}

// 筛选层序数组中属于指定中序范围的节点，生成子层序数组
template <typename T>
int ArrayBinaryTree<T>::filterLevelNodes(const T levelOrder[], int levelLen, const T inOrder[], int inStart, int inEnd, T subLevel[]) {
    int idx = 0;
    for (int i = 0; i < levelLen; i++) {
        if (isInRange(levelOrder[i], inOrder, inStart, inEnd)) {
            subLevel[idx++] = levelOrder[i];
        }
    }
    return idx;  // 返回子层序数组的长度
}

//---------------实现公共成员函数---------------

// 根据前序和中序列建立二叉树
// 参数：preTree-前序序列, preStart-前序起始索引, preEnd-前序结束索引
//       inTree-中序序列, inStart-中序起始索引,inEnd-中序结束索引
//       nodeNum-当前节点的编号（从1开始）
template <typename T>
void ArrayBinaryTree<T>::buildTreeByPre(const T preTree[], int preStart, int preEnd, const T inTree[], int inStart, int inEnd, int nodeNum, int treeSize) {
    if (preStart > preEnd || inStart > inEnd) {
        return;
    }

    qty = treeSize;//设置二叉树最大节点数

    T rootVal = preTree[preStart];      // 1. 当前根节点值（前序子序列第一个元素）
    tree[nodeNum] = rootVal;            // 2. 将根节点存入数组对应位置
    int rootIdx = findRootIndex(inTree, inStart, inEnd, rootVal);// 3. 找到根节点在中序序列中的索引
    int leftSize = rootIdx - inStart;   // 4. 计算左子树的节点个数

    // 5. 递归构建左子树
    // 前序左子树范围：[preStart+1, preStart+leftSize]，
    // 中序左子树范围：[inStart, rootIdx-1]
    // 左子节点编号：nodeNum * 2
    buildTreeByPre(preTree, preStart + 1, preStart + leftSize,
                       inTree, inStart, rootIdx - 1,
                       nodeNum * 2, treeSize);

    // 6. 递归构建右子树
    // 前序右子树范围：[preStart+leftSize+1, preEnd]
    // 中序右子树范围：[rootIdx+1, inEnd]
    // 右子节点编号：nodeNum * 2 + 1
    buildTreeByPre(preTree, preStart + leftSize + 1, preEnd,
                       inTree, rootIdx + 1, inEnd,
                       nodeNum * 2 + 1, treeSize);
}

// 根据后序和中序列建立二叉树
// 参数：postTree-后序序列, postStart-后序起始索引, postEnd-后序结束索引
//       inTree-中序序列, inStart-中序起始索引,inEnd-中序结束索引
//       nodeNum-当前节点的编号（从1开始）
template <typename T>
void ArrayBinaryTree<T>::buildTreeByPost(const T postTree[], int postStart, int postEnd, const T inTree[], int inStart, int inEnd, int nodeNum, int treeSize) {
    if (postStart > postEnd || inStart > inEnd) {
        return;
    }
    qty = treeSize;//设置二叉树最大节点数

    T rootVal = postTree[postEnd];      // 1. 后序序列最后一个元素是当前根节点
    tree[nodeNum] = rootVal;            // 2. 将根节点存入数组对应位置
    int rootIdx = findRootIndex(inTree, inStart, inEnd, rootVal);// 3. 找到根节点在中序序列中的索引
    int leftSize = rootIdx - inStart;   // 4. 计算左子树的节点个数

    // 5. 递归构建左子树
    // 后序左子树范围：[postStart, postStart + leftSize - 1]
    // 中序左子树范围：[inStart, rootIdx - 1]
    // 左子节点编号：nodeNum * 2
    buildTreeByPost(postTree, postStart, postStart + leftSize - 1,
                      inTree, inStart, rootIdx - 1,
                      nodeNum * 2, treeSize);

    // 6. 递归构建右子树
    // 后序右子树范围：[postStart + leftSize, postEnd - 1]
    // 中序右子树范围：[rootIdx + 1, inEnd]
    // 右子节点编号：nodeNum * 2 + 1
    buildTreeByPost(postTree, postStart + leftSize, postEnd - 1,
                      inTree, rootIdx + 1, inEnd,
                      nodeNum * 2 + 1, treeSize);

}

// 根据层序和中序列建立二叉树
// 参数：levelTree-层序序列, levelLen-层序长度
//       inTree-中序序列, inStart-中序起始索引,inEnd-中序结束索引
//       nodeNum-当前节点的编号（从1开始）
template <typename T>
void ArrayBinaryTree<T>::buildTreeByLevel(const T levelTree[], int levelLen, const T inTree[], int inStart, int inEnd, int nodeNum, int treeSize) {
    if (inStart > inEnd || levelLen <= 0) {
        return;
    }
    qty = treeSize;//设置二叉树最大节点数

    T rootVal = levelTree[0];      // 1. 层序序列第一个元素是当前根节点
    tree[nodeNum] = rootVal;            // 2. 将根节点存入数组对应位置
    int rootIdx = findRootIndex(inTree, inStart, inEnd, rootVal);// 3. 找到根节点在中序序列中的索引
    int leftSize = rootIdx - inStart;   // 4. 计算左子树的节点个数
    int rightSize = inEnd - rootIdx;    // 5. 计算右子树的节点个数

    // 6. 筛选层序数组中属于左、右子树的节点
    T leftLevel[MAXSIZE], rightLevel[MAXSIZE];
    int leftLevelLen = filterLevelNodes(levelTree, levelLen, inTree, inStart, rootIdx - 1, leftLevel);
    int rightLevelLen = filterLevelNodes(levelTree, levelLen, inTree, rootIdx + 1, inEnd, rightLevel);

    // 4. 递归构建左、右子树
    buildTreeByLevel(leftLevel, leftLevelLen, inTree, inStart, rootIdx - 1, nodeNum * 2, treeSize);
    buildTreeByLevel(rightLevel, rightLevelLen, inTree, rootIdx + 1, inEnd, nodeNum * 2 + 1, treeSize);

}

// 删除二叉树
template <typename T>
void ArrayBinaryTree<T>::deleteTree(int index)
{
    if (index>qty) return;
    tree[index] = T();
    deleteTree(index*2);
    deleteTree(index*2+1);
}

// 前序遍历（根 → 左 → 右）
template <typename T>
void ArrayBinaryTree<T>::preOrder(int index)
{
    if (index >qty) return;
    if(tree[index] != valNull)
        std::cout<<tree[index]<<" ";
    preOrder(index*2);
    preOrder(index*2+1);
}

// 中序遍历（左 → 根 → 右）
template <typename T>
void ArrayBinaryTree<T>::inOrder(int index)
{
    if (index >qty) return;
    inOrder(index*2);
    if(tree[index] != valNull)
        std::cout<<tree[index]<<" ";
    inOrder(index*2+1);
}

// 后序遍历（左 → 右 → 根）
template <typename T>
void ArrayBinaryTree<T>::postOrder(int index)
{
    if (index >qty) return;
    postOrder(index*2);
    postOrder(index*2+1);
    if(tree[index] != valNull)
        std::cout<<tree[index]<<" ";
}

// 迭代---前序遍历（根 → 左 → 右）
template <typename T>
void ArrayBinaryTree<T>::preOrderIter(int index)
{
    std::stack<int> stack1;  // 存储节点编号
    stack1.push(index);        // 根节点入栈

    while (stack1.size() >= 1) {
        int currIndex = stack1.top();stack1.pop();  // 出栈
        if (currIndex >= qty) {
            continue;
        }
        if(tree[currIndex] != valNull)
            std::cout<<tree[currIndex]<<" ";  // 访问根

        // 栈后进先出，先入栈右子树，后入栈左子树
        int rightIndex = currIndex * 2 + 1;
        if (rightIndex <= qty) {
            stack1.push(rightIndex);
        }
        int leftIndex = currIndex * 2;
        if (leftIndex <= qty) {
            stack1.push(leftIndex);
        }
    }
}

// 迭代---中序遍历（左 → 根 → 右）
template <typename T>
void ArrayBinaryTree<T>::inOrderIter(int index)
{
    std::stack<int> stack1;  // 存储节点编号
    int currIndex = index;
    T valNull = T();

    // 迭代终止条件：当前节点为空 且 栈为空
    while (stack1.size()>=1 || (currIndex < qty && tree[currIndex] != valNull)) {
        // 第一步：遍历到最左子节点，路径上的节点下标入栈
        while( currIndex <= qty && tree[currIndex] != valNull ) {
            stack1.push(currIndex);
            currIndex = currIndex * 2;  // 左子节点
        }

        // 第二步：弹出栈顶节点（最左节点）
        currIndex = stack1.top();stack1.pop();
        std::cout<<tree[currIndex]<<" ";

        // 第三步：转向右子节点
        currIndex = currIndex * 2 + 1;
    }
}

// 迭代---后序遍历（左 → 右 → 根）
template <typename T>
void ArrayBinaryTree<T>::postOrderIter(int index)
{
    std::stack<int> stack1, stack2;
    stack1.push(index);

    // 栈1：根→右→左；栈2：存储逆序结果
    while (stack1.size() >= 1) {
        int currIndex = stack1.top(); stack1.pop();
        if (currIndex > qty) {
            continue;
        }
        stack2.push(currIndex);

        // 先入栈左子树，后入栈右子树（栈1出栈顺序相反）
        int leftIndex = currIndex * 2;
        if (leftIndex <= qty) {
            stack1.push(leftIndex);
        }
        int rightIndex = currIndex * 2 + 1;
        if (rightIndex <= qty) {
            stack1.push(rightIndex);
        }
    }

    // 输出栈2（后序遍历结果）
    while(stack2.size() >= 1) {
        int currIndex = stack2.top(); stack2.pop();
        if(tree[currIndex] != valNull)
            std::cout<<tree[currIndex]<<" ";
    }
}

// 迭代---层序遍历（根 → 左 → 右）
template <typename T>
void ArrayBinaryTree<T>::levelOrderIter(int index)
{
    if (index <= 0) return;

    std::queue<int> queues;
    queues.push(index); // 根节点入队

    while (!queues.empty()) {
        int curr = queues.front(); // 获取队头节点
        queues.pop();// 出队头节点
        if(tree[curr] != valNull)
            std::cout<<tree[curr]<<" "; // 输出当前节点值

        // 左子节点入队（先左后右）
        if (curr <= qty) {
            queues.push(curr*2);
        }
        // 右子节点入队
        if (curr <= qty) {
            queues.push(curr*2+1);
        }
    }
}

// 显式实例化常用类型（避免链接错误，可选）
template class ArrayBinaryTree<int>;
template class ArrayBinaryTree<float>;
template class ArrayBinaryTree<std::string>;

7.3 main.cpp 测试代码

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

int main() {
    ArrayBinaryTree<char> tree1;
    ArrayBinaryTree<char> tree2;
    ArrayBinaryTree<char> tree3;

    // 1. 根据前序和中序建立二叉树
    printf("== 1.建立二叉树（根据前序和中序） ==\n");
    printf("          A \n");
    printf("         / \\ \n");
    printf("        B   C \n");
    printf("       / \\ / \\ \n");
    printf("      D  E F    \n");
    printf("        / /    \n");
    printf("       G H    \n");
    char preTree1[] = {'A', 'B', 'D', 'E', 'G', 'C', 'F', 'H'};// 前序序列
    char inTree1[] =  {'D', 'B', 'G', 'E', 'A', 'C', 'H', 'F'};// 中序序列
    int n1 = sizeof(preTree1) / sizeof(preTree1[0]); // 计算元素个数
    int k1 = floor(log2(n1)) + 1;// 计算二叉树深度
    int treeSize1 = pow(2, k1) - 1;// 计算二叉树最大节点数
    tree1.buildTreeByPre(preTree1, 0, n1-1, inTree1, 0, n1-1, 1, treeSize1); //建立二叉树
    printf("\n===== 递归遍历测试 =====\n");
    printf("前序遍历："); tree1.preOrder(1); printf("\n");
    printf("中序遍历："); tree1.inOrder(1); printf("\n");
    printf("后序遍历："); tree1.postOrder(1); printf("\n");
    printf("===== 迭代遍历测试 =====\n");
    printf("前序遍历："); tree1.preOrderIter(1); printf("\n");
    printf("中序遍历："); tree1.inOrderIter(1); printf("\n");
    printf("后序遍历："); tree1.postOrderIter(1); printf("\n");
    printf("层序遍历："); tree1.levelOrderIter(1); printf("\n");

    // 2. 根据后序和中序建立二叉树
    printf("\n== 2.建立二叉树（根据后序和中序）==\n");
    printf("          A \n");
    printf("         / \\ \n");
    printf("        B   C \n");
    printf("         \\ / \\ \n");
    printf("         D E  F\n");
    printf("          \\   / \n");
    printf("           G  H \n");
    char postTree2[] = {'G', 'D', 'B', 'E', 'H', 'F', 'C', 'A'};// 后序序列
    char inTree2[] =   {'D', 'G', 'B', 'A', 'E', 'C', 'H', 'F'};// 中序序列
    int n2 = sizeof(postTree2) / sizeof(postTree2[0]); // 计算元素个数
    int k2 = floor(log2(n2)) + 1;// 计算二叉树深度
    int treeSize2 = pow(2, k2) - 1;// 计算二叉树最大节点数
    tree2.buildTreeByPost(postTree2, 0, n2-1, inTree2, 0, n2-1, 1, treeSize2);//建立二叉树
    printf("===== 递归遍历测试 =====\n");
    printf("前序遍历："); tree2.preOrder(1); printf("\n");
    printf("中序遍历："); tree2.inOrder(1); printf("\n");
    printf("后序遍历："); tree2.postOrder(1); printf("\n");
    printf("===== 迭代遍历测试 =====\n");
    printf("前序遍历："); tree2.preOrderIter(1); printf("\n");
    printf("中序遍历："); tree2.inOrderIter(1); printf("\n");
    printf("后序遍历："); tree2.postOrderIter(1); printf("\n");
    printf("层序遍历："); tree2.levelOrderIter(1); printf("\n");

    // 3. 根据层序和中序建立二叉树
    printf("\n== 3.建立二叉树（根据层序和中序）==\n");
    printf("          A \n");
    printf("         / \\ \n");
    printf("        B   C \n");
    printf("         \\ / \\ \n");
    printf("         D E  F\n");
    printf("          \\   / \n");
    printf("           G  H \n");
    char levelTree3[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};// 层序序列
    char inTree3[] =   {'D', 'G', 'B', 'A', 'E', 'C', 'H', 'F'};// 中序序列
    int n3 = sizeof(levelTree3) / sizeof(levelTree3[0]); // 计算元素个数
    int k3 = floor(log2(n3)) + 1;// 计算二叉树深度
    int treeSize3 = pow(2, k3) - 1;// 计算二叉树最大节点数
    tree3.buildTreeByLevel(levelTree3, n3, inTree3, 0, n3-1, 1, treeSize3);//建立二叉树
    printf("===== 递归遍历测试 =====\n");
    printf("前序遍历："); tree3.preOrder(1); printf("\n");
    printf("中序遍历："); tree3.inOrder(1); printf("\n");
    printf("后序遍历："); tree3.postOrder(1); printf("\n");
    printf("===== 迭代遍历测试 =====\n");
    printf("前序遍历："); tree3.preOrderIter(1); printf("\n");
    printf("中序遍历："); tree3.inOrderIter(1); printf("\n");
    printf("后序遍历："); tree3.postOrderIter(1); printf("\n");
    printf("层序遍历："); tree3.levelOrderIter(1); printf("\n");
    
    return 0;
}

八、注意事项

九、总结

• 树是“一对多”的层级结构，核心术语包括节点的度、层次、树的深度等；
• 二叉树每个节点度不超过2，有5种基本形态，核心性质n₀ = n₂ + 1是重点；
• 满二叉树是特殊的完全二叉树，完全二叉树适合顺序存储，一般二叉树适合链式存储；
• 二叉树遍历是核心操作，深度优先（前、中、后序）用递归实现简洁，广度优先（层次）用队列实现；
• 可通过前序+中序或后序+中序构建唯一的二叉树。

通过理论学习+代码实践，就能真正掌握树与二叉树的核心逻辑，为后续学习更复杂的数据结构打下坚实基础！