首页 > 代码库 > c#使用数组实现二叉查找树
c#使用数组实现二叉查找树
原创性申明:
本文地址是http://blog.csdn.net/zhujunxxxxx/article/details/40925687 转载请注明出处。作者联系邮箱 zhujunxxxxx@163.com
二叉排序树
（Binary Sort Tree）又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
它或者是一棵空树；或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
树的储方案：
用数组来实现二叉树，树上的元素存放位置在数组中是固定的---如果树的i位置（从1开始按层编号）有元素，就放在数组的i号位置，没有元素，数组对应的位置就空着。i的左右子树的编号为2i和2i+1。
1，实例变量，容量动态扩展，以及构造方法：
/// <summary>
/// 数组存储树的结构(还有一种是Node)
/// </summary>
private int[] data;//从1开始存储数据
/// <summary>
/// 树的长度
/// </summary>
private int len;
/// <summary>
/// 删除节点时用的一个临时的数据结构
/// </summary>
private List<int> tmpList;
public Tree()
{
//先初始化一个1w大小的数组
this.data = http://www.mamicode.com/new int[100];>
2，树的插入
数组实现插入其实跟链式思想还是一样，往下找插入节点就是往下找插入的下标，下标的关系已经在前面说过，要注意的是数组容量可能不够，需要扩展容量
/// <summary>
/// 把节点插入树
/// </summary>
public void Insert(int key)
{
if (len == 0)
{
data[1] = key;
len++;
}
else
{
int index = 1;
while (index <data.Length)
{
if (key < data[index])
{
//拓展数组
if (LeftChild(index) >= data.Length)
Expand();
//判断这个节点是否为空
if (data[LeftChild(index)] == 0)
{
data[LeftChild(index)] = key;
len++;
break;
}
else
{
index = LeftChild(index);
}
}
else
{
//拓展数组
if (RightChild(index) >= data.Length)
Expand();
//判断这个节点是否为空
if (data[RightChild(index)] == 0)
{
data[RightChild(index)] = key;
len++;
break;
}
else
{
index = RightChild(index);
}
}
}
}
}3，树的删除
当某个结点被删后，它的子树上的全部结点的下标都要调整，而且这个调整顺序还得从上网下调，否则下面的节点的可能覆盖上面的，
没有想到什么好的办法，最后只有用了一个消耗最大的笨方法---将被删结点置为null后，前序遍历树（或者后序，不能中序），
将前序序列依次重新插入建树。相当于删除节点后，把剩下结点取出来重新建树
没有想到什么好的办法，最后只有用了一个消耗最大的笨方法---将被删结点置为null后，前序遍历树（或者后序，不能中序），
将前序序列依次重新插入建树。相当于删除节点后，把剩下结点取出来重新建树
/// <summary>
/// 删除树的节点
/// </summary>
public int Delete(int key)
{
int value=http://www.mamicode.com/-1;>
4，树的前序遍历
/// <summary>
/// 先序遍历
/// </summary>
public void PreOrder(int i)
{
if (i >= data.Length)
return;
if (data[i] != 0)
{
tmpList.Add(data[i]);
}
PreOrder(LeftChild(i));
PreOrder(RightChild(i));
}5，树的中序遍历
/// <summary>
/// 中序遍历
/// </summary>
/// <param name="i"></param>
public void InOrder(int i)
{
if (i >=data.Length)
return;
InOrder(LeftChild(i));
if (data[i] != 0)
{
Console.Write(data[i] + " ");
}
InOrder(RightChild(i));
}6，树的后续遍历
/// <summary>
/// 后续遍历
/// </summary>
/// <param name="i"></param>
public void PostOrder(int i)
{
if (i >= data.Length)
return;
PostOrder(LeftChild(i));
PostOrder(RightChild(i));
if (data[i] != 0)
{
Console.Write(data[i] + " ");
}
}使用实例
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Other
{
/// <summary>
/// 二叉排序树（Binary Sort Tree）
/// 二叉查找树（Binary Search Tree）
/// </summary>
public class Tree
{
/// <summary>
/// 数组存储树的结构(还有一种是Node)
/// </summary>
private int[] data;//从1开始存储数据
/// <summary>
/// 树的长度
/// </summary>
private int len;
/// <summary>
/// 删除节点时用的一个临时的数据结构
/// </summary>
private List<int> tmpList;
public Tree()
{
//先初始化一个1w大小的数组
this.data = http://www.mamicode.com/new int[100];> static void Main(string[] args)
{
Tree t = new Tree();
t.Insert(50);
t.Insert(20);
t.Insert(60);
t.Insert(15);
t.Insert(30);
t.Insert(70);
//从第一个位置开始
t.InOrder(1);
Console.WriteLine();
t.Delete(20);
t.InOrder(1);
}
c#使用数组实现二叉查找树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。