当前位置: 编程技术>c/c++/嵌入式
C++二叉树结构的建立与基本操作
来源: 互联网 发布时间:2014-10-22
本文导语: 准备数据定义二叉树结构操作中需要用到的变量及数据等。 代码如下:#define MAXLEN 20 //最大长度typedef char DATA; //定义元素类型struct CBTType //定义二叉树结点类型 { DATA data; //...
准备数据
定义二叉树结构操作中需要用到的变量及数据等。
代码如下:
#define MAXLEN 20 //最大长度
typedef char DATA; //定义元素类型
struct CBTType //定义二叉树结点类型
{
DATA data; //元素数据
CBTType * left; //左子树结点指针
CBTType * right; //右子树结点指针
};
定义二叉树结构数据元素的类型DATA以及二叉树结构的数据结构CBTType。结点的具体数据保存在一个姐都DATA中,而指针left用来指向左子树结点,指针right用来指向右子树结点
初始化二叉树
初始化二叉树,将一个结点设置为二叉树的根结点。
代码如下:
CBTType * InitTree()
{
CBTType * node;
if(node = new CBTType) //申请内存
{
coutleft=NULL;
node->right=NULL;
if(node!=NULL) //如果二叉树结点不为空
{
return node;
} else
{
return NULL;
}
}
return 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;
}
}
}
}
输入参数treeNode为待查找的二叉树的根结点,输入参数data为待查找的结点数据。程序中首先判断根结点是否为空,然后根据数据判断是否为根结点,然后分别向左右子树进行查找,采用递归的方法进行查找,查找到该结点则返回结点对应的指针;如果全都查找不到,则返回NULL。
添加结点
添加结点就是在二叉树中添加结点数据,添加结点时除了要输入结点数据外,还需要指定其父结点,以及添加的结点作为左子树还是右子树。然后将该结点置为其父结点的左子树或者右子树。
代码如下:
void AddTreeNode(CBTType *treeNode)
{
CBTType *pnode,*parent;
DATA data;
char menusel;
if(pnode=new CBTType) //分配内存
{
coutleft=NULL; //设置左子树为空
pnode->right=NULL; //设置左子树为空
cout