二叉树的主要难点是：二级指针的应用和数据的删除。
二叉树的成立的主要点是：根结点必须大于左子树、小于右子树
二叉树的删除分别为几种情况为：无子节点、有一个子节点、为满子结点。
无子节点：删除其即可。
有一个子节点：将子节点的父节点指向该节点。（ps：如何判断他是父节点的左数还是右树？，可根据程立的主要点：根结点必须大于左子树、小于右子树来判断）
为满子节点：将右结点代替删除的节点，如何找到已经代替好的结点的左节点的最深处，并将原左结点替换上去。
如图：
查找：完全可以按照可根据程立的主要点，判断它和根结点，是大于还小于，小于从左结点开始重复该操作，大于同上。
插入：个人感觉完全就是添加新节点，因为你要是随意插入一个数据，可能破坏数据平衡导致查找不到该数据。
#pragma once #include<Windows.h> #include<iostream> using namespace std; template<typename Type> class Tree; template<typename Type> //数据模型 class Data_ { public: friend class Tree<Type>; Data_(Type a = 0):data(a),left(NULL),right(NULL){} private: Type data; Data_<Type>* left; Data_<Type>* right; protected: }; template<typename Type> //查找的父子结点 struct cha_lao_nei_rong { Data_<Type>** fu_xi_jie_dian = NULL; Data_<Type>** zi_xi_jie_dian = NULL; bool jie_guo = false; }; template<typename Type> class Tree { public: // 初始化 Tree() { root = NULL; count = 0; } //输入数据 void Push_Data_() { Type fu_Data; cout << "输入参数：" << endl; cin >> fu_Data; Data_<Type>** kuai = &root; //查看是否具有根结点 if (!root) { try { root = new Data_<Type>(fu_Data); count++; } catch (bad_alloc) { cout << "申请失败!" << endl; exit(-1); } } else { //为数据找到合适位置 while (*kuai) { if ((*kuai)->data > fu_Data) kuai = &(*kuai)->left; else if ((*kuai)->data < fu_Data) kuai = &(*kuai)->right; else break; } //找到后给数据赋值 try { *kuai = new Data_<Type>(fu_Data); count++; }//若申请内存失败 catch (bad_alloc) { cout << "申请失败!" << endl; exit(-1); } } } //显示数据 ostream& print(ostream& a, Data_<Type>* e) { if (!e) return a; a << "数据：" << e->data << endl; print(a, e->left); print(a, e->right); return a; }; friend ostream& operator<<(ostream& a, Tree<Type> e) { return e.print(a,e.root); }; //查找数据 cha_lao_nei_rong<Type> & find_s() { //输入查找的数据 Type fu_Data; cout << "输入查找的参数：" << endl; cin >> fu_Data; cha_lao_nei_rong<Type>a; a.fu_xi_jie_dian = NULL; a.zi_xi_jie_dian = &(root); //利用添加数据的原理：大于往右树，小于往左树 while ((*a.zi_xi_jie_dian)) { if ((*a.zi_xi_jie_dian)->data > fu_Data) { a.fu_xi_jie_dian = a.zi_xi_jie_dian; a.zi_xi_jie_dian = &(*a.zi_xi_jie_dian)->left; }else if ((*a.zi_xi_jie_dian)->data < fu_Data) { a.fu_xi_jie_dian = a.zi_xi_jie_dian; a.zi_xi_jie_dian = &(*a.zi_xi_jie_dian)->right; } else //当他不大于不小于则为等于 { cout << "有该元素" << endl; a.jie_guo = true; return a; } } a.jie_guo = false; return a; }; //删除数据 int Delet_Data() { cha_lao_nei_rong<Type> &a = find_s(); if (!a.jie_guo) cout << "删除的数据不在" << endl; else { if ((*a.zi_xi_jie_dian)->left == NULL && (*a.zi_xi_jie_dian)->right == NULL) { (*a.fu_xi_jie_dian)->data > (*a.zi_xi_jie_dian)->data ? (*a.fu_xi_jie_dian)->left = NULL : (*a.fu_xi_jie_dian)->right = NULL; delete (*a.zi_xi_jie_dian); count--; } else if ((*a.zi_xi_jie_dian)->left != NULL && (*a.zi_xi_jie_dian)->right == NULL) { Data_<Type> * wc = (*a.zi_xi_jie_dian)->left; Data_<Type>* detele_s = (*a.zi_xi_jie_dian); (*a.fu_xi_jie_dian)->data > (*a.zi_xi_jie_dian)->data ? (*a.fu_xi_jie_dian)->left = wc : (*a.fu_xi_jie_dian)->right = wc; delete detele_s; count--; } else if ((*a.zi_xi_jie_dian)->left == NULL && (*a.zi_xi_jie_dian)->right != NULL) { Data_<Type>* wc = (*a.zi_xi_jie_dian)->right; Data_<Type>* detele_s = (*a.zi_xi_jie_dian); (*a.fu_xi_jie_dian)->data > (*a.zi_xi_jie_dian)->data ? (*a.fu_xi_jie_dian)->left = wc : (*a.fu_xi_jie_dian)->right = wc; delete detele_s; count--; } else { //删除根结点 if (!(a.fu_xi_jie_dian)) { //保存原根结点的左右子节点 Data_<Type>* Left = (root->left); Data_<Type>* Right = (root->right); //删除根结点 delete root; //将右树赋值给根 root = Right; //将右树赋值给** 类型方便对指针进行操作 Data_<Type>** Right_Left = &(Right->left); //查找最深的右子树 while ((*Right_Left)) Right_Left = &(*Right_Left)->left; //赋值 *Right_Left = &(*Left); count--; } //删除满结点 else { //保存原满结点 Data_<Type>* delete_s = (*a.zi_xi_jie_dian); //保存原根结点的左右子节点 Data_<Type>* Left = (*a.zi_xi_jie_dian)->left; Data_<Type>* Right = (*a.zi_xi_jie_dian)->right; (*a.fu_xi_jie_dian)->data > (*a.zi_xi_jie_dian)->data ? (*a.fu_xi_jie_dian)->left = Right: (*a.fu_xi_jie_dian)->right = Right; (*a.zi_xi_jie_dian) = Right; //将右树赋值给** 类型方便对指针进行操作 Data_<Type>** Right_Left = &(Right->left); //查找最深的右子树 while ((*Right_Left)) Right_Left = &(*Right_Left)->left; *Right_Left = Left; delete delete_s; count--; } } } return 0; } //删除树 void clear() { Data_<Type> *Left = root->left; Data_<Type> *Right = root->right; while (Left)//直到为NULL { Data_<Type>* Left_fu = Left->left; // 记录下个结点的地址 delete Left; Left = Left_fu;//将下个结点赋值给Left } while (Right)//直到为NULL { Data_<Type>* Right_fu = Right->right;// 记录下个结点的地址 delete Right; Right = Right_fu;//将下个结点赋值给Right } delete root; count = 0; }; private: Data_<Type>* root; int count; protected: };