C++二叉树结构的建立与基本操作.doc

C++二叉树结构的建立与基本操作 二叉树是数据结构中的树的一种特殊情况，有关二叉树的相关概念，这里不再赘述，如果不了解二叉树相关概念，建议先学习数据结构中的二叉树的知识点 准备数据 定义二叉树结构操作中需要用到的变量及数据等。 复制代码 代码如下: #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) //申请内存 { cout请先输入一个根节点数据：endl; cinnode-data; node-left=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) //分配内存 { cout输入二叉树结点数据：endl; cinpnode-data; pnode-left=NULL; //设置左子树为空 pnode-right=NULL; //设置左子树为空 cout输入该结点的父结点数据endl; cindata; parent=TreeFindNode(treeNode,data);//查找父结点，获得结点指针 if(!parent) { cout没有找到父结点endl; delete pnode; return ; } cout1.添加该结点到左子树；2.添加该结点到右子树。请输入操作对应的数字。endl; do { cinmenusel; if(menusel==1||menusel==