C++二叉树结构的建立与基本操作详解

结果或目标

最终将构建一个支持交互式操作的C++控制台程序，能够完成二叉树的动态维护与多种维度的数据访问，确保理解递归在树形结构处理中的核心作用。

准备条件

在编写具体功能前，需要先定义二叉树的内存结构。这包括数据类型的别名定义、最大容量常量以及包含左右指针的节点结构体。

第1步：定义节点结构

目的：确定存储在树中的数据格式及指针连接方式。
参数：MAXLEN用于控制队列长度，DATA为元素类型，CBTType为结构体名称。

#define MAXLEN 20      //最大长度
typedef char DATA;       //定义元素类型
struct CBTType              //定义二叉树结点类型 
{
    DATA data;             //元素数据 
    CBTType * left;        //左子树结点指针 
    CBTType * right;       //右子树结点指针 
};

该结构通过left和right指针分别指向左右子节点，空指针表示子树为空。这种链式存储结构使得二叉树可以灵活地扩展。

真实操作顺序

第2步：初始化二叉树

目的：申请堆内存并设置根节点。
入口：调用InitTree函数。
动作：使用new关键字分配CBTType对象，获取用户输入的根数据，并将左右指针初始化为NULL。

CBTType * InitTree()
{
    CBTType * node;
    if(node = new CBTType)   //申请内存 
    {
        cout<<"请先输入一个根节点数据："<<endl;
        cin>>node->data;
        node->left=NULL;
        node->right=NULL;
        return node; 
    }
    return NULL;
}

第3步：查找指定数据的节点

目的：在添加节点时，必须定位到其父节点位置。
入口：TreeFindNode(treeNode, data)。
逻辑：采用深度优先搜索策略，首先检查当前节点是否匹配，若不匹配则递归向左右子树延伸。找到返回指针，未找到返回NULL。

CBTType *TreeFindNode(CBTType *treeNode,DATA data)
{
    CBTType *ptr;
    if(treeNode==NULL)
    {
        return NULL;
    }else
    {
        if(treeNode->data==data)
        {
            return treeNode;
        }else   
        {
            if(ptr=TreeFindNode(treeNode->left,data))   //左子树递归查找 
            {
                return ptr;
            }else if(ptr=TreeFindNode(treeNode->right,data))     //右子树递归查找 
            {
                return ptr;
            }else
            {
                return NULL;
            }
        }
    } 
}

第4步：添加新节点

目的：将新数据挂载到指定的父节点下，形成左右子树关系。
入口：AddTreeNode(root)。
动作：1. 为新节点分配内存；2. 输入新数据并设为空子树；3. 调用查找函数定位父节点；4. 若找到父节点，根据用户选择（1或2）将新节点指针赋给父节点的left或right。

void AddTreeNode(CBTType *treeNode)
{
    CBTType *pnode,*parent;
    DATA data;
    char menusel;
    if(pnode=new CBTType)         //分配内存 
    {
        cout<<"输入二叉树结点数据："<<endl;
        cin>>pnode->data;
        pnode->left=NULL;        //设置左子树为空 
        pnode->right=NULL;        //设置右子树为空 
        cout<<"输入该结点的父结点数据"<<endl;
        cin>>data;
        parent=TreeFindNode(treeNode,data); //查找父结点 
        if(!parent)
        {
            cout<<"没有找到父结点"<<endl;
            delete pnode;
            return ;
        }
        cout<<"1.添加该结点到左子树；2.添加该结点到右子树。"<<endl;
        do
        {
            cin>>menusel;
            if(menusel=='1'||menusel=='2')
            {
                switch(menusel)
                {
                    case '1':        //添加结点到左子树 
                        if(parent->left)       //左子树不为空
                        {
                            cout<<"左子树结点不为空"<<endl; 
                        } 
                        else
                        {
                            parent->left=pnode;
                            cout<<"数据添加成功！"<<endl;
                        }
                        break;
                    case '2':        //添加结点到右子树 
                        if(parent->right)       //右子树不为空
                        {
                            cout<<"右子树结点不为空"<<endl;
                        } 
                        else
                        {
                            parent->right=pnode;
                            cout<<"数据添加成功！"<<endl; 
                        } 
                        break;
                    default:
                        cout<<"子节点选择error!"<<endl;
                        break;
                } 
            }
        }while(menusel!='1'&&menusel!='2');
    }
} 

