C++ 实现简单二叉树操作：插入节点与数据打印-EW帮帮网

一、引言

在计算机科学领域，树结构是一种非常重要的数据结构，尤其是二叉树，它在搜索、排序和存储数据方面有着广泛的应用。本文将详细介绍一个使用 C++ 实现的简单二叉树项目，该项目包含节点插入和数据打印功能。我们将从代码结构、核心功能实现到测试用例等方面进行深入分析。

二、项目概述

本项目主要由两个文件组成：main.cpp 和 tree.h。tree.h 文件定义了二叉树的节点结构和树类，包含节点的插入、数据打印和内存释放等功能；main.cpp 文件则是程序的入口，负责创建树对象并进行节点插入和数据打印操作。

三、代码结构分析

1. tree.h 文件

节点结构定义

template<class Data>
struct node
{
    Data data;
    node* parent;
    node* pLeft;
    node* pRight;
    node* brother;
    node();
};

这里定义了一个模板结构体 node，用于表示二叉树的节点。每个节点包含数据 data、父节点指针 parent、左右子节点指针 pLeft 和 pRight 以及兄弟节点指针 brother。构造函数 node() 用于初始化节点的数据和指针。

树类定义

template<class Data>
class tree
{
    node<Data>* pRoot;
public:
    tree();
    ~tree();
    void insertChildren(Data d, int position = 1);
    void insertChildren(node<Data>* pos, Data d, int position = 1);
    node<Data>* pNode();
    void printData();
private:
    node<Data>* creatNode(Data d);
    bool isEndNode(node<Data>* p);
    void _printData(node<Data>* p);
    void _insertNode_L(node<Data>* root, Data data);
    void _insertNode_R(node<Data>* root, Data data);
    void _destroyData(node<Data>* curr_root);
};

tree 类是二叉树的核心类，包含根节点指针 pRoot。公有成员函数包括构造函数 tree()、析构函数 ~tree()、节点插入函数 insertChildren、获取根节点指针函数 pNode() 和数据打印函数 printData()。私有成员函数用于辅助实现节点创建、节点插入和内存释放等功能。

核心功能实现

节点插入：insertChildren 函数用于在指定位置插入新节点。根据 position 参数的值，可以选择将新节点插入到左子节点或右子节点位置。

template<class Data>
inline void tree<Data>::insertChildren(node<Data>* pos, Data d, int position)
{
    if (pos)
    {
        if (position == 1)
        {
            if (pos->pLeft)_insertNode_L(pos->pLeft, d);
            else
            {
                pos->pLeft = creatNode(d);
                if (SHOW_DEBUG_DATA == 1)printf("已向堆区%p申请空间存储数据\n", pos->pLeft);
            }
        }
        else if (position == 2)
        {
            if (pos->pRight)_insertNode_R(pos->pRight, d);
            else
            {
                pos->pRight = creatNode(d);
                if (SHOW_DEBUG_DATA == 1)printf("已向堆区%p申请空间存储数据\n", pos->pRight);
            }
        }
    }
}

数据打印：printData 函数使用递归方式遍历二叉树，并打印每个节点的数据。

template<class Data>
void tree<Data>::printData()
{
    _printData(pRoot);
}

template<class Data>
inline void tree<Data>::_printData(node<Data>* p)
{
    if (!isEndNode(p))
    {
        if (p->pLeft)
        {
            _printData(p->pLeft);
        }
        if (p->pRight)
        {
            _printData(p->pRight);
        }
    }
    printf("data:%d\n", p->data);
}

内存释放：析构函数 ~tree() 调用 _destroyData 函数，使用递归方式释放二叉树中所有节点的内存。

cpp

运行

template<class Data>
inline tree<Data>::~tree()
{
    _destroyData(pRoot);
}

template<class Data>
void tree<Data>::_destroyData(node<Data>* curr_root)
{
    if (!isEndNode(curr_root))
    {
        if (curr_root->pLeft)
        {
            _destroyData(curr_root->pLeft);
        }
        if (curr_root->pRight)
        {
            _destroyData(curr_root->pRight);
        }
    }
    if (SHOW_DEBUG_DATA == 1)printf("已析构%p\n", curr_root);
    delete curr_root;
}

