有了递归实现为啥还要用非递归呢？你会不会有疑惑？如果有，请接着看。
函数的调用需要用到栈，一个应用分配到的栈空间一般为1M大小，在数据很大的情况会造成栈溢出，所以要少用递归。
不用递归实现的原理是模拟栈的运行机制------先进后出，如果这个不会的话，可以看我写的数组模拟栈（现在还没写）。
头文件
#ifdef __cplusplus
extern "C" {
#endif
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//bool
#include <stdbool.h>
//字节封装的模拟栈
#include "SeqStack.h"
/*
*自定义结构体必须包含BiNode结构体,且位于结构体最上方
*struct Person
*{
* struct BiNode data;
* int age;
};
*增加必须提供返回值int型的比较函数,参数为(void* ,void*),函数内强转自己定义的结构体
*int init(void* d1, void* d2)
*{
* struct Person* p1 = (struct Person*)d1;
* struct Person* p2 = (struct Person*)d2;
* int tmp = (p1->age) - (p2->age);
* return tmp;
*}
*遍历需要提供遍历函数，参数为void*，函数内强转自己定义的结构体
*void myprint(void* node)
*{
* if (NULL == node)
* {
* return;
* }
* struct Person* p = (struct Person*)node;
*
* myprint(p->data.lchild);
*
*printf("%c\n", p->age);
*
* myprint(p->data.rchild);
*}
*
*/
//定义结构体
struct BiNode {
//父节点用于删除
struct BiNode* parent;
struct BiNode* rchild;
struct BiNode* lchild;
//用于遍历
bool flag;
};
//初始化树，外部调用
void* Init_BBTree();
//插入根数据，外部调用
void Insert_BBTree(void* tree,void *data,int(*compare)(void *,void *));
//返回树高度，内部使用
int getHight(struct BiNode* node);
//左旋,内部使用
struct BiNode* LeftHand(struct BiNode* data);
//右旋,内部使用
struct BiNode* RightHand(struct BiNode* data);
//平衡树节点,内部使用
struct BiNode* AdjTree(struct BiNode* data);
//遍历二叉树
void foreachTree(void* tree, void(*myprint)(void*));
//删除节点，外部使用
void RemoveTree(void* tree, void* data,int(*compare)(void* ,void*));
//销毁，外部使用
void DestroyTree(void* tree);
#ifdef __cplusplus
}
#endif
初始化
void* Init_BBTree()
{//开辟一个新空间
struct ABLTree* tree = malloc(sizeof(struct ABLTree));
//开辟失败返回NULL
if (NULL == tree)
{
return NULL;
}//初始化根节点为NULL
tree->root = NULL;
//返回空间指针
return tree;
}
插入数据
void Insert_BBTree(void* tree, void* data, int(*compare)(void*, void*))
{//判断参数是否为空
if (NULL == tree)
{
return;
}
if (NULL == data)
{
return;
}
if (NULL == compare)
{
return;
}
//强转
struct ABLTree* newtree = (struct ABLTree*)tree;
//判断根节点是否为空，若为空，把数据赋值给根节点，并返回
if (NULL == newtree->root)
{
newtree->root = data;
return;
}
//不为空，初始化一个栈
void* stack = Init_SeqStack();
//把根节点压入栈中
Push_SeqStack(stack, newtree->root);
//判断栈中是否还有数据
while (Size_SeqStack(stack) > 0)
{//获取栈顶元素
struct BiNode* info = (struct BiNode*)Top_SeqStack(stack);
//弹出栈顶元素
Pop_SeqStack(stack);
//判断栈顶元素与数据的大小
if(compare(info,data)>0)
{//如果栈顶元素大，判断栈顶元素的左子节点是否为空
if (NULL == info->lchild)
{//为空，赋值并返回
info->lchild = data;
info->lchild->parent = info;
break;
}
//不为空，把左子节点压入栈中,并中断当前循环，进入下次循环
Push_SeqStack(stack, info->lchild);
continue;
}
else
{//如果栈顶元素小，判断栈顶元素的右子节点是否为空
if (NULL == info->rchild)
{//为空，赋值并返回
info->rchild = data;
info->rchild->parent = info;
break;
}
//不为空，把右子节点压入栈中,并中断当前循环，进入下次循环
Push_SeqStack(stack, info->rchild);
continue;
}
}
//销毁栈
Destroy_SeqStack(stack);
//平衡树节点
newtree->root = AdjTree(newtree->root);
}
调节平衡
//获取树高度
int getHight(struct BiNode* node)
{
if (NULL == node)
{
return 0;
}
int n = getHight(node->lchild);
int m = getHight(node->rchild);
return n > m ? ++n : ++m;
}
//左旋转
struct BiNode* LeftHand(struct BiNode* data)
{
struct BiNode* temp = data;
data = data->rchild;
data->parent = temp->parent;
struct BiNode* pCurror = data->lchild;
temp->rchild = data->lchild;
if (pCurror)
{
pCurror->parent = temp;
}
data->lchild = temp;
temp->parent=data;
return data;
}
//右旋转
struct BiNode* RightHand(struct BiNode* data)
{
struct BiNode* temp = data;
data = data->lchild;
data->parent= temp->parent;
struct BiNode* pCurror = data->rchild;
temp->lchild = data->rchild;
if (data->rchild)
{
pCurror->parent = temp;
}
data->rchild = temp;
temp->parent = data;
return data;
}
//平衡节点
struct BiNode* AdjTree(struct BiNode* data)
{//判断节点是否为空，为空返回该节点
if (NULL == data)
{
return data;
}
//判断子节点是否有一个不为空，都为空不需要调整
if (NULL != data->lchild || NULL != data->rchild)
{
//初始化栈
void* stack = Init_SeqStack();
//把节点压入栈
Push_SeqStack(stack, data);
//栈中节点不为0就循环
while (Size_SeqStack(stack) > 0)
{//获取栈顶元素
struct BiNode* info = (struct BiNode*)Top_SeqStack(stack);
//判断右子节点是否为空
if (NULL != info->rchild)
{//不为空，压入栈中
Push_SeqStack(stack, info->rchild);
}
//判断左子节点是否为空
if (NULL != info->lchild)
{
//不为空，压入栈中
Push_SeqStack(stack, info->lchild);
}
//弹出栈顶元素
Pop_SeqStack(stack);
//判断节点左右子节点高度差
int l = getHight(info->lchild);
int r = getHight(info->rchild);
//如果左高度-右高度大于1，要进行右旋
if ((l - r) > 1)
{
struct BiNode* d1 = info->lchild;
int ll = getHight(d1->lchild);
int rl = getHight(d1->rchild);
//如果子节点的右节点高度大于左节点高度，要先进行左旋
if (rl > ll)
{//左旋
info->lchild = LeftHand(d1);
}
//右旋
info = RightHand(info);
}
//右高度比左高度大1，要进行左旋
else if ((r - l) > 1)
{
struct BiNode* d1 = info->rchild;
int ll = getHight(d1->lchild);
int rl = getHight(d1->rchild);
//如果左子节点高度大于右子节点高度
if (ll > rl)
{//右旋
info->rchild = RightHand(d1);
}
//左旋
info = LeftHand(info);
}
返回交换后的节点
return info;
}
//销毁栈
Destroy_SeqStack(stack);
}
//不满足条件，返回传入的节点
return data;
}