第5步：计算二叉树的深度

目的：通过递归统计树的最大层数。
逻辑：若节点为空返回0；否则分别递归计算左子树深度和右子树深度，取较大值加1作为当前节点深度。

int TreeDepth(CBTType *treeNode)
{
    int depleft,depright;
    if(treeNode==NULL)
    {
        return 0;       //结点为空的时候，深度为0 
    }
    else
    {
        depleft=TreeDepth(treeNode->left);   //左子树深度
        depright=TreeDepth(treeNode->right);       //右子树深度
        if(depleft)  //如果左子树深度大，则取左+1
        {
            return ++depleft;
        }
        else 
        {
            return ++depright;
        } 
    }
}

第6步：清空二叉树（资源释放）

风险提示：此操作不可逆，执行后所有数据及节点内存将被释放。
逻辑：严格遵循后序遍历的顺序进行清理，先清空左子树，再清空右子树，最后删除当前节点。这样可以避免悬垂指针导致的安全隐患。

void ClearTree(CBTType *treeNode)
{
    if(treeNode)          
    {
        ClearTree(treeNode->left);           //清空左子树
        ClearTree(treeNode->right);           //清空右子树
        delete treeNode;      //释放当前结点所占用的内存 
    }
}

第7步：实现四种遍历算法

按层遍历（LevelTree）：不使用递归，而是利用MAXLEN定义的数组模拟循环队列。根节点入队后，循环取出队首节点显示，并将其非空的左右孩子依次入队，直到队列为空。

void LevelTree(CBTType *treeNode)
{
    CBTType *p;
    CBTType *q[MAXLEN];       //定义一个队列 
    int head=0,tail=0;
    if(treeNode)          
    {
        tail=(tail+1)%MAXLEN;                 
        q[tail]=treeNode;                   
        while(head!=tail)
        {
            head=(head+1)%MAXLEN;           
            p=q[head];                  
            ShowNodeData(p);            
            if(p->left!=NULL)               
            {
                tail=(tail+1)%MAXLEN;                
                q[tail]=p->left;                  
            }
            if(p->right!=NULL)               
            {
                tail=(tail+1)%MAXLEN;                
                q[tail]=p->right;                  
            } 
        } 
    } 
}

先序、中序、后序遍历：均基于递归实现，区别在于ShowNodeData显示的时机。先序（根-左-右），中序（左-根-右），后序（左-右-根）。

// 先序遍历
void DLRTree(CBTType *treeNode)
{
    if(treeNode)
    {
        ShowNodeData(treeNode);    
        DLRTree(treeNode->left);        
        DLRTree(treeNode->right);      
    }
}

// 中序遍历
void LDRTree(CBTType *treeNode)
{
    if(treeNode)
    {
        LDRTree(treeNode->left);          
        ShowNodeData(treeNode);             
        DLRTree(treeNode->right);          
    } 
}

// 后序遍历
void LRDTree(CBTType *treeNode)
{
    if(treeNode)
    {
        LRDTree(treeNode->left);          
        DLRTree(treeNode->right);          
        ShowNodeData(treeNode);             
    } 
}

完成判断

完成上述各函数的封装后，编写main函数整合交互逻辑。通过循环菜单引导用户进行“添加节点”、“查看深度”以及不同方式的“遍历输出”。当所有输入操作结束且无报错提示时，即视为基本功能验证通过。

原文有依据的排错

• 节点不存在处理：在AddTreeNode中，若查找到的父节点指针为NULL，程序会提示并提前退出，同时手动delete掉已分配但未挂载的新节点，防止内存泄漏。
• 左右子树覆盖检查：在添加节点时，若对应的左/右子树指针已存在内容，程序仅给出警告而不强制覆盖，符合通用二叉树添加规则（除非明确需要重载，但原逻辑为非满二叉树插入限制）。

简要总结

C++中二叉树的构建与操作体现了经典的“分而治之”与递归思维。无论是深度的递推计算，还是节点的层级调度，都依赖于对左右子树状态的准确追踪。在实际开发中，更复杂的场景可能会涉及平衡二叉树（如AVL或红黑树）以优化查询效率，但掌握上述基础操作是进阶的必要前提。

对应的树形结构图如图：

程序运行界面：

以上就是C++二叉树结构的建立与基本操作的详细内容，更多关于C++数据结构与算法的资料请关注本站其它相关文章！