数据结构 浙大MOOC 树-上
静态查找
方法1:顺序查找
基本思想:Tb1[0]中存放的是待查找元素K
,从表尾开始查找,如果当前元素Tb1->Element[i]
与待查找的元素K
相等,返回当前下标,否则会一直查找到第一个元素(即数组下标为0的元素)返回的是0;表明查找失败,最坏情况是遍历一遍整个数组,即顺序查找算法的时间复杂度为O(n).
//在表Tb[1]~Tb[n]中查找关键字为K的数据元素
int SequentialSearch (StaticTable *Tb1, ElementType K)
{
int i;
Tb1->Element[0] = K; //建立哨兵
for(i = Tb1->Length; Tb1->Element[i]!=K; i--)
return i; //查找成功返回所在单元下标,不成功返回0;
}
#include <iostream>
using namespace std;
typedef struct StaticTable
{
int Element[11]; //指向数组的指针
int length; //表明当前数组的长度
StaticTable(int *e, int len) : length(len)
{
for (int i = 1; i <= 10; i++)
{
Element[i] = e[i];
}
}
}StaticTable;
int SequentSearch(StaticTable *Tb1, int K)
{
int i;
Tb1->Element[0] = K;
// for (i = Tb1->length; Tb1->Element[i] != K; i--); //结束
//
// // cout << Tb1->Element[i] << " ";
// return i;
//
for(i=Tb1->length; ;i--)
{
if(Tb1->Element[i] == K)
{
return i;
}
}
//此种while循环可以实现
// i = Tb1->length;
// while(i>0)
// {
// if(Tb1->Element[i] == K)
// {
// return i;
// }
// i--;
// }
// return 0;
}
int main()
{
int a[11] = { 0 };
for (int i = 1; i <= 10; i++)
{
a[i] = 2 * i + 1;
}
for (auto i : a)
{
cout << i << " ";
}
cout << endl;
StaticTable tb1(a, 10);
StaticTable *Tb1 = &tb1;
cout << "查找6的位置";
cout << SequentSearch(Tb1, 6) << endl;
cout << "查找11的位置";
cout << SequentSearch(Tb1, 11) << endl;
return 0;
}
二分查找
假设n个数据元素的关键字满足有序(比如:小到大),k1<k2<…<kn,并且使连续存放(数组),那么可以进行二分查找。
二分查找算法具有对数的时间复杂度O(logN)
#include <iostream>
using namespace std;
typedef struct StaticTable
{
int Element[11]; //指向数组的指针
int length; //表明当前数组的长度
StaticTable(int *e, int len) : length(len)
{
for (int i = 1; i <= 10; i++)
{
Element[i] = e[i];
}
}
}StaticTable;
int BinarySearch(StaticTable *Tb1, int K)
{
//在表Tb1中查找关键字为K的数据元素
int left, right, mid, NotFound = -1;
left = 1; //初始左边界
right = Tb1->length; //初始右边界
while(left < right)
{
mid = (left + right)/2; //计算中间元素的坐标
if(K<Tb1->Element[mid])
{
right = mid-1; //调整右边界
}
else if(K>Tb1->Element[mid])
{
left = mid+1; //调整左边界
}
else
{
return mid; //查找成功,返回数组元素的下标
}
}
return NotFound; //查找不成功,返回-1
}
int main()
{
int a[11] = { 0 };
for (int i = 1; i <= 10; i++)
{
a[i] = 2 * i + 1;
}
for (auto i : a)
{
cout << i << " ";
}
cout << endl;
StaticTable tb1(a, 10);
StaticTable *Tb1 = &tb1;
cout << "查找6的位置";
cout << BinarySearch(Tb1, 6) << endl;
cout << "查找11的位置";
cout << BinarySearch(Tb1, 11) << endl;
cout << "Hello world!" << endl;
return 0;
}
typedef struct TreeNode *BinTree; //结构指针-指向树节点
typedef BinTree Position; //BinTree == Position
struct TreeNode{ //树节点结构
ElementType Data; //数据域
BinTree Left; //左指针
BinTree Right; //右指针
}
二叉树的遍历
先序遍历
- 先遍历根节点
- 先序遍历其左子树
- 先序遍历其右子树
递归实现
void PreOrderTraversal(BinTree BT) //BT指向树根节点
{
if(BT)
{
printf("%d", BT->Data); // 访问根节点
PreOrderTraversal(BT->Left); //先序遍历左子树
PreOrderTraversal(BT->Right); //先序遍历右子树
}
}
中序遍历
- 中序遍历其左子树
- 访问根节点
- 中序遍历其右子树
//中序遍历--递归实现
void InOrderTraversal(BinTree BT)
{
if(BT)
{
InOrderTraversal(BT->Left);
printf("%d", BT->Data);
InOrderTraversal(BT->Right);
}
}
后序遍历
- 后序遍历其左子树
- 后序遍历其右子树
- 访问根节点
//后续遍历,递归实现
void PostOrderTraversal(BinTree BT)
{
if(BT)
{
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
printf("%d", BT->Data);
}
}
中序遍历非递归遍历算法
- 遇到一个节点,就将它压栈,并去遍历它的左子树
- 当左子树遍历结束之后,从栈顶弹出这个节点并访问它,
- 然后按其右指针再去中序遍历该节点的右子树
//中序遍历,栈实现非递归
void InOrderTraversal(BinTree BT)
{
BinTree T = BT; //保存树根节点的地址
Stack S = CreateStack(MaxSize); //创建并初始化堆栈S
while(T || !IsEmpty(S))
{
while(T) //一直向左并将沿途节点压入堆栈
{
Push(S, T);
T = T->Left;
}
if(!IsEmpty(S))
{
T = Pop(S); // 节点弹出堆栈
printf("%5d", T->Data); //访问,打印节点
T = T->Right; //转向右子树
}
}
}
先序遍历的非递归算法
//先序遍历的非递归算法
void InOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S = CreateStack(MaxSize);
while(T || !IsEmpty(S))
{
while(T) //一直向左并将沿途节点压入堆栈
{
printf("%5d", T->Data); //访问节点
Push(S, T);
T = T->Left;
}
if(!IsEmpty(S))
{
T = Pop(S); //节点弹出堆栈
T = T->Right; //转向右子树
}
}
}
层序遍历队列实现过程
- 从队列中取出一个节点
- 访问该元素所指节点
- 若该元素所指节点的左,右孩子节点非空,则将其左右孩子的指针顺序入队
void LevelOrderTraversal(BinTree BT)
{
Queue Q;
BInTree T;
if(!BT)
{
return; //若是空树直接返回
}
Q = CreateQueue(MaxSize); //创建并初始化队列Q
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);
}
}
}
遍历二叉树应用:输出二叉树中的叶子节点
关键是在二叉树遍历算法中增加检测节点的"左右子树是否为空"
void PreOrderPrintLeaves(BinTree BT)
{
if(BT)
{
//只有当左子树和右子树都为空时才进行处理
if(!BT->Left && !BT->Right)
{
printf("%d", BT->Data);
}
PreOrderTraversal(BT->Left);
PreOrderTraversal(BT->Right);
}
}
int PostOrderGetHeight(BinTree BT)
{
int HL, HR, MaxH;
if(BT)
{
HL = PostOrderGetHeight(BT->Left); //求左子树的深度
HR = PostOrderGetHeight(BT->Right); //求右子树的深度
MaxH = (HL > HR)? HL:HR; //取左右子树中较大的深度
return (MaxH + 1); //返回树的深度
}
else
return 0; //空树的深度为0
}