算法(2)——二叉树
二叉树
二叉树 - 二叉链表存储
二叉树每个结点最多有两个孩子,所以为它设计一个数据域和两个指针域,我们称这样的链表为二叉链表。
二叉数的性质
1,在二叉树的第i层上最多有 2i-1个结点(i>=1)
2,深度为k的二叉树至多有2k-1个结点
20+21+22+23+24+25+26+27+.....+2k-1+-1
=1+20+21+22+23+24+25+26+27+.....+2k-1-1
=21+21+22+23+24+25+26+27+.....+2k-1-1
=22+22+23+24+25+26+27+.....+2k-1-1
=23+23+24+25+26+27+.....+2k-1-1
=2k-1+2k-1-1
=2k-1
3,对于一个完全二叉树,假设它有n个结点,对结点进行从1开始编号,对任一结点i满足下面
a,它的双亲是结点 i/2 (除了i=1的情况)
b,左孩子是 2i 右孩子是 2i+1
c,如果2i>n 说明无左孩子 2i+1>n 说明无右孩子
class Program
{
static void Main(string[] args)
{
char[] data = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J' };//这个是我们要存储的数据
BiTree<char> tree = new BiTree<char>(10);
for (int i = 0; i < data.Length; i++)
{
tree.Add(data[i]);
}
//前序遍历
tree.FirstTraversal();
Console.WriteLine();
//中序遍历
tree.MiddleTraversal();
Console.WriteLine();
//后序遍历
tree.LastTraversal();
Console.WriteLine();
//层遍历
tree.LayerTraversal();
Console.ReadKey();
}
}
前序遍历,中序遍历,后序遍历三种遍历方式
二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。
1,前序遍历
先输出当前结点的数据,再依次遍历输出左结点和右结点
A (B) (C)
B (D) C (E) F
D G H E I
A B D G H C E I
2,中序遍历
先遍历输出左结点,再输出当前结点的数据,再遍历输出右结点
GDH B A E I C F
3,后序遍历
先遍历输出左结点,再遍历输出右结点,最后输出当前结点的数据
G H D B I E F C A
4、层序遍历
从树的第一层开始,从上到下逐层遍历,在同一层中,从左到右对结点 逐个访问输出
//如果一个结点是空的话,那么这个结点所在的数组位置,设置为-1,
class BiTree<T>
{
private T[] data;
private int count = 0;
public BiTree(int capacity)// 这个参数是当前二叉树的容量,容量就是最多可以存储的数据个数, 数量count代表当前保存了多少个数据
{
data = new T[capacity];
}
public bool Add(T item)
{
if (count >= data.Length)
return false;
data[count] = item;
count++;
return true;
}
public void FirstTraversal()
{
FirstTraversal(0);
}
//前序遍历
/// <summary>
/// 前序遍历:先输出当前结点的数据,再依次遍历输出左结点和右结点
/// </summary>
/// <param name="index"></param>
private void FirstTraversal(int index)
{
if (index >= count) return;
//得到要遍历的这个结点的编号
int number = index + 1;
if (data[index].Equals(-1)) return;
Console.Write(data[index] + " ");
//得到左子结点的编号
int leftNumber = number * 2;
//右子节点的编号
int rightNumber = number * 2 + 1;
//递归
FirstTraversal(leftNumber - 1);
FirstTraversal(rightNumber - 1);
}
public void MiddleTraversal()
{
MiddleTraversal(0);
}
/// <summary>
/// //中序遍历,先遍历输出左结点,再输出当前结点的数据,再遍历输出右结点
/// </summary>
/// <param name="index"></param>
private void MiddleTraversal(int index)
{
if (index >= count) return;
//得到要遍历的这个结点的编号
int number = index + 1;
if (data[index].Equals(-1)) return;
//得到左子结点的编号
int leftNumber = number * 2;
int rightNumber = number * 2 + 1;
MiddleTraversal(leftNumber - 1);
Console.Write(data[index] + " ");
MiddleTraversal(rightNumber - 1);
}
public void LastTraversal()
{
LastTraversal(0);
}
/// <summary>
/// 后续遍历:先遍历输出左结点,再遍历输出右结点,最后输出当前结点的数据
/// </summary>
/// <param name="index"></param>
private void LastTraversal(int index)
{
if (index >= count) return;
//得到要遍历的这个结点的编号
int number = index + 1;
if (data[index].Equals(-1)) return;
//得到左子结点的编号
int leftNumber = number * 2;
int rightNumber = number * 2 + 1;
LastTraversal(leftNumber - 1);
LastTraversal(rightNumber - 1);
Console.Write(data[index] + " ");
}
public void LayerTraversal()
{
for (int i = 0; i < count; i++)
{
//当前的节点没有数据
if (data[i].Equals(-1)) continue;
Console.Write(data[i] + " ");
}
Console.WriteLine();
}
}
二叉排序树
二叉排序树,又称为二叉查找树。它或者是一棵空树,或者是具有下列性质的二叉树。
若它的左子树不为空,则左子树上所有的结点的值均小于根结构的值;
若它的右子树不为空,则右字数上所有结点的值均大于它的根结点的值;
它的左右子树也分别为二叉排序树。
1,排序方便
2,方便查找
3,方便插入和删除
二叉排序树 删除操作
二叉排序树删除
1,叶子结点
2,仅有左子树或者右子数的结点
3,左右子树都有
二叉排序树的存储
因为二叉排序树的存储,跟自身值的大小有关系,并不是想之前学习的完全二叉树使用顺序结构可以存储的,
所以我们使用链式结构存储二叉排序树。
二叉排序树的代码实现
一个是树类的定义 BSTree
一个是结点类的定义BSNode
节点
class BSNode
{
public BSNode LeftChild { get; set; }
public BSNode RightChild { get; set; }
public BSNode Parent { get; set; }
public int Data { get; set; }
public BSNode()
{
}
public BSNode(int item)
{
this.Data = item;
}
}
执行程序
class Program
{
static void Main(string[] args)
{
BSTree tree = new BSTree();
int[] data = { 62, 58, 88, 47, 73, 99, 35, 51, 93, 37 };
foreach (int t in data)
{
tree.Add(t);
}
tree.MiddleTraversal();
Console.WriteLine();
Console.WriteLine(tree.Find(99));
Console.WriteLine(tree.Find(100));
tree.Delete(35);
tree.MiddleTraversal(); Console.WriteLine();
tree.Delete(62);
tree.MiddleTraversal(); Console.WriteLine();
Console.ReadKey();
}
}
树
class BSTree
{
BSNode root = null;
//添加数据
public void Add(int item)
{
BSNode newNode = new BSNode(item);
if (root == null)
{
root = newNode;
}
else
{
BSNode temp = root;
while (true)
{
//比根节点大
if (item >= temp.Data)//放在temp的右边
{
if (temp.RightChild == null)
{
//右节点为空,直接放右边
//孩子和父亲互认一下
temp.RightChild = newNode;
newNode.Parent = temp;
break;
}
else
{
temp = temp.RightChild;
}
}
else//放在temp的左边
{
if (temp.LeftChild == null)
{
//左节点为空,放左节点,父子相认
temp.LeftChild = newNode;
newNode.Parent = temp;
break;
}
else
{
temp = temp.LeftChild;
}
}
}
}
}
/// <summary>
/// 中序遍历
/// </summary>
public void MiddleTraversal()
{
MiddleTraversal(root);
}
//中序遍历从哪个节点开始
private void MiddleTraversal(BSNode node)
{
if (node == null) return;
MiddleTraversal(node.LeftChild);
Console.Write(node.Data + " ");
MiddleTraversal(node.RightChild);
}
/// <summary>
/// 查找根节点,外部调用
/// </summary>
/// <param name="item"></param>
/// <returns></returns>
public bool Find(int item)
{
BSNode temp = root;
while (true)
{
if (temp == null) return false;
if (temp.Data == item) return true;
if (item > temp.Data)
//向右子树查找
temp = temp.RightChild;
else
//向左册数查找
temp = temp.LeftChild;
}
}
private bool Find(int item, BSNode node)
{
if (node == null) return false;
if (node.Data == item)
{
return true;
}
else
{
if (item > node.Data)
{
return Find(item, node.RightChild);
}
else
{
return Find(item, node.LeftChild);
}
}
}
/// <summary>
/// //删除节点值
/// </summary>
/// <param name="item"></param>
/// <returns></returns>
public bool Delete(int item)
{
BSNode temp = root;
while (true)
{
if (temp == null) return false;
if (temp.Data == item)
{
Delete(temp);
return true;
}
if (item > temp.Data)
temp = temp.RightChild;
else
temp = temp.LeftChild;
}
}
public void Delete(BSNode node)
{
if (node.LeftChild == null && node.RightChild == null)
{
//左右节点都为空
if (node.Parent == null)
{
root = null;
}
else if (node.Parent.LeftChild == node)
{
node.Parent.LeftChild = null;
}
else if (node.Parent.RightChild == node)
{
node.Parent.RightChild = null;
}
return;
}
if (node.LeftChild == null && node.RightChild != null)
{
//左节点为空
node.Data = node.RightChild.Data;
node.RightChild = null;
return;
}
if (node.LeftChild != null && node.RightChild == null)
{
//右节点为空
node.Data = node.LeftChild.Data;
node.LeftChild = null;
return;
}
//左右节点都存在,找右节点的最左侧的值
BSNode temp = node.RightChild;
while (true)
{
if (temp.LeftChild != null)
{
temp = temp.LeftChild;
}
else
{
break;
}
}
node.Data = temp.Data;
Delete(temp);
}
}
堆
堆是具有下列性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于等于其左右孩子结点的值,称为小顶堆!
堆排序
堆排序算法就是利用堆(小顶堆或者大顶堆)进行排序的方法。
将待排序的序列构造成一个大顶堆,此时整个序列的最大值就是根节点。将它移走(跟堆的最后一个元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素中的次小值。如此反复执行,便能得到一个有序序列了。
本文地址:https://blog.csdn.net/qq_35647121/article/details/110939205
下一篇: mysql 造大批量数据 insert
推荐阅读
-
从月薪2千到2万 运营提升这六大工具你必须会
-
SQLserver海量数据库的查询优化及分页算法详解
-
win2008 R2安装网站安全狗提示HTTP 错误 500.21的解决方法
-
Reverse a String-freecodecamp算法题目
-
Windows Server 2012 R2 预览版安装全程图解
-
Windows 2008 r2 防火墙设置端口例外的方法
-
windows server 2008 R2 禁用ipv6和隧道适配器
-
win2008 r2 iis7.5中限制带宽的方法(图文)
-
Microsoft Windows 2008 Server R2 iis7.5上传文件限制200K更改
-
jQuery插件HighCharts实现的2D面积图效果示例【附demo源码下载】