二叉树

二叉树的逻辑结构

二叉树的定义

二叉树是n（n$\ge$0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

二叉树特点

1.每个结点最多有两颗子树。

2.二叉树是有序的，其次序不能任意颠倒。

注意：二叉树和树是两种树结构。

 

分类

了解好：斜树，满二叉树，完全二叉树

 

二叉树的基本性质

性质1:二叉树的第i层上最多有$2^{i-1}$个结点（i$\ge$1）

性质2:一棵深度为k的二叉树中，最多有$2^{k-1}$个结点，最少有k个结点。

性质3:在一棵二叉树中，如果叶子结点数为$n_0$，度为2的结点数为$n_2$，则有：$n_0=n_2+1$。

性质4:具有n个结点的完全二叉树的深度为$\left\lfloor\log _{2} n\right\rfloor+1$。

性质5:对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（$1\le i \le n$）的结点(简称为结点i），有：
（1）如果i>1，则结点的双亲结点的序号为i/2；如果i=1，则结点是根结点，无双亲结点。

（2）如果$2i \le n$，则结点i的左孩子的序号为2i；如果2i>n，则结点i无左孩子。

（3）如果$2i+1\le n$，则结点i的右孩子的序号为2i+1；如果$2i+1>n$，则结点无右孩子。

 

顺序存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置（下标）应能体现结点之间的逻辑关系-父子关系。

完全二叉树的顺序储存

二叉树编号

按照完全二叉树编号

可以编号为：

没有编号的位置直接存储为空。

二叉链表

data	数据域，存放该结点的数据信息
Ichild	左指针域，存放指针指向左孩子的指针
rchild	右指针域，存放指针指向右孩子的指针

class tree
{
    public:
    int data;
    class tree* Ichild;
    class tree* rchild;
}
typedef class tree node;
typedef node *btree;

 

二叉树的遍历

二叉树的组成：根结点D，左子树L，右子树R。

如果限定先左后右，则二叉树遍历方式有三种：

前序（Preorder）：DLR

中序（Inorder）：LDR

后序（Postorder）：LRD

如下图所视

中序遍历

1.遍历左子树
2.遍历（或访问）树根
3.遍历右子树

中序遍历为：FDHGIBEAC

void Inorder(btree ptr)
{
if (ptr != NULL)
	{
	Inorder(ptr->left);   //遍历左子树
	cout<<ptr ->data;     //遍历并打印树根
	Inorder(ptr->right);   //遍历右子树
	}
}

 

后序遍历

1.遍历左子树
2.遍历右子树
3.遍历树根

中序遍历为：FHIGDEBCA

void Postorder (btree ptr)
{
if (ptr != NULL)
{
	Postorder(ptr->left);     //遍历左子树
	Postorder(ptr->right);    //遍历右子树
	cout<<ptr->data;          //遍历并打印树根
}

 

前序遍历

1.遍历树根
2.遍历左子树
3.遍历右子树

中序遍历为：ABDFGHIEC

void Preorder(btree ptr)
{
if (ptr != NULL)
	{
    cout<<ptr ->data;     //遍历并打印树根
	Inorder(ptr->left);   //遍历左子树
	Inorder(ptr->right);   //遍历右子树
	}
}

 

二叉树节点的插入和删除

在二叉树建立的过程中，是根据左子树<树根<右子树的原则建立的。

查找

只需从树根出发比较键值，如果比树根大就往右，否则往左而下，直到相等就找到了要查找的值，如果比到NULL，无法再前进就代表查找不到此值。

btree search (btree ptr,int val)  //查找二叉树某键值得函数
{
	while（1）
	{
		if(ptr==NULL)     //没找到就返回NULL
			return NULL;
		if(ptr->data==val)   //节点值等于查找值
			return ptr;
		else if(ptr->data>val)  //节点值大于查找值
			ptr=ptr->left;
		else                  //小于查找值
			ptr=ptr->right;    
	}
}

插入操作

插入节点的情况和查找相似，关键是插入后仍要保持二叉查找树的特性（左子树<树根<右子树）。如果插入的节点在二叉树中没有找到，就是出现查找失败的情况，就相当于找到了要插入的位置。我们可以修改，只要多加一条if判断语句，当查找到键值时输出“二叉树中有此节点了！”，如果找不到，再将此节点加到此二叉树中。算法如下所示。

	btree ptr=NULL;
if((search(ptr,data))!=NULL)     //查找二叉树
    cout<<"二叉树中有此节点了-"<<data<<endl;
else
	{
    	ptr=creat_tree(ptr,data);//将此键值加入到此二叉树中
    	inorder(ptr);
	}

btree creat_tree(btree root,int val)
{  
	btree newnode,current,backup;
	newnode=(btree)malloc(sizeof(node));//创建一个新结点
	newnode->data=val;
	newnode->left=NULL;
	newnode->right=NULL;
	if(root==NULL)    //如果树根为空
	{  
		root=newnode;
		return root;
	}
	else     //树不为空
	{  
		for(current=root;current!=NULL;)   //把树赋给root
		{  
			backup=current;    //current赋给backup
			if(current->data > val)    //val小于此结点的data
				current=current->left; //current被赋为右树的节点
			else
				current=current->right;//current被赋为左树的节点
		}
		if(backup->data >val) //节点数据域大于val值说明新结点是它的左孩子
			backup->left=newnode;
		else
			backup->right=newnode;
	}
	return root;
}

}
void inorder(btree ptr)			//中序遍历子程序
{  
  if(ptr!=NULL)
     {  
      inorder(ptr->left);
      cout<<"["<<ptr->data<<"]";
      inorder(ptr->right);
      }
}

 

二叉树的删除

1.删除的结点为树叶：只要将其相连的父节点指向NULL即可。

2.删除的节点只有一颗子树，如下图，要删除节点1，就要将其右指针放到其父节点的左指针

3.删除的节有两颗子树，如下图，要删除节点4，方式有两种

​ 3.1 找出中序立即先行者（inorder immediate predecessor）

即是将欲删除节点的左子树中最大者向上提，在此即为图中的节点2，简单来说，就是在该节点的左子树，往右寻找，直到右指针为NULL，这个节点就是中序立即先行者。

​ 3.2 找出中序立即后继者（inorder immediate successor）

即是将欲删除节点的右子树中最小者向上提，在此即为图中的节点5，简单来说，就是在该节点的右子树，往左寻找，直到左指针为NULL，这个节点就是中序立即后继者。

 

平衡二叉树（AVL树）

由于二叉查找树的缺点是无法永远保持在最佳状态。当加入的数据部分已排序的情况下，极有可能产生斜二叉树，因而使树的高度增加，导致查找效率降低。所以二叉查找树不利于数据的经常变动（加入或删除）的情况。为了能够尽量降低所需要的时间，在查找的时候能够很快找到所要的键值，就必须让树的高度越小越好。

现在又a[8] = {1,2,3,4,5,6,7,8}需要构建二叉排序树。在没有学习平衡二叉树之前，根据二叉排序树的特性，通常会将它构建成如下左图。虽然完全符合二叉排序树的定义，但是对这样高度达到8的二叉树来说，查找是非常不利的。因此，更加期望构建出如下右图的样子，高度为4的二叉排序树，这样才可以提供高效的查找效率。

二叉排序树

由序列{1，2，3，4，5}得到二叉排序树：ASL=（1+2+3+4+5）/5=3

由序列{3，1，2，5，4}得到二叉排序树：ASL =（2+3+1+3+2）/5= 2.2

平衡树的定义

在AVL树中，每次在插入数据和删除数据后，必要的时候会对二叉树作一些高度的调整让二叉查找树的高度随时维持平衡。T是一个非空的二叉树，$T_l$和$T_r$，分别是它的左右子树，若符合$\left|h_{1}-h_{r}\right|\leq1$。$h_i$和$h_r$，分别为$T_l$和$T_r$的高度，也就是所有内部节点的左右子树高度相差必定小于或等于1，则称T是个高度平衡树。

平衡因子：结点的平衡因子是该结点的左子树的深度与右子树的深度之差。

平衡二叉树的调整

构造平衡二叉树的基本思想：每插入一个结点，
（1）从插入结点开始向上计算各结点的平衡因子，如果某结点平衡因子的绝对值超过1，则说明插入操作破坏了二叉排序树的平衡性，需要进行平衡调整；否则继续执行插入操作。
（2）如果二叉排序树不平衡，则找出最小不平衡子树的根结点，根据新插入结点与最小不平衡子树根结点之间的关系判断调整类型。
（3）根据调整类型进行相应的调整，使之成为新的平衡子树。

当我们从零开始插入一个二叉树的时候，最开始是一个空的树

if (root == NULL) {
		root = (AVLTREE*)malloc(sizeof(AVLTREE));
		root->data = data;
		root->height = 0;
		root->leftChlid = root->rightChild = NULL;
	}

如果判断树为空，那么我们先给树跟分配一个空间，树的data域储存第一个数据，这个树的高度为零，左右孩子都为空。

然后当我们去插入节点的时候，通过规则判断，比这个数据小的会储存到左孩子中，比这个数据大的会储存到右孩子中。但当我们插入第三个开始就可能会出现不平衡的情况，即不符合$\left|h_{1}-h_{r}\right|\leq1$我们归纳为以下四种情况，每次插入我们都进行判断，从而保证二叉树一直在一个平衡的状态。

设结点A为最小不平衡子树的根结点，对该子树进行平衡调整归纳起来有以下四种情况：
1.LL型

1. RR型

2. LR型

3. RL型

LL型

当根结点左子树的左子树中的节点导致根结点的平衡因子为2时，采用LL型旋转进行调整。

因为我们插入的时候就已经知道$B_R$是大于B小于A的，所以我们可以把$B_R$当作A的一个左孩子

if (data < root->data) {    //如果要插入的数据小于树的data域，插入为树的左孩子            
	root->leftChlid = insertPoint(data, root->leftChlid); 

	if (getHeight(root->leftChlid) - getHeight(root->rightChild) == 2) {//如果左子树的深                                                                          度比右子树的深度高1
		if (data < root->leftChlid->data)  //插入数据小于左孩子就是左左
			root = left_Left_Rotation(root);
		else                               //反之则为右右
			root = left_Right_Rotation(root);
	}
}

左左的操作

AVLTREE* left_Left_Rotation(AVLTREE* root) {
	AVLTREE* newRoot = NULL;

	newRoot = root->leftChlid;
	root->leftChlid = newRoot->rightChild;
	newRoot->rightChild = root;

	root->height = max(getHeight(root->leftChlid), getHeight(root->rightChild)) + 1;
	newRoot->height = max(getHeight(newRoot->leftChlid), root->height) + 1;

	return newRoot;
}

RR型

AVLTREE* right_Right_Rotation(AVLTREE* root) {
	AVLTREE* newRoot = NULL;

	newRoot = root->rightChild;
	root->rightChild = newRoot->leftChlid;
	newRoot->leftChlid = root;

	root->height = max(getHeight(root->leftChlid), getHeight(root->rightChild)) + 1;
	newRoot->height = max(getHeight(newRoot->rightChild), root->height) + 1;

	return newRoot;
}

 

LR型

LR型是一种特殊情况，前面两次LL和RR都是单旋转，而LR型和RL型是双旋转

对其应该先进行一次右右，再进行一次左左

AVLTREE* left_Right_Rotation(AVLTREE* root) {
	root->leftChlid = right_Right_Rotation(root->leftChlid);

	return left_Left_Rotation(root);
}

RL形

AVLTREE* right_Left_Rotation(AVLTREE* root) {
	root->rightChild = left_Left_Rotation(root->rightChild);

	return right_Right_Rotation(root);
}

AVL树的插入

AVLTREE* insertPoint(int data, AVLTREE* root) {
	
	if(root == NULL) {
		root = (AVLTREE *)malloc(sizeof(AVLTREE));
		root->data = data;
		root->height = 0;
		root->leftChlid = root->rightChild = NULL;
	} else if(data < root->data) { //如果插入数据小于树的数据，则插入到书的左子树        
		root->leftChlid = insertPoint(data, root->leftChlid);
		
		if(getHeight(root->leftChlid) - getHeight(root->rightChild) == 2) {	//判断是LX
			if(data < root->leftChlid->data)
				root = left_Left_Rotation(root);//判断为LL
			else
				root = left_Right_Rotation(root);//判断为LR
		}
	} else if(data > root->data) {//如果插入数据大于于树的数据，则插入到书的左子树  
		root->rightChild = insertPoint(data, root->rightChild);
		if(getHeight(root->rightChild) - getHeight(root->leftChlid) == 2) {//判断为RX型
			if(data > root->rightChild->data)  //判断为RR型
				root = right_Right_Rotation(root);
			else                               //判断为RL型
				root = right_Left_Rotation(root);
		}
	} else if(data == root->data) {
		return NULL;               
	}
 
	root->height = max(getHeight(root->leftChlid), getHeight(root->rightChild)) + 1;
	return root;
}

 

平衡二叉树的删除

删除操作和二叉查找树删除一样，分为三种情况讨论

（1）删除节点没有左右子树，这种情况直接删除此节点即可

（2）删除节点没有左子树，这种情况直接将删除节点的父节点指向删除节点的右子树。

（3）删除节点没有右子树，这种情况直接将删除节点的父节点指向删除节点的左子树。

（4）删除节点左右子树都存在，可以采用两种方式，

​ 1：让删除节点左子树的最右侧节点代替当前节点

​ 2：让删除节点右子树的最左侧节点代替当前节点

  

只有左右子树，或者无子树

AVLTREE* temp = root;

root = root->leftChlid ? root->leftChlid : root->rightChild;
destroy(temp);

创建一个临时节点存放树，如果左孩子不为空，此节点root等于root的左子树，如果左子树节点为空，此节点root就等于root的右孩子。就相当于删除了root

如果是没有子节点的情况下，三目运算判断root为root的右子树，但是右子树为null就相当于把其删去

 

有左右子树

if (root->leftChlid && root->rightChild) {

			if (getHeight(root->leftChlid) > getHeight(root->rightChild)) {
				
				AVLTREE* max = getMaxNum(root->leftChlid);
				root->data = max->data;
				root->leftChlid = deletePoint(max->data, root->leftChlid);
			}
			else {
				
				AVLTREE* min = getMinNum(root->rightChild);
				root->data = min->data;
				root->rightChild = deletePoint(min->data, root->rightChild);
			}
		}

 

重要的是，在每一次删除节点以后，都要对新的树进行判断是否平衡，也就是平衡因子是小于等于1。

待删除的点在左子树

if (abs(getHeight(root->rightChild) - getHeight(root->leftChlid)) == 2) {
			AVLTREE* p = root->rightChild;

			if (getHeight(p->leftChlid) > getHeight(p->rightChild)) {
				root = right_Left_Rotation(root);
			}
			else {
				root = right_Right_Rotation(root);
			}
		}

待删除的点在右子树

if (abs(getHeight(root->leftChlid) - getHeight(root->rightChild)) == 2) {
			AVLTREE* p = root->leftChlid;
			if (getHeight(p->rightChild) > getHeight(p->leftChlid)) {
				root = left_Right_Rotation(root);
			}
			else {
				root = left_Left_Rotation(root);
			}