CPP[算法与数据结构]Day015 有序二叉树的增删改查，先序遍历，中序遍历，后序遍历

目录0x00 二叉树0x01 有序二叉树0x02补充二叉树的遍历0X03 升降序二叉树的增删改查0x00 二叉树二叉树每个节点有且只有两个孩子设计数据结构的时候每个节点只设计两个指针左节点和右节点二叉树中的叶子节点两个孩子都为NULL的节点。0x01 有序二叉树升序二叉树左节点 根节点 右节点,更准确的说升序二叉树按照“左中右”中序遍历的结果一定是从小到大的。其实中序遍历本质上也是递归遍历。降序二叉树左节点 根节点 右节点 按照左中右中序遍历的结果一定是大到小0x02补充二叉树的遍历根据根的位置分为三种先序遍历根左右中序遍历左根右后序遍历左右根0X03 升降序二叉树的增删改查增问题如何将一个数据插入一个升序二叉树或者一个升序二叉树的子树呢可以采用分治的思想递归插入。即首先确定最简单的情况基线条件要插入的子树(树)没有节点那么直接插入的数据作为子树树的根节点。然后确定递归条件即想办法缩小问题的规模如果插入的数据小于根节点那么就将该数据插入根节点的左子树缩小了问题的规模如果插入的数据比根节点大那么将该数据插入根节点的右子树。遍历遍历仍然使用分治思想最简单的情形即基线条件树没有节点直接返回。递归条件缩小问题规模遍历左子树打印根的值遍历右子树查因为二叉树是有序的这里二分查找这种高效率利器就能大显身手了删注意我们删除了有序二叉树的某个节点后仍然要保证有序二叉树有序删除根节点有右孩子让根节点的左孩子成为右孩子的最左孩子。让根节点的右孩子成为根。释放根节点内存没有右孩子让左孩子成为根释放根节点内存删除的节点不是根节点找到要删除的节点的父节点如果要删除的节点有右孩子要删除的节点的左孩子成为要删除的节点的右孩子的最左孩子要删除的节点如果是其父的左孩子要删除的节点的 右孩子 成为 要删除的节点的父节点的左孩子要删删除的节点如果是其父的右孩子要删除的节点的 右孩子 成为 要删除的节点的父节点的 右孩子释放要删除的节点的内存3.要删除的节点如果没有右孩子如果要删除的节点是其父的左孩子要删除的节点的左孩子成为要删除的节点的父节点的左孩子如果要删除的节点是其父的右孩子要删除的节点的左孩子成为要删除的节点的父节点的右孩子释放要删除的节点的内存。代码有点小bug以后闲了重写#include iostream using namespace std; #include 00-Tree.h int main(){ Treeint tree; tree.insert(6); tree.insert(4); tree.insert(7); tree.insert(2); tree.insert(5); tree.insert(8); tree.insert(1); tree.insert(3); coutbefore:endl; tree.travel(); tree.search(6); tree.delNode(6); coutafter:endl; tree.travel(); return 0; }#pragma once /*有序二叉树*/ template class T class Tree{ //定义内部类节点类型 //原因创建内部类更好操作一些也可以不创建内部类 struct Node{ T pBuff; Node* pLeft; Node* pRight; }; Node* pRoot;//树类型只有一个元素根节点指针。 public: //1.构造函数 Tree(){pRoot NULL;} //2.析构函数: //为什么要写析构函数因为我们希望当Tree类对象死亡的它动态内存分配开的相关内存也能被释放。 //释放思路从二叉树的叶子开始逐层往上释放动态内存分配开的内存空间。 ~Tree(){if(pRoot) _clear(); pRoot NULL;} //3.创建节点 Node* CreateNode(const T data){ Node* pNew new Node; pNew-pBuff data; pNew-pLeft pNew-pRight NULL; return pNew; } //4.增 void insert(const T data); //5.中序遍历 void travel(); //6.查 void search(const T data); //7.删除 bool delNode(const T data); private: void _insert(Node** ppRoot,const T data); void _travel(Node* pRoot); Node* _search(Node* pRoot,const T data); void _clear(){} }; //1.增 template class T void TreeT::insert(const T data){ _insert(pRoot,data); } template class T //向一颗树ppRoot升序插入数据data注意想要通过函数修改一个指针的指向必须传入该指针的二级指针 void TreeT::_insert(Node** ppRoot,const T data){ Node* pNew CreateNode(data); //最简单的情形:基线条件 if(*ppRoot NULL){ *ppRoot pNew; return; } //递归条件 //如果比根小那么就用同样的算法插入到左子树 if((*ppRoot)-pBuff data){//升序二叉树左根右成为左孩子 _insert(((*ppRoot)-pLeft),data); }else{ _insert(((*ppRoot)-pRight),data); } } //2.中序遍历 template class T void TreeT::_travel(Node* pRoot){ if(pRoot NULL) return; else{ _travel(pRoot-pLeft); coutpRoot-pBuff; _travel(pRoot-pRight); } return; } template class T void TreeT::travel(){ _travel(pRoot); coutendl; } //3.查 template class T void TreeT::search(const T data){ Node* ret _search(pRoot,data); if(ret){ coutnot find!endl; return; } coutnot find!; return; } template class T typename TreeT::Node* TreeT::_search(Node* pRoot,const T data){ if(pRoot NULL) return NULL; if(pRoot-pBuff data )return pRoot; else{ if(pRoot-pBuff data) return _search(pRoot-pLeft,data); else return _search(pRoot-pRight,data); } } //4.删除 template class T bool TreeT::delNode(const T data){ Node* pTemp NULL; Node* pDelete pRoot; if(pRoot-pBuff data){//要删除的节点是根节点 if(pRoot-pRight){//有右孩子 pTemp pRoot-pRight; while(pTemp-pLeft){ pTemp pTemp-pLeft; } pTemp-pLeft pRoot-pRight; pRoot pRoot - pLeft; }else{//没有右孩子 pRoot pRoot-pLeft; } delete pDelete; return true; } Node* pDelParent NULL; bool isFind false; while(pDelete){ if(pDelete-pBuff data){ isFind true; break; } pDelParent pDelete; if(pDelete-pBuff data){ pDelete pDelete-pLeft; }else{ pDelete pDelete-pRight; } } if(isFind false) return false; if(pDelete-pRight){ Node* pTemp pDelete-pRight; while(pTemp-pLeft){ pTemp pTemp-pLeft; } pTemp-pLeft pDelete-pLeft; if(pDelete pDelParent-pLeft){ pDelParent-pLeft pDelete-pRight; }else{ pDelParent-pRight pDelete-pRight; } delete pDelete; }else{ if(pDelete pDelParent-pLeft){ pDelParent-pLeft pDelete-pLeft; }else{ pDelParent-pRight pDelete-pLeft; } delete pDelete; } return true; } rootkali:~/桌面/C/算法/2019-09#