⼆叉树
⼀：创建以及初始化赋值：
struct BiTree{
char data; BiTree* lchild; BiTree* Rchild;};
//初始化
BiTree* create() {//先序创建⼆叉树 BiTree *T; char a; cin >> a;
if (a == '.')return NULL; else {
T = (BiTree*)malloc(sizeof(BiTree)); T->data = a;
T->lchild = create(); T->Rchild = create(); }
//若想中序或后序创建，则只需改变函数中
//T->data=a;T->lchild=create();T->rchild=create();这三条语句的顺序
//先给T->data=a在先的话是先序，在中间的话是中序，在最后的话是后序。}
⼆：⼆叉树遍历⽅法：
/*
先序的遍历顺序是根节点->左⼦树->右⼦树。 中序的遍历顺序是左⼦树->根节点->右⼦树。 后序的遍历顺序是右⼦树->根节点->左⼦树。 层序的遍历顺序是按层顺次遍历。 先序、中序、后序的代码基本相同*/
void pre(BiTree *root) { BiTree* p = root; if (p) {
cout << p->data; pre(p->lchild); pre(p->Rchild); }}
void mid(BiTree* root) { BiTree* p = root; if (root) {
mid(p->lchild); cout << p->data; mid(p->Rchild); }}
void post(BiTree* root) { BiTree* p = root; if (p) {
post(p->Rchild); post(p->lchild); cout << p->data; }}
三：⼆叉树插⼊操作：
//插⼊操作,没有重复的元素//插⼊法1：
BiTree* BSTInsert(BiTree* L, int key) {
if (!L) {//若是⼀个空表，那么就创建最开始的 L = (BiTree*)malloc(sizeof(BiTree)); L->data = key;
L->lchild = L->Rchild = NULL; }
else {//若不是空表就按照⼆叉树组成规则遍历插⼊ if (L->data < key)
L->Rchild = BSTInsert(L->Rchild, key); else if (L->data > key)
L->lchild = BSTInsert(L->lchild, key); }
return L;}
//插⼊法2：整列树的插⼊//int data[9]={8,3,10,13,14,1,6,7,4};BiTree* Insert(BiTree* L, int data[], int n) { int i;
for (int i = 0; i < n; i++) {
L = BSTInsert(L, data[i]); }
return L;}
四：⼆叉树查询：
//查询元素位置：/*
查询法1：
寻找最⼩、最⼤元素的⽅法是相同的。根据⼆叉树的特点， 若左右⼦树不为空，则根节点的值⼀定⼤于左⼦树的值、
⼩于右⼦树的值，那么这棵树的根节点的最左⼦树和最右⼦树即为最⼩、最⼤元素*/
BiTree* Searchmin(BiTree* L) {//查询最⼩元素或最⼤值 if (L == NULL) {
return NULL; }
if (L->lchild == NULL) { return NULL; }
else return Searchmin(L->lchild);//使⽤递归，不断搜索左⼦树。同理也可以搜索右⼦树来寻找最⼤值}
/*
查询法2：
⽽查找特定元素也利⽤了排序树的特点。将结点的值与待查值做⽐较， 若结点值⼤，则说明待查值在结点的左⼦树；若结点值⼩，
则说明待查值在结点的右⼦树，然后递归或不递归地查询结点的左⼦树或右⼦树即可。*/
BiTree* Search_1(BiTree* L, int key) { if (L == NULL) return NULL; if (key > L->data)
return Search_1(L->Rchild, key);//查找右⼦树 else if (key < L->data)
return Search_1(L->lchild, key);//查找左⼦树 else return L;//找到则返回指针}
// 查询法3：在此基础上，我们可以省掉递归过程，⽤while循环来实现结点的遍历。⾮递归查找代码如下：BiTree* Search_2(BiTree* L, int key) {//重要：不使⽤递归来查找
BiTree* p = L;
while (p) { if (p->data == key) return p;
else p = (p->data > key) ? p->lchild : p->Rchild;//判断下⼀个寻找的是左⼦树还是右⼦树 }
return NULL;//找不到就返回空
}
五：⼆叉树删除节点：
/*删除节点：
⼀、要求
1.没⼦节点时，直接删除
2.有⼦节点时，删除该节点。
如果该节点有左节点，则左节点为⽗节点，右节点不变，如果没只有左节点或者右节点，则直接提升为⽗节点。 3.若左右⼦节点都有的话，那么就找右⼦树的最左⼦树p或者寻找左⼦树的最右⼦树,然后把p放到删除的那个节点的位置*/
void DeleTree(BiTree* T, int data){
{
//1.//寻找需要删除的点
BiTree* p = T, * f = T, *temp;
while (p)
{
if (p->data == data) break;
else if (data > p->data) { f = p; p = p->Rchild; }
else if (data < p->data) {
f = p;
p = p->lchild;
}
}/*找到后,p为⽬标结点,f为其⽗结点*/
//正式开始删除节点操作 if (!p) //找不到 printf(\"错误,⽆此数据\");
//以下为找到的情况
else if (p->lchild == NULL) //情况1:p⽆左⼦树 {
if (f->Rchild = p) //p为f的右⼦树
f->Rchild = p->Rchild; //直接将p的右⼦树连接在f的右⼦树上 else if (f->lchild = p) //p为f的左⼦树
f->lchild = p->Rchild; //直接将p的右⼦树连接在f的右⼦树上 free(p);
}
else if (p->Rchild == NULL) //情况2:p⽆右⼦树 {
if (f->Rchild = p) //p为f的右⼦树
f->Rchild = p->lchild; //直接将p的左⼦树连接在f的右⼦树上
else if (f->lchild = (p)) //p为f的左⼦树
f->lchild = (p)->lchild; //直接将p的左⼦树连接在f的右⼦树上 free(p);
}
else if ((p)->lchild == NULL && (p)->Rchild == NULL)//情况3:p⽆左⼦树和右⼦树 {
if ((f)->Rchild = (p)) //p为f的右⼦树
(f)->Rchild = NULL; //f的右⼦树直接置空 else if ((f)->lchild = (p)) //p为f的左⼦树 (f)->lchild = NULL; //f的右⼦树直接置空 free(p);
}
else if ((p)->lchild != NULL && (p)->Rchild != NULL)//情况4:p有左⼦树和右⼦树 { /*
注意：这⾥是可以寻找被删除节点的左⼦树的最右节点（下⾯的⽅法就是使⽤这个的） 还可以使⽤右⼦树的最左节点 */
*/
if ((f)->Rchild == (p)) //p为f的右⼦树
{
temp = (p)->lchild; //temp为p的左⼦树
while (temp->Rchild) //在temp的右⽀寻找空位,注意，在左⼦树那就是找最右元素，在右⼦树，就找最左元素
temp = temp->lchild; //注意：要是判断没有对应⽅向的⼦树就结束循环
temp->Rchild = (p)->Rchild; //将p的右⼦树连接在temp的右⼦树上,这⼀步是不是很难理解，循环后的节点将会代替删除的节点，所以右⼦树会变成被删除的的右⼦树
(f)->Rchild = (p)->lchild; //再将p的左⼦树连接在f的右⼦树上，这⼀步也是，原本被删除的节点是⽗节点的右⼦树，所以这时候会把
寻找到的中序后继节点的左⼦树分配给
free(p);
}
else if ((f)->lchild = (p)) //注意：这种虽然不是同⼀种节点，但是本质上想要删除都是需要通过右边的中级后节点来代替实现删除 {
temp = (p)->lchild; while (temp->Rchild) temp = temp->lchild; temp->Rchild = (p)->Rchild; (f)->lchild = (p)->lchild; free(p); } }}
因篇幅问题不能全部显示，请点此查看更多更全内容