二叉树
二叉树 – 二叉链表存储
二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域，我们称这样的链表为二叉链表。
二叉数的性质
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，中序遍历
先遍历输出左结点，再输出当前结点的数据，再遍历输出右结点
GＤH 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