2. `main.cpp` 文件

#include"tree.h"
#include<stdio.h>

int main()
{
    tree<int> a;
    for (int i = 0; i < 200; i++)
    {
        int r = i % 2 + 1;
        a.insertChildren(i, r);
    }
    a.printData();
    return 0;
}

main.cpp 文件是程序的入口，创建了一个 tree<int> 类型的对象 a，并使用 for 循环插入 200 个节点，最后调用 printData 函数打印二叉树中的所有数据。

四、测试与运行

将 main.cpp 和 tree.h 文件保存到同一目录下，使用 C++ 编译器进行编译和运行。运行程序后，将看到节点插入和数据打印的输出信息。

五、总结

通过这个简单的二叉树项目，我们学习了如何使用 C++ 实现二叉树的基本操作，包括节点插入、数据打印和内存释放。递归是实现这些操作的关键，它可以使代码更加简洁和易于理解。同时，我们也了解了模板类的使用，它可以提高代码的复用性。希望本文对大家理解二叉树的实现和应用有所帮助。

完整代码

tree.h

#pragma once
#include <cstddef>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
//SHOE_DEBUG_DATA == 1时，显示调试输出信息
#define SHOW_DEBUG_DATA 1
//定义结点
template<class Data>
struct node
{
	Data data;
	node* parent;
	node* pLeft;
	node* pRight;
	node* brother;
	node();
};

template<class Data>
class tree
{
	node<Data>* pRoot;
public:
	tree();
	~tree();
	
	/*在根节点插入数据
	* @param d 数据
	* @param position 位置
	* 1->左孩子位置
	* 2->右孩子位置
	* 默认为左孩子
	*/
	void insertChildren(Data d, int position = 1);
	/*在pos节点创建孩子
	* @param pos 节点位置
	* @param d 数据
	* @param position 位置
	* 1->左孩子位置
	* 2->右孩子位置
	* 默认为左孩子
	*/
	void insertChildren(node<Data>* pos,Data d, int position = 1);
	//获取pNode
	node<Data>* pNode();
	void printData();
private:
	//创建节点并返回新节点的指针
	node<Data>* creatNode(Data d);
	//判断是不是叶节点
	bool isEndNode(node<Data>* p);
	void _printData(node<Data>* p);
	void _insertNode_L(node<Data>* root, Data data);
	void _insertNode_R(node<Data>* root, Data data);
	void _destroyData(node<Data>* curr_root);//析构数据
};

template<class Data>
node<Data>::node()//数据初始化
{
	memset(&data, 0, sizeof(Data));
	parent=NULL;
	pLeft=NULL;
	pRight = NULL;
	brother=NULL;
}

template<class Data>
tree<Data>::tree()//创建节点
{
	pRoot = new node<Data>;
	if(SHOW_DEBUG_DATA==1)printf("已向堆区%p申请空间存储tree的根节点\n", pRoot);
}

template<class Data>
inline tree<Data>::~tree()
{
	_destroyData(pRoot);
}

template<class Data>
node<Data>* tree<Data>::creatNode(Data d)
{
	node<Data>* tempNode = new node<Data>;//创建节点 注意内存释放
	tempNode->data = d;
	return tempNode;//返回指针
}

template<class Data>
inline void tree<Data>::insertChildren(node<Data>* pos, Data d, int position)
{
	if (pos)//当前根节点不为空
	{
		if (position == 1)
		{
			if (pos->pLeft)_insertNode_L(pos->pLeft, d);
			else
			{
				pos->pLeft = creatNode(d);
				if (SHOW_DEBUG_DATA == 1)printf("已向堆区%p申请空间存储数据\n", pos->pLeft);
			}
		}
		else if (position == 2)
		{
			if (pos->pRight)_insertNode_R(pos->pRight, d);
			else
			{
				pos->pRight = creatNode(d);
				if (SHOW_DEBUG_DATA == 1)printf("已向堆区%p申请空间存储数据\n", pos->pRight);
			}
		}
	}
}

template<class Data>
node<Data>* tree<Data>::pNode()
{
	return pRoot;
}

template<class Data>
void tree<Data>::printData()
{
	_printData(pRoot);
}

template<class Data>
void tree<Data>::insertChildren(Data d, int position)
{
	if (pRoot)//当前根节点不为空
	{
		if (position == 1)
		{
			if (pRoot->pLeft)_insertNode_L(pRoot->pLeft, d);
			else
			{
				pRoot->pLeft = creatNode(d);
				if (SHOW_DEBUG_DATA == 1)printf("已向堆区%p申请空间存储数据\n",pRoot->pLeft);
			}
		}
		else if (position == 2)
		{
			if (pRoot->pRight)_insertNode_R(pRoot->pRight, d);
			else
			{
				pRoot->pRight = creatNode(d);
				if (SHOW_DEBUG_DATA == 1)printf("已向堆区%p申请空间存储数据\n", pRoot->pRight);
			}
		}
	}
}

template<class Data>
inline bool tree<Data>::isEndNode(node<Data>* p)
{
	return !(p->pLeft || p->pRight);
}

template<class Data>
inline void tree<Data>::_printData(node<Data>* p)
{
	if (!isEndNode(p))//针对有孩子的，需要递归
	{
		if (p->pLeft)//只要有孩子就不忙析构
		{
			_printData(p->pLeft);
		}
		if (p->pRight)//只要有孩子就不忙析构
		{
			_printData(p->pRight);//递归处理
		}
	}
	printf("data:%d\n", p->data);
}

template<class Data>
void tree<Data>::_insertNode_L(node<Data>* root, Data data)
{
	if (root)//当前的节点有孩子
	{
		if (root->pLeft)_insertNode_L(root->pLeft, data);//左孩子有，则再找子孩子
		else//没有孩子，就直接加
		{
			root->pLeft = creatNode(data);
			if (SHOW_DEBUG_DATA == 1)printf("已向堆区%p申请空间存储数据\n", root->pLeft);
		}
	}
	else//没有孩子
	{
		root->pLeft = creatNode(data);
	}
}

template<class Data>
void tree<Data>::_insertNode_R(node<Data>* root, Data data)
{
	if (root)//当前的节点有孩子
	{
		if (root->pRight)_insertNode_L(root->pRight, data);//左孩子有，则再找子孩子
		else//没有孩子，就直接加
		{
			root->pRight = creatNode(data);
			if (SHOW_DEBUG_DATA == 1)printf("已向堆区%p申请空间存储数据\n", root->pRight);
		}
	}
	else//没有孩子
	{
		root->pRight = creatNode(data);
	}
}

template<class Data>
void tree<Data>::_destroyData(node<Data>* curr_root)
{
	if (!isEndNode(curr_root))//针对有孩子的，需要递归
	{
		if (curr_root->pLeft)//只要有孩子就不忙析构
		{
			_destroyData(curr_root->pLeft);
		}
		if (curr_root->pRight)//只要有孩子就不忙析构
		{
			_destroyData(curr_root->pRight);//递归处理
		}
	}
	if (SHOW_DEBUG_DATA == 1)printf("已析构%p\n", curr_root);
	delete curr_root;
}

以上就是关于这个二叉树项目的详细介绍，欢迎大家在评论区留言交流。

C++ 实现简单二叉树操作：插入节点与数据打印

一、引言

二、项目概述

三、代码结构分析

1. tree.h 文件

节点结构定义

树类定义

核心功能实现

2. `main.cpp` 文件

四、测试与运行

五、总结

完整代码

网站公告

今日签到

热门文章

最新发布

C++ 实现简单二叉树操作：插入节点与数据打印

一、引言

二、项目概述

三、代码结构分析

1. tree.h 文件

节点结构定义

树类定义

核心功能实现

2. main.cpp 文件

四、测试与运行

五、总结

完整代码

网站公告

今日签到

热门文章

最新发布

2. `main.cpp` 文件