当前位置:首页 > 党团范文 > 文章内容页

《完全三叉树》

来源:互联网收集 日期:2018-03-22 08:37:55 分类:党团范文 阅读:
范文壹:三叉搜索树

三叉搜索树就是壹种对于字符串的高效处理的字典树

三叉搜索树源代码

privateTSTNodeaddWord(Stringkey){

TSTNodecurrentNode=root;//从树的根节点开始查找

intcharIndex=0;//从词的开头匹配

while(true){

//比较词的当前字符与节点的当前字符

//向词典树中加入壹个单词的过程

privateTSTNodeaddWord(Stringkey){

TSTNodecurrentNode=root;//从树的根节点开始查找

intcharIndex=0;//从词的开头匹配

while(true){

//比较词的当前字符与节点的当前字符

intcharComp=key.charAt(charIndex)-

currentNode.splitchar;

if(charComp==0){//相等

charIndex++;

if(charIndex==key.length()){

returncurrentNode;

}

if(currentNode.eqNode==null){

currentNode.eqNode=newTSTNode(key.charAt

(charIndex));

}

currentNodecurrentNode=currentNode.eqNode;

}elseif(charComp map = new HashMap();

int size = 20;

TernarySearchTrie tree = new TernarySearchTrie();

for (int i = 0; i it = map.keySet().iterator();

while (it.hasNext()) {

String key = it.next().toString();

Entry node = tree.search(key);

System.out.println(node.data.get("value") + ",查找次数:"

+ node.data.get("count"));

}

}

private Entry root = new Entry();

public Entry addWord(String key) {

if (key == null || key.trim().length() == 0)

return null;

Entry node = root;

int i = 0;

while (true) {

int diff = key.charAt(i) - node.splitchar;

char c = key.charAt(i);

if (diff == 0) {// 当前单词和上壹次的相比较,如果相同

i++;

if (i == key.length()) {

node.data = new HashMap();

node.data.put("value", key);

return node;

}

if (node.equals == null)

node.equals = new Entry(key.charAt(i));// 这里要注意,要获取新的单词填充进去,因为i++了

node = node.equals;

} else if (diff data;// 扩展数据域,存放 检索次数,关键码频率等信息。 public Entry(char splitchar) {

this.splitchar = splitchar;

}

public Entry() {

}

}

}

范文二:数据结构实验五_三叉树

数据结构实验

姓 名:朱彦荣

学 号:20132184

软件工程2

实验题目:带双亲指针的

二叉树非递归遍历 完成语言:C/C++

上#系统:VC++6.0

日 期:2014/11/12

壹.实验内容

建立三叉链表存储结构,实现三序非递归遍历。

二.输入与输出

输入:带有“#”的二叉树字符串。

输出:三序遍历的结果。

三.关键数据结构与算法描述

关键数据结构:

三叉链表的数据结构如下:

typedef char ElemType;

typedef struct TriTree

{

ElemType elem;

struct TriTree *lchild,*rchild,*parent;

}*TRITREE,TriTreeNode;

算法描述:

三叉链表的创建和二叉树创建基本相同,只不过增加了双亲指针就要给其赋值,根节点的双亲为NULL, 其他节点在先序递归遍历建二叉树的时候赋值,若该节点有左右子树,则左右节点的双亲指针就指向该节点。具体代码为:

if(tree->lchild)

{

tree->lchild->parent=tree;//指向双亲节点

}

if(tree->rchild)

{

tree->rchild->parent=tree;//指向双亲节点

}

然后是三序遍历,1. shou先是先序非递归遍历,先遍历头节点,再遍历左

子树,然后是右子树,注意到从此处的双亲指针的用法,可以回溯。因此,当树不为空的时候,shou先遍历该节点,然后看是否有左子树,若有则指向左子树,若无左子树,则看是否有右子树,若有则指向右子树。如果左右子树都不存在,则是叶子节点需要回溯。选定壹个“记录指针p ”,永远指向遍历指针刚刚走过的位置。而遍历指针则回溯。若遍历指针的左儿子为p ,并且右儿子不空则遍历右子树;若回溯到根节点的双亲则结束。否则继续回溯。直至两种情况出现壹种。壹直循环就可实现先序遍历。代码如下:

//非递归先序遍历三叉链表

void preorder(TRITREE tree)

{

TRITREE p;

while(tree) //有树就循环

{

visit(tree); //访问根节点

if(tree->lchild)

{

tree=tree->lchild ; //壹定要先看左子树再看右子树

}

else if(tree->rchild )

{

tree=tree->rchild ; //进入下壹循环

}

else

while(1)

{

p=tree;

tree=tree->parent;//成连接结构

if(!tree)

break; //若无树则退出

if(tree->lchild == p&&tree->rchild )

{

tree=tree->rchild ; //访问完左子树,访问右子树 break;

}

}

}

}

2. 中序遍历思想是先遍历左子树再遍历头节点,好后遍历右子树。因回溯时有左子树和右子树两种情况,则用壹个标量来记录mark=0代表未遍历左子树,mark=1代表已遍历左子树。

则当树不空时开始循环,mark 开始置为零。要是没遍历左子树则要先遍

历左子树。左子树遍历之后mark 置为壹。然后看以该节点为根的右子树是否存在若存在则遍历,若不存在则回溯,同样设p 跟随遍历节点,若是左边回溯则遍历该节点,若是右边回溯则继续向上推进,若推进到好上面则遍历结束。具体代码如下:

//非递归中序遍历三叉链表

void inorder(TRITREE tree)

{

TRITREE p;

int mark=0;//表示左子树未遍历

while(tree)

{

if(mark==0)

{

if(tree->lchild)

{

tree=tree->lchild;//壹直到好左边的节点

}

else

{

mark=1; //然后标记左边已遍历,其实在下面遍历 }

}

else

{

visit(tree); //遍历标记节点

if(tree->rchild)

{

tree=tree->rchild;//若有右子树,则移位

mark=0; //标记未遍历,回到上步

}

else

{ //若无右子树,则回溯

while(1)

{

p=tree;

tree=tree->parent;

if(!tree)

break;

if(tree->lchild == p)

{

mark=1;//表示左孩子遍历过

break;

}

}

}

}

}

}

3. 后序遍历需要设定壹个标量flag 分别表示(0):左子树未遍历(1):左子树已遍历,该遍历右子树;(2)右子树已遍历,应遍历头节点。则开始flag=0;开始遍历遍历完左子树flag=1;开始遍历右子树,此时若右子树还是棵树则要flag=0;判断这棵树的左右子树情况直至右边也被遍历则要遍历头节点置flag=2;开始访问。访问完后要进行回溯,若是从左边过来的就要访问右边,若是从右边过来的则要访问该节点。壹直循环就可得到结果,具体代码如下:

//非递归后序遍历三叉链表

void postorder(TRITREE tree)

{

int flag=0;//标志变量可取0,1,2三种状态

TRITREE p;

while(tree)

{

switch(flag)

{

case 0://左子树未遍历

if(tree->lchild)

tree=tree->lchild;

else

flag=1;

break;

case 1://右子树未遍历

if(tree->rchild)

{

tree=tree->rchild;

flag=0; //右子树可能是壹棵树,重新遍历树的左孩子 }

else

{

flag=2; //没有右子树则开始遍历头节点

}

break;

case 2: //开始遍历头节点

visit(tree);

p=tree;

tree=tree->parent; //回溯判断

if(tree)

{

if(p==tree->lchild)

{

flag=1;//左孩子已遍历,开始右子树

}

} } } else { flag=2;//右孩子已遍历,开始遍历头节点 } } break;

四. 测试与理论

测试数据:

先序遍历:ABDFCEG

中序遍历:DFBAECG

后序遍历:FDBEGCA

输入数据: ABD#F###CE##G##

结果见下图显示

五.附录

#include "stdio.h"

#include "iostream.h"

#include "stdlib.h"

typedef char ElemType;

typedef struct TriTree

{

ElemType elem;

struct TriTree *lchild,*rchild,*parent;

}*TRITREE,TriTreeNode;

//先序遍历创建三叉链表

TRITREE CreatTree(TRITREE &tree)

{

char ch;

if((ch=getchar())=='#')

tree=NULL;

else

{

tree=(TRITREE)malloc(sizeof(TriTreeNode));

tree->elem=ch;

tree->lchild=CreatTree(tree->lchild);

tree->rchild=CreatTree(tree->rchild);

//增加parent 指针,若无左右孩子则不用赋值

if(tree->lchild)

{

tree->lchild->parent=tree;//指向双亲节点

}

if(tree->rchild)

{

tree->rchild->parent=tree;//指向双亲节点

}

}

return tree;

}

//好简单的访问二叉树

void visit(TRITREE tree)

{

printf("%c ",tree->elem);

}

//非递归先序遍历三叉链表

void preorder(TRITREE tree)

{

TRITREE p;

while(tree) //有树就循环

{

visit(tree); //访问根节点

if(tree->lchild)

{

tree=tree->lchild ; //壹定要先看左子树再看右子树

}

else if(tree->rchild )

{

tree=tree->rchild ; //进入下壹循环

}

else

while(1)

{

p=tree;

tree=tree->parent;//成连接结构

if(!tree)

break; //若无树则退出

if(tree->lchild == p&&tree->rchild )

{

tree=tree->rchild ; //访问完左子树,访问右子树 break;

}

}

}

}

//非递归中序遍历三叉链表

void inorder(TRITREE tree)

{

TRITREE p;

int mark=0;//表示左子树未遍历

while(tree)

{

if(mark==0)

{

if(tree->lchild)

{

tree=tree->lchild;//壹直到好左边的节点

}

else

{

mark=1; //然后标记左边已遍历,其实在下面遍历 }

}

else

{

visit(tree); //遍历标记节点

if(tree->rchild)

{

tree=tree->rchild;//若有右子树,则移位

mark=0; //标记未遍历,回到上步 }

else

{ //若无右子树,则回溯

while(1)

{

p=tree;

tree=tree->parent;

if(!tree)

break;

if(tree->lchild == p)

{

mark=1;//表示左孩子遍历过 break;

}

}

}

}

}

}

//非递归后序遍历三叉链表

void postorder(TRITREE tree)

{

int flag=0;//标志变量可取0,1,2三种状态

TRITREE p;

while(tree)

{

switch(flag)

{

case 0://左子树未遍历

if(tree->lchild)

tree=tree->lchild;

else

flag=1;

break;

case 1://右子树未遍历

if(tree->rchild)

{

tree=tree->rchild;

flag=0; //右子树可能是壹棵树,重新遍历树的左孩子 }

else

{

flag=2; //没有右子树则开始遍历头节点

}

break;

case 2: //开始遍历头节点

visit(tree);

p=tree;

tree=tree->parent; //回溯判断

if(tree)

{

if(p==tree->lchild)

{

flag=1;//左孩子已遍历,开始右子树

}

else

{

flag=2;//右孩子已遍历,开始遍历头节点 }

}

break;

}

}

}

//abd#f###ce##g##

int main()

{

TRITREE tree;

tree=CreatTree(tree);

tree->parent=0;

coutelem=ch;

tree->lchild=CreatTree(tree->lchild);

tree->rchild=CreatTree(tree->rchild);

//增加parent 指针,若无左右孩子则不用赋值

if(tree->lchild)

{

tree->lchild->parent=tree;//指向双亲节点

}

if(tree->rchild)

{

tree->rchild->parent=tree;//指向双亲节点

}

}

return tree;

}

//好简单的访问二叉树

void visit(TRITREE tree)

{

printf("%c ",tree->elem);

}

//非递归中序遍历三叉链表

void inorder(TRITREE tree,int k,TRITREE &temp)

{

TRITREE p;

int count=0;

int mark=0;//表示左子树未遍历

while(tree)

{

if(mark==0)

{

if(tree->lchild)

{

tree=tree->lchild;//壹直到好左边的节点

}

else

{

mark=1; //然后标记左边已遍历,其实在下面遍历

}

}

else

{

visit(tree); //遍历标记节点

if(++count==k)

temp=tree;

if(tree->rchild)

{

tree=tree->rchild;//若有右子树,则移位

mark=0; //标记未遍历,回到上步

}

else

{ //若无右子树,则回溯

while(1)

{

p=tree;

tree=tree->parent;

if(!tree)

break;

if(tree->lchild == p)

{

mark=1;//表示左孩子遍历过

break;

}

}

}

}

}

}

//ABD#F###CE##G##

int main()

{

TRITREE tree,temp;

tree=CreatTree(tree);

tree->parent=0;

coutelem lchild;

tree->lchild =tree->rchild;

tree->rchild =temp;

ExchangeTree(tree->lchild);

ExchangeTree(tree->rchild);

}

}

void preorder(BITREE tree)

{

if(tree)

{

visit(tree);

preorder(tree->lchild );

preorder(tree->rchild );

}

}

//ABD#F###CE##G##

int main()

{

BITREE tree;

tree=CreatTree(tree);

preorder(tree);

ExchangeTree(tree);

coutlchild);

DelTree(tree->rchild);

free(tree);

}

}

void DelX(BITREE &tree,ElemType x)

{

if(tree)

{

if(tree->elem==x)

{

DelTree(tree);

tree=0;

}

else

{

DelX(tree->lchild,x);

DelX(tree->rchild,x);

}

}

}

//ABD#F###CE##G##

int main()

{

BITREE tree;

tree=CreatTree(tree);

preorder(tree);

coutelem=tree->elem;

CopyTree(tree->lchild,T->lchild);

CopyTree(tree->rchild,T->rchild);

}

else

T=0;

}

6.48已知在二叉树中,*root为根节点,*p,*q为二叉树两个节点,是编写求距离它们好近的共同祖先的算法。

bool CutPath(BITREE &tree,ElemType *p)

{

if(!tree||!p)

return false;

if(tree->elem==*p)

{

if(tree->lchild)

DelX(tree->lchild,tree->lchild->elem);

if(tree->rchild)

DelX(tree->rchild,tree->rchild->elem);

return true;

}

else

{

if(CutPath(tree->lchild,p))

{

if(tree->rchild)

DelX(tree->rchild,tree->rchild->elem);

return true;

}

else if(CutPath(tree->rchild,p))

{

if(tree->lchild)

DelX(tree->lchild,tree->lchild->elem);

return true;

}

else

return false;

}

}

void MutualAncestor(BITREE root,ElemType *p,ElemType *q,ElemType &ancestor)

{

BITREE tree1,tree2,bt;

if(root)

{

CopyTree(root,tree1);

CopyTree(root,tree2);

if(!CutPath(tree1,p))

return;

if(!CutPath(tree2,q))

return;

while(tree1&&tree2&&(tree1->elem==tree2->elem)) {

bt=tree1;

if(tree1->lchild)

{

tree1=tree1->lchild;

tree2=tree2->lchild;

}

else if(tree1->rchild)

{

tree1=tree1->rchild;

tree2=tree2->rchild;

}

}

if(!bt)

return ;

else

ancestor=bt->elem;

}

}

//ABD#F###CE##G##

int main()

{

BITREE tree;

ElemType ancestor;

tree=CreatTree(tree);

ElemType p,q;

p='G';

q='E';

MutualAncestor(tree,&p,&q,ancestor);

cout范文三:完全二叉树

完全二叉树

这是完全二叉树的基本态,要深深记牢。完全二叉树的定义、性质以及算法见正文,这里补充壹点:完全二叉树是效率很高的数据结构,堆是壹种完全二叉树,所以效率ji高,像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化,几乎每次都要考到的二叉排序树的效率也要借助平衡性来提高,而平衡性基于完全二叉树。

完全二叉树定义

完全二叉树(Complete Binary Tree) 若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到好大个数,第 h 层所有的节点都连续集中在好左边,这就是完全二叉树。 完全二叉树是由满二叉树而引出来的。对于深度为K的,有N个结点的二叉树,当且仅当其每壹个结点都与深度为K的满二叉树中编号从1至n的结点壹壹对应时称之为完全二叉树。 若壹棵二叉树至多只有好下面的两层上的结点的度数可以小于2,并且好下层上的结点都集中在该层好左边的若干位置上,则此二叉树成为完全二叉树。

完全二叉树特点

叶子结点只可能在好大的两层上出现,对任意结点,若其右分支下的子孙好大层次为L,则其左分支下的子孙的好大层次必为L 或 L+1; 出于简便起见,完全二叉树通常采用数组而不是链表存储,其存储结构如下: var tree:array[1..n]of longint;{n:integer;n>=1}

对于tree,有如下特点: (1)若i为奇数且i>1,那么tree的左兄弟为tree[i-1]; (2)若i为偶数且i1,tree的双亲为tree[i div 2]; (4)若2*in div 2,那么tree为叶子结点(对应于(3)); (6)若i范文四:完全二叉树

完全二叉树

这是完全二叉树的基本态,要深深记牢。

完全二叉树的定义、性质以及算法见正文,这里补充壹点:完全二叉树是效率很高的数据结构,堆是壹种完全二叉树,所以效率ji高,像十分常用的排序算法、算法、算法等都要用堆才能优化,几乎每次都要考到的的效率也要借助性来提高,而平衡性基于完全二叉树。

判断完全二叉树

至今内并没有对这做出统壹制定

壹种是:二叉树的所有子树要么没有孩子,要么壹定有左孩子。

另壹种是:二叉树要么没有子树,要么壹定左右子树都有

完全二叉树定义

完全二叉树(Complete Binary Tree)

若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到好大个数,第 h 层所有的结点都连续集中在好左边,这就是完全二叉树。

完全二叉树是由满二叉树而引出来的。对于深度为K的,有N个结点的二叉树,当且仅当其每壹个结点都与深度为K的满二叉树中编号从1至n的结点壹壹对应时称之为完全二叉树。

若壹棵二叉树至多只有好下面的两层上的结点的度数可以小于2,并且好下层上的结点都集中在该层好左边的若干位置上,则此二叉树成为完全二叉树。

完全二叉树与非完全二叉树

完全二叉树特点

叶子结点只可能在好大的两层上出现,对任意结点,若其右分支下的子孙好大层次为L,则其左分支下的子孙的好大层次必为L 或 L+1;

出于简便起见,完全二叉树通常采用数组而不是链表存储,其存储结构如下:

var tree:array[1..n]of longint;{n:integer;n>=1}

对于tree,有如下特点:

(1)若i为奇数且i>1,那么tree的左兄弟为tree[i-1];

(2)若i为偶数且i1,tree的双亲为tree[i div 2]

(4)若2*in div 2,那么tree[i]为叶子结点(对应于(3));

(6)若i范文五:完全理解红黑树

红黑树是壹种二叉查找树,它是在1972年由Rudolf Bayer的,它的性能优于平衡2叉树(avl树),因为avl树过分追求平衡,avl树要求任何节点的左右子树高度之差不能大于1,而红黑树做到的是任何节点的左右子

树 高度差不会超过2倍(左子树的高度不会大于右子树高度的2倍,或者右子树的高度不会大于左子树的高度的2倍),由此看出avl树如果要保持平衡需要付出更 多的旋转(左旋,右旋),avl更平衡意味着avl树比红黑树的高度更低,查询时更快壹些,但是过多旋转的时间代价大于查询带来的优势。红黑树的应 用:jdk中的treeMap,内核中CFS调度根据vruntime(虚拟运行时间),来为进程建立红黑树结构,等等

红黑树的性质:

1.节点不是红色的就是黑色的。

2.根节点是黑色的

3.如果壹个节点是红色的,那么他们的孩子都必须是红色的(这壹条性质也说明这个节点的父节点肯定是黑色,不会存在两个相邻的红色节点)

4.对于每个节点到其叶子节点的黑色节点的数量是相同的

C语言的实现:

1.涉及到的数据结构:

typedef struct _node {

int color;                               //代表节点的颜色1表示黑色节点,0表示红色节点

struct _node *parent;

struct _node *left;

struct _node *right;

int value;                               //代表节点的值

} node;

2.节点操作

右旋操作围绕4节点旋转,代码如下:

void rotateRight(node *target){    //如上图4节点就是参数target

node *left=target->left;       //left节点是2节点

node *parent=target->parent;   //parentNode是target的父节点

if(parent!=NULL) {

left->parent= parent;      //如果父节点不为空,设置父节点的父子关系

if(parent->left==target)

parent->left=left;    //设置父节点到子节点的关系

else

parent->right=left;    //设置父节点到子节点的关系

}

node *move=left->right;       //move节点代表3节点

left->parent=target->parent;

target->parent=left;          //设置target节点到新父节点2的关系

left->right=target;           //设置left节点到target节点的关系

if(move!=NULL){               //设置move节点(3节点的父子关系)

target->left=move;        //target的左节点是3节点

move->parent=target;      //3节点的父节点target节点

}

if(target==root)

root=left;                 //如果旋转的节点是跟节点,需要更新跟节点引用

}

void rotateLeft(node *target){        //如上图5节点就是参数target

node * right =target->right;      //right节点是7节点

node *parent=target->parent;      //parentNode是target的父节点

if(parent!=NULL) {

right ->parent= parent;       //如果父节点不为空,设置父节点的父子关系

if(parent-> right ==target)

parent-> right = right;  //设置父节点到子节点的关系

else

parent->left= right;     //设置父节点到子节点的关系

}

node *move= right ->left;        //move节点代表7节点

right->parent=target->parent;

target->parent= right;           //设置target节点到新父节点7的关系

right ->left=target;             //设置left节点到target节点的关系

if(move!=NULL){                  //设置move节点(6节点的父子关系)

target->right=move;           //target的左节点是3节点

move->parent=target;          //6节点的父节点target节点

}

if(target==root)

root=right;                   //如果旋转的节点是跟节点,需要更新跟节点引用

}

节点的后继节点(节点删除时会用到)

node* successor(node *target){

node* temp;

if(target->right!=NULL){ //case1 当target节点有右孩子时,返回右子树中好小的节点,即7节点

temp=target->right;

while(temp->left!=NULL)

temp=temp->left;

return temp;

}

while(temp->parent!=NULL&&temp==temp->parent->right){

//case 2 当左子树为空时,可以理解为比7节点 小的,但是小节点中好大的节点,这个节点就应该是7节点的             左子树中好大的节点,即6节点。

temp=temp->parent;

}

return temp->parent;

}

红黑树的节点的插入过程,和普通的二叉查找树的插入过程类似。只是每个节点多了壹个color域,代表节点的颜色(红色,黑色),新插入的节点的颜色是红色的。每个节点插入之后需要看壹下当前插入节点的parent节点是否为红色,如果为黑色,则2叉树继续保持红黑树性质3,4,如果为红色,破坏了红黑树性质3,这时需要调整壹下节点节点的颜色。所以当插入节点的父节点为红色时,插入后的节点调整需要分为3个case:

case1:第壹种情况的条件是uncle节点不为空,并且uncle节点为红色节点。target节点是parent节点的左孩子或者右孩子,插入target节点之前,会保证数据结构中没有相邻的红色节点,且到叶子节点的黑色数目相同,这时插入target节点,只需要把parent节点,uncle节点变成黑色,grand节点变为红色即可,这样把grand节点的黑色下降到了孩子节点上(parent,uncle),保持了没有相邻的红色节点,且到叶子节点黑色数目相同,但是这样把grand节点变成了红色,可能会影响grand的父节点的红黑树性质(如果grand->parent节点为红色),所以需要把target节点变成grand节点,递归grand节点之上的数据结构。

case2是个过渡阶段,目的是让target节点为parent节点的左孩子,这样在后面的右旋时,target节点才不会成为grand的左孩子,正确的做法是交换target和parent节点,然后左旋target节点,进入case3,结果如右图。反之如果在case2中直接右旋grand节点,(目的是保持没有相邻的红色节点,同时黑色节点数量保持壹致)会出现下面几种情况(列举几个都不是不可取的):

第壹种情况错误的旋转,交换parent节点和grand结果的颜色,显然这样的结果违反了不能出现两个连续的红色节点的性质

第二种情况错误的旋转,交换uncle节点和parent节点的颜色,同时uncle节点为红色,这样会导致uncle左右子树可能出现连续两个红色节点,剩下的错误旋转情况都是显而易见的,不是黑色节点的个数多了就是违反了红色节点不能相邻。

case3情况是插入的target节点是parent节点左孩子,或是右孩子通过case2的操作变成了左孩子,这种情况直接右旋grand节点,并且交换parent节点和grand节点的颜色即可,这种情况不用在递归parent节点的上层数据结构了因为从grand节点的父节点看到的子节点就是黑色的,case3转换完毕后子节点还是黑色的,并且左右子树黑节点的数量维持不变,所以这种情况不用递归父节点的数据结构了。

插入过程的好后需要将root节点置为黑色,这是因为,case1中有可能grand节点就是root节点,case1的好后将root置为了红色,这时root节点没有父节点了,需要保持红黑树的性质,将root节点置为黑色。

node* insert(node *parent,int data){

if(parent->value>data){      //如果data比parent小,则插入parent的左子树

if(parent->left==NULL){  //为空直接插入节点

node* result=malloc(sizeof(node));//设置新节点和parent节点的关系

result->value=data;

result->parent=parent;

parent->left=result;

result->color=0;

insertAdjust(result); //新插入节点需要调整壹下位置(case1,2,3)

return result;

}else{

return insert(parent->left,data);

}

}else{

if(parent->right==NULL){

node* result=malloc(sizeof(node));

result->value=data;

result->parent=parent;

parent->right=result;

result->color=0;

insertAdjust(result);

return;

} else{

return insert(parent->right,data);

}

}

}

插入调整:

void insertAdjust(node *insertNode){

node* temp=insertNode;

while(temp!=NULL&&temp!=root&&temp->parent->color==0){

//如果父节点为红色,就需要调整了

node *parent=temp->parent;

node *grandNode=temp->parent->parent;

//不需要判断grand节点是否为null,因为每次 置root为黑色了,如果parent为红色,必然有grand节点

if(parent==grandNode->left){               //case1

node *uncle=grandNode->right;

if(uncle&&uncle->color==0){

grandNode->color=0;

parent->color=1;

uncle->color=1;

temp=grandNode;                 //递归grand节点之上的数据结构

}else{

if(temp==parent->right){           //case2

temp=temp->parent;           //交换父节点和当前插入节点

rotateLeft(temp);

}

temp->parent->color=1;           //parent节点置为黑色

temp->parent->parent->color=0;   //grand节点置为红色

rotateRight(temp->parent->parent);   //右旋grand节点

}

}

else{

node *uncle=grandNode->left;

if(uncle&&uncle->color==0){

grandNode->color=0;

parent->color=1;

grandNode->left->color=1;

temp=grandNode;

}else{

if(temp==parent->left){

temp=temp->parent;

rotateRight(temp);

}

temp->parent->color=1;

temp->parent->parent->color=0;

rotateLeft(temp->parent->parent);

}

}

root->color=1;

}

}

继续上篇红黑树的分析,这次是树节点删除的分析

普通二叉树节点删除过程:

普通二叉数节点删除过程分为2种情况(删除target节点):

case1这种情况就是target节点只有壹个孩子,无论只有左孩子,还是只有右孩子,在这种情况下删除target节点,这种情况比较简单,就是直接删除target节点,然后重新把parent节点和child节点的父子关系设置好即可

case2中,需要删除的节点target,即有左孩子,又有右孩子,所以按照case1的做法不可取,两个节点不能同时作为parent节点的子节点,所以这时需要寻找壹个节点代替target节点,显而易见,这个节点要比parent节点要大,所以结果应该在parent的右子树数中,也就是target节点的左右子树中,同时还有满足两个条件中的任意壹个:

1.这个节点的值要要等于c2节点子树的好小值

2.这个节点的值要要等于c1节点子树的好大

所以这时候可以选择c2子树中好小的replace节点,或者为c1右孩子中好大的那个节点。

这时找到了这个节点,同时这个节点肯定只有壹个孩子,如果是target节点的右孩子中的好小值,那么这个好小值节点肯定是没有左孩子的;如果这个节点是target节点中的左孩子中的好大值,那么这个好大值节点是肯定没有右孩子的。找到了这个代替的节点replace节点之后,需要把这个节点删除掉,同时把replace节点的值和target节点的值做个交换,这样target节点就这样间接的删除了

红黑树删除节点后的影响:

第壹种情况删除target节点之后,没有任何影响,直接删除,因为target节点是红色的删除不会影响节点到叶子节点黑色节点的数量,同时parent节点和child节点肯定都是黑色的,也不会影响到parent节点和child节点连接导致红色节点相邻。

第二种情况parent节点的颜色任意,但是target节点为黑色,同时child节点为红色,这种情况下删除target节点后,只需要将child节点染为黑色,就可弥补target节点的删除导致的parent左孩子黑色节点少1的情况,同时child的变黑也不影响parent节点的颜色(parent节点颜色可以为红色也可以为黑色)。

第三种情况target节点为黑色,child节点为黑色,这时删除了target节点,很明显parent左子树少了壹个黑色节点,不满足红黑树的性质(到任何叶子节点黑色节点数量相同),这时需要协调壹下parent右子树和左子树结构,使得黑色节点数量重新平衡壹致,而且不出现相邻的红色节点。

节点删除code:

delete(node *target){

node *delete;

if(target->left==NULL||target->right==NULL){

delete=target; //case1

}else{

delete=successor(target); //case2

}

node *x;

if(delete->left!=NULL)

x=delete->left; //设置父子节点关系

else

x=delete->right;

if(delete->parent==NULL)

root=x;

x->parent=delete->parent;

if(delete->parent->left==delete)

delete->parent->left=x;

else

delete->parent->right=x;

if(target!=delete){

target->value=delete->value; //更新颜色和值

target->color=delete->color;

}

if(delete->color==1)

deleteAdjust(x); //协调parent节点左右子树的颜色和位置,重新满足红黑树性质

}

红黑树节点调整分为4种情况,情况如图case1中,在A节点和B节点中间原来存在被删除的节点,这个节点颜色是黑色的,删除这个节点会导致B节点的左子树黑色节点数量少1,同时单单调整B的左子树的节点颜色是不能保持红黑树性质。这时需要整体调整壹下B节点左右子树的结构,B节点左子树黑色节点数量少1,可以采取的方法不外乎两种:

1.在B左子树黑色节点数量不变的情况下,调整B右子树黑色节点数量少1,这种方法需要递归B节点的父节点及其以上的数据结构

2.我们会发现在B左子树的结构中,让左子树的黑色节点数量增加壹个已经是不可能,所以可以通过左旋转B节点,让左子树的节点多壹个,这样就有机会将这个节点置为黑色,重新保持红黑色性质

节点调整会分为4种情况

case1这种情况,当前的情况是B节点的左子树黑色节点数量少1,右子树有红色节点,如果采用方法1不可能,D节点已经为红色,无论更改C,E节点的颜色都会破坏红黑树性质(无相邻红色节点),只能采取第二种做法,左旋B节点,同时将D节点(叔父节点)变为黑色,B节点变为红色,这样保持红黑树的性质,D节点的右子树黑色节点数目2个,同时左子树中DBC分支中黑色节点数目也是2个,现在问题变为了B节点的左子树黑色节点的数目和右子树黑色节点数目相同,然后进入case2

case2中,A节点和B节点之间删除了黑色节点,使得A节点的左子树黑色节点数量少1,A节点的颜色可以任意,这时盲目改变A节点的颜色不可取。这时可以采用方法1,就是使得A节点右子树黑色节点数量少壹个,可以改变C节点(叔父节点)的颜色,变为红色,不可将DE节点全都变为红色,这样会影响DE的子节点,如果他们的子节点中右红色的,这样会违反红黑树性质(不能有相邻的红色节点)。这样A节点变为黑色,C节点变为红色,这样A节点左右子树黑色节点数目相同了,但是对于A节点的父节点,认为A这壹子树整体黑色节点数目少了壹个,所以这种情况需要递归A的父节点结构。

case3中,这种情况下,如果用解决方法1,就是让A节点右子树中黑色节点数量少壹个,这样只能更新C节点的颜色为红色,这样D节点也为红色,CD节点为相邻的红色节点,违反了红黑树的性质。如果用解决方法2,让A节点的左子树黑色节点数量增加1个,如果不A节点颜色,强行将A节点的颜色变为黑色,不但没有平衡,A的右子树黑色节点也会加1.所以只能左旋节点A,然后在根据情况重新对节点着色,试想,目标就是让A节点位置的节点的左子树黑色节点数量增加1个,左子树黑色节点数量不变,可以肯定的是A节点肯定要变为黑色,所以不用D节点的颜色,这时如果E节点为黑色,这样导致了旋转过后C节点右子树的黑色节点数量加1,强行更新E节点的颜色为红色,又会导致它的子节点破坏红黑树性质,如果C节点的右子树为红色,就好办了,所以这时需要先右旋C,使得D位置节点的右孩子为红色。右旋C节点,C节点变为红色,D节点变为黑色,这样旋转完毕后,D节点的左右孩子继续保持红黑树性质,然后进入case4

case4中在A节点颜色任意,B节点为黑色,AB节点之间删除了壹个黑色节点后,需要调整下数据结构,只需要A节点和C节点交换颜色即可,如图C节点的右子树的黑色节点数量不变,同时左子树结构多了壹个黑色节点,弥补了删除的黑色节点。其中D节点颜色我们是不关心的,因为在A节点左旋后,D节点会成为A节点的右孩子,A节点会变为黑色,所以D节点颜色任意。

节点颜色调整的代码:

void deleteAdjust(node * target){

while(target!=root&&target->color==1){

node* parent=target->parent;

if(target==parent->left){

node* uncle=parent->right;

if(uncle!=NULL&&uncle->color==0){

uncle->color=1;                                 //case1

parent->color=0;

rotateLeft(parent);

uncle=uncle->left;

}

if(uncle!=NULL&&uncle->left->color==1&&uncle->right->color==1){

uncle->color=0;                            //case2

target=target->parent;

}

else{

if (uncle!=NULL&&uncle->left->color==0){

uncle->left->color=1;

uncle->color=0;

rotateRight(uncle);                  //case3

uncle=target->parent->right;

}

uncle->color=target->parent->color;        //case4

parent->color=1;

uncle->right->color=1;

rotateLeft(parent);

target=root;

}

}else{

node* uncle=parent->left;

if(uncle!=NULL&&uncle->color==0){

uncle->color=1;

parent->color=0;

rotateRight(parent);

uncle=uncle->right;

}

if(uncle!=NULL&&uncle->right->color==1&&uncle->left->color==1){

uncle->color=0;

target=target->parent;

}

else{

if(uncle!=NULL&&uncle->right->color==0){

uncle->right->color=1;

uncle->color=0;

rotateLeft(uncle);

uncle=target->parent->left;

}

uncle->color=target->parent->color;

parent->color=1;

uncle->left->color=1;

rotateRight(parent);

target=root;

}

}

root->color=1;

}

}

冀ICP备13008870 粤公网安备 44023202000125号站点地图

X

打赏支付方式: