有了遞歸實(shí)現(xiàn)為啥還要用非遞歸呢？你會(huì)不會(huì)有疑惑缭乘？如果有沐序，請(qǐng)接著看琉用。
函數(shù)的調(diào)用需要用到棧堕绩，一個(gè)應(yīng)用分配到的棧空間一般為1M大小邑时，在數(shù)據(jù)很大的情況會(huì)造成棧溢出奴紧，所以要少用遞歸。
不用遞歸實(shí)現(xiàn)的原理是模擬棧的運(yùn)行機(jī)制------先進(jìn)后出晶丘，如果這個(gè)不會(huì)的話黍氮，可以看我寫(xiě)的數(shù)組模擬棧（現(xiàn)在還沒(méi)寫(xiě)）。
頭文件
#ifdef __cplusplus
extern "C" {
#endif
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//bool
#include <stdbool.h>
//字節(jié)封裝的模擬棧
#include "SeqStack.h"
/*
*自定義結(jié)構(gòu)體必須包含BiNode結(jié)構(gòu)體,且位于結(jié)構(gòu)體最上方
*struct Person
*{
* struct BiNode data;
* int age;
};
*增加必須提供返回值int型的比較函數(shù),參數(shù)為(void* ,void*),函數(shù)內(nèi)強(qiáng)轉(zhuǎn)自己定義的結(jié)構(gòu)體
*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;
*}
*遍歷需要提供遍歷函數(shù)浅浮，參數(shù)為void*沫浆，函數(shù)內(nèi)強(qiáng)轉(zhuǎn)自己定義的結(jié)構(gòu)體
*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);
*}
*
*/
//定義結(jié)構(gòu)體
struct BiNode {
//父節(jié)點(diǎn)用于刪除
struct BiNode* parent;
struct BiNode* rchild;
struct BiNode* lchild;
//用于遍歷
bool flag;
};
//初始化樹(shù)，外部調(diào)用
void* Init_BBTree();
//插入根數(shù)據(jù)滚秩，外部調(diào)用
void Insert_BBTree(void* tree,void *data,int(*compare)(void *,void *));
//返回樹(shù)高度专执，內(nèi)部使用
int getHight(struct BiNode* node);
//左旋,內(nèi)部使用
struct BiNode* LeftHand(struct BiNode* data);
//右旋,內(nèi)部使用
struct BiNode* RightHand(struct BiNode* data);
//平衡樹(shù)節(jié)點(diǎn),內(nèi)部使用
struct BiNode* AdjTree(struct BiNode* data);
//遍歷二叉樹(shù)
void foreachTree(void* tree, void(*myprint)(void*));
//刪除節(jié)點(diǎn)，外部使用
void RemoveTree(void* tree, void* data,int(*compare)(void* ,void*));
//銷毀郁油，外部使用
void DestroyTree(void* tree);
#ifdef __cplusplus
}
#endif
初始化
void* Init_BBTree()
{//開(kāi)辟一個(gè)新空間
struct ABLTree* tree = malloc(sizeof(struct ABLTree));
//開(kāi)辟失敗返回NULL
if (NULL == tree)
{
return NULL;
}//初始化根節(jié)點(diǎn)為NULL
tree->root = NULL;
//返回空間指針
return tree;
}
插入數(shù)據(jù)
void Insert_BBTree(void* tree, void* data, int(*compare)(void*, void*))
{//判斷參數(shù)是否為空
if (NULL == tree)
{
return;
}
if (NULL == data)
{
return;
}
if (NULL == compare)
{
return;
}
//強(qiáng)轉(zhuǎn)
struct ABLTree* newtree = (struct ABLTree*)tree;
//判斷根節(jié)點(diǎn)是否為空本股，若為空攀痊，把數(shù)據(jù)賦值給根節(jié)點(diǎn)，并返回
if (NULL == newtree->root)
{
newtree->root = data;
return;
}
//不為空拄显，初始化一個(gè)棧
void* stack = Init_SeqStack();
//把根節(jié)點(diǎn)壓入棧中
Push_SeqStack(stack, newtree->root);
//判斷棧中是否還有數(shù)據(jù)
while (Size_SeqStack(stack) > 0)
{//獲取棧頂元素
struct BiNode* info = (struct BiNode*)Top_SeqStack(stack);
//彈出棧頂元素
Pop_SeqStack(stack);
//判斷棧頂元素與數(shù)據(jù)的大小
if(compare(info,data)>0)
{//如果棧頂元素大苟径，判斷棧頂元素的左子節(jié)點(diǎn)是否為空
if (NULL == info->lchild)
{//為空，賦值并返回
info->lchild = data;
info->lchild->parent = info;
break;
}
//不為空躬审，把左子節(jié)點(diǎn)壓入棧中,并中斷當(dāng)前循環(huán)棘街，進(jìn)入下次循環(huán)
Push_SeqStack(stack, info->lchild);
continue;
}
else
{//如果棧頂元素小，判斷棧頂元素的右子節(jié)點(diǎn)是否為空
if (NULL == info->rchild)
{//為空盒件，賦值并返回
info->rchild = data;
info->rchild->parent = info;
break;
}
//不為空蹬碧，把右子節(jié)點(diǎn)壓入棧中,并中斷當(dāng)前循環(huán)，進(jìn)入下次循環(huán)
Push_SeqStack(stack, info->rchild);
continue;
}
}
//銷毀棧
Destroy_SeqStack(stack);
//平衡樹(shù)節(jié)點(diǎn)
newtree->root = AdjTree(newtree->root);
}
調(diào)節(jié)平衡
//獲取樹(shù)高度
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;
}
//左旋轉(zhuǎn)
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;
}
//右旋轉(zhuǎn)
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;
}
//平衡節(jié)點(diǎn)
struct BiNode* AdjTree(struct BiNode* data)
{//判斷節(jié)點(diǎn)是否為空炒刁，為空返回該節(jié)點(diǎn)
if (NULL == data)
{
return data;
}
//判斷子節(jié)點(diǎn)是否有一個(gè)不為空恩沽，都為空不需要調(diào)整
if (NULL != data->lchild || NULL != data->rchild)
{
//初始化棧
void* stack = Init_SeqStack();
//把節(jié)點(diǎn)壓入棧
Push_SeqStack(stack, data);
//棧中節(jié)點(diǎn)不為0就循環(huán)
while (Size_SeqStack(stack) > 0)
{//獲取棧頂元素
struct BiNode* info = (struct BiNode*)Top_SeqStack(stack);
//判斷右子節(jié)點(diǎn)是否為空
if (NULL != info->rchild)
{//不為空，壓入棧中
Push_SeqStack(stack, info->rchild);
}
//判斷左子節(jié)點(diǎn)是否為空
if (NULL != info->lchild)
{
//不為空翔始，壓入棧中
Push_SeqStack(stack, info->lchild);
}
//彈出棧頂元素
Pop_SeqStack(stack);
//判斷節(jié)點(diǎn)左右子節(jié)點(diǎn)高度差
int l = getHight(info->lchild);
int r = getHight(info->rchild);
//如果左高度-右高度大于1罗心，要進(jìn)行右旋
if ((l - r) > 1)
{
struct BiNode* d1 = info->lchild;
int ll = getHight(d1->lchild);
int rl = getHight(d1->rchild);
//如果子節(jié)點(diǎn)的右節(jié)點(diǎn)高度大于左節(jié)點(diǎn)高度，要先進(jìn)行左旋
if (rl > ll)
{//左旋
info->lchild = LeftHand(d1);
}
//右旋
info = RightHand(info);
}
//右高度比左高度大1城瞎，要進(jìn)行左旋
else if ((r - l) > 1)
{
struct BiNode* d1 = info->rchild;
int ll = getHight(d1->lchild);
int rl = getHight(d1->rchild);
//如果左子節(jié)點(diǎn)高度大于右子節(jié)點(diǎn)高度
if (ll > rl)
{//右旋
info->rchild = RightHand(d1);
}
//左旋
info = LeftHand(info);
}
返回交換后的節(jié)點(diǎn)
return info;
}
//銷毀棧
Destroy_SeqStack(stack);
}
//不滿足條件渤闷，返回傳入的節(jié)點(diǎn)
return data;
}
