TreeNote - juedaiyuer/researchNote GitHub Wiki

#数据结构-树#

分层次组织在管理上具有更高的效率
静态查找,动态查找

查找方法

哨兵方法

顺序查找算法的时间复杂度O(n)
Binary Search,时间复杂度O(logN)

有序存放,数组结构
由二分查找可以画出二分查找的判定树

判定树

判定树上每一个节点需要查找次数刚好为该结点所在的层数
n结点的判定树深度为[logN]+1 (log取2,方括号取整)
ASL 平均成功查找次数第几层所在元素的个数*第几层 / 总节点数

树的表现

儿子-兄弟表示法(儿子指第一个儿子)

##二叉树##

完全二叉树(从上往下,从左到右,结点序号与满二叉树相同)；换句话说,满二叉树最后一层右侧节点没有几个的形式

重要性质

一个二叉树第i层的最大结点数 2^(i-1)
深度为k的二叉树最大结点总数为:2^k - 1
对于任何非空二叉树T,N(0)表示叶结点的个数,N(1)非叶结点有一个儿子的个数...N(0) = N(2)+1

存储结构

顺序存储结构(数组存储方法)
链表存储

##常用的遍历方法##

###递归方式###

先序遍历根-左子树-右子树

void PreOrderTraversal(BinTree BT)
{
	if(BT)
	{
		printf("%d",BT->Data);
		PreOrderTraversal(BT->Left);
		PreOrderTraversal(BT->Right)
	}
}

ABDFECGHI

中序左子树-根结点-右子树

void PreOrderTraversal(BinTree BT)
{
	if(BT)
	{
		PreOrderTraversal(BT->Left);
		printf("%d",BT->Data);		
		PreOrderTraversal(BT->Right)
	}
}

DBEFAGHCI

后序左子树-右子树-根结点

DEFBHGICA

层次遍历

递归方式经过结点的路径相同,访问时机不一样
先序:第一次经过结点访问；中序:第二次经过结点访问；后序:第三次经过访问

二叉树

###非递归方式###

使用堆栈

中序遍历非递归

void InOrderTraversal(BinTree BT)
{
	BinTree T = BT;
	Stack S = CreateStack(MaxSize);
	while(T || !IsEmpty(S)){
		while(T)  //遇到结点,指向左儿子,一直到没有左儿子
		{
			while(T);
			Push(S,T);
			T = T->left;
		}
		if(!IsEmpty(S)){
			T = Pop(S);
			printf("%5d",T->Data);
			T = T->Right;   //遍历结点的右儿子
		}
	}
}

###层序遍历###

存储结构:堆栈,队列

队列实现

void LevelOrderTraversal(BinTree BT)
{
	Queue Q;
	BinTree T;
	if(!BT) return;
	Q = CreateQueue(MaxSize);
	AddQ(Q,BT);
	while(!IsEmpty(Q))
	{
		T = DeleteQ(Q);
		printf("%d\n",T->Data);
		if(T->Left) AddQ(Q,T->Left);
		if(T->Right) AddQ(Q,T->Right);
	}
}

##应用##

二叉树高度

后序遍历实现

二元运算表达式树及其遍历

叶结点为数值
非叶结点为运算符
根结点是左右子树的连接运算符,譬如+；左子树+右子树
中序表达式受运算符优先级影响,解决方式是增加()

##二叉搜索树##

Binary Search Tree (BST)
左子树<根结点<右子树
查找的效率决定于树的高度
最大元素在最右分支的端结点
最小元素在最左分支的端结点

尾递归方法

Position Find(Element x,BinTree BST)
{
	if(!BST) return NULL;
	if(x>BST->Data)
		return Find(x,BST->Right);
	else if(x<BST->Data)
		return Find(x,BST->Left);
	else
		return BST;
}

非递归函数的执行效率高,迭代

Position IterFind(ElementType x,BinTree BST)
{
	while(BST)
	{
		if(x>BST->Data)
			BST = BST->Right;
		else if(x<BST->Data)
			BST = BST->Left;
		else
			return BST;
	}
	return null;
}

查找最小元素的递归函数

Position FindMin(BinTree BST)
{
	if(!BST) return null;
	else if(!BST->Left) 
		return BST;
	else 
		return FindMin(BST->Left);
}

查找最大元素的迭代函数

Position FindMax(BinTree BST)
{
	if(BST)
		while(BST->Right) BST = BST->Right;
	return BST;
}

###插入###

插入递归

BinTree Insert(ElementType x,BinTree BST)
{
	if(!BST)
	{
		BST = malloc(sizeof(struct TreeNode));
		BST->Data = x;
		BST->Left = BST->Right = null
	}else
		if(x<BST->Data)
			BST->Left = Insert(x,BST->Left); // 递归插入左子树
		else if(x>BST->Data)
			BST->Right = Insert(x,BST->Right);

	return BST;
		
}

##删除##

叶结点直接删除,其父结点的指针置于null
删除的结点只有一个儿子的结点
删除结点有左右儿子.(右子树的最小元素,左子树的最大元素)

递归删除结点有两个儿子的方式

BinTree Delete(ElmentType x,BinTree BST)
{
	Position Tmp;
	if(!BST) printf("要删除的元素未找到");
	else if(x<BST->Data)
		BST->Left = Delete(x,BST->Left);
	else if(x>BST->Right)
		BST->Right = Delete(x,BST->Right);
	else
		if(BST->Left&&BST->Right)
		{
			Tmp = FindMin(BST->Right); //在右子树中找到最小的元素
			BST->Data = Tmp->Data;
			BST->Right = Delete(BST->Data,BST->Right); //删除点的右子树的最小元素
		}else{
			Tmp = BST;
			if(!BST->Left)
				BST = BST->Right;
			else if(!BST->Right)
				BST = BST->Left;
			free(Tmp);
		}	
	return BST;
}

##平衡二叉树AVL##

平均查找长度ASL
平衡因子(Balance Factor),BF,BF(T)=Hl-Hr
平衡二叉树(Balanced Binary Tree),AVL树,|BF(T)|小于等于1
搜索算法复杂度是log(n)量级

AVL高度