//节点实体类
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace AVLTreeTool
{
public class TreeNode<T,T2>
{
/// <summary>
/// 前驱结点
/// </summary>
private TreeNode<T, T2> hNode;
public TreeNode<T, T2> HNode
{
get { return hNode; }
set { hNode = value; }
}
/// <summary>
/// 左子树
/// </summary>
private TreeNode<T,T2> lNode;
public TreeNode<T,T2> LNode
{
get { return lNode; }
set { lNode = value; }
}
/// <summary>
/// 右子树
/// </summary>
private TreeNode<T,T2> rNode;
public TreeNode<T,T2> RNode
{
get { return rNode; }
set { rNode = value; }
}
/// <summary>
/// 平衡因子
/// </summary>
private int bal=0;
public int Bal
{
get { return bal; }
set { bal = value; }
}
/// <summary>
/// 值
/// </summary>
private T value;
public T Value
{
get { return this.value; }
set { this.value = value; }
}
/// <summary>
/// 值为value对应的选项列表
/// </summary>
private HashSet<T2> havalue;
public HashSet<T2> Havalue
{
get { return havalue; }
set { havalue = value; }
}
}
}
//AVL操作类
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace AVLTreeTool
{
public class AVLTreeOPer
{
private TreeNode<int, string> _root;
private int p;//记录_root的节点个数。
#region
/// <summary>
/// 根据最大价格（maxid）和最小价格（minid）获取货物名称列表
/// </summary>
/// <param name="minid"></param>
/// <param name="maxid"></param>
/// <returns></returns>
public Dictionary<int, List<string>> findTreeNodeByRange(int minid, int maxid)
{
return new Dictionary<int, List<string>>();
}
/// <summary>
/// 根据价格获取货物名称列表
/// </summary>
/// <param name="Id"></param>
/// <returns></returns>
public List<string> findTreeNodeById(int Id)
{
if (null != _root)
{
TreeNode<int, string> potNode = _root;
int potvalue = _root.Value;
TreeNode<int, string> lnode = _root.LNode;
TreeNode<int, string> rnode = _root.RNode;
HashSet<string> rets = _root.Havalue;
while (Id != potvalue)
{
if (Id < potvalue)
{
if (null != lnode.Value)
{
potvalue = lnode.Value;
lnode = lnode.LNode;
rnode = lnode.RNode;
rets = lnode.Havalue;
}
else
break;
}
else
{
if (null != rnode.Value)
{
potvalue = rnode.Value;
lnode = rnode.LNode;
rnode = rnode.RNode;
rets = rnode.Havalue;
}
else
break;
}
}
if (potvalue == Id)
return rets.ToList();
else
return new List<string>();
}
else
return new List<string>();
}
/// <summary>
/// 判断改价格是否存在（存在返回true，不存在返回false）
/// </summary>
/// <param name="Id"></param>
/// <returns></returns>
public bool isExsist(int Id)
{
if (null != _root)
{
int potvalue = _root.Value;
TreeNode<int, string> lnode = _root.LNode;
TreeNode<int, string> rnode = _root.RNode;
HashSet<string> rets = _root.Havalue;
while (Id != potvalue)
{
if (Id < potvalue)
{
if (null != lnode)
{
potvalue = lnode.Value;
lnode = lnode.LNode;
rnode = lnode.RNode;
rets = lnode.Havalue;
}
else
break;
}
else
{
if (null != rnode)
{
potvalue = rnode.Value;
lnode = rnode.LNode;
rnode = rnode.RNode;
rets = rnode.Havalue;
}
else
break;
}
}
if (potvalue == Id)
return true;
else
return false;
}
else
return false;
}
#endregion
/// <summary>
/// 查找最接近的value值的节点
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public TreeNode<int, string> FindTreeNodeByValue(int value)
{
if (null != _root)
{
TreeNode<int, string> potNode = _root;
while (value != potNode.Value)
{
if (value < potNode.Value)
{
if (potNode.LNode != null)
potNode = potNode.LNode;
else
break;
}
else
{
if (potNode.RNode != null)
potNode = potNode.RNode;
else
break;
}
}
return potNode;
}
return null;
}
//根据叶子节点回溯得到最小的不平衡祖先节点
/// <summary>
/// 根据叶子节点回溯得到最小的不平衡祖先节点
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
public TreeNode<int, string> FindTreeNodeByNode(TreeNode<int, string> node)
{
if (node == null)
return null;
TreeNode<int, string> hnode = node;
while (hnode.Bal == 0)
{
if (hnode != null && hnode.HNode!=null)
hnode = hnode.HNode;
else
break;
}
return hnode;
}
//回溯到最小不平衡点修改各个祖先的平衡因子
/// <summary>
/// 回溯到最小不平衡点修改各个祖先的平衡因子
/// </summary>
/// <param name="hn"></param>
/// <param name="potn"></param>
/// <param name="bacn"></param>
/// <param name="value"></param>
/// <param name="name"></param>
public void AddNodeBackOper(TreeNode<int, string> hn, TreeNode<int, string> potn, int value, string name)
{
try
{
TreeNode<int, string> newNode = new TreeNode<int, string>();
newNode.Value = value;
newNode.Havalue = new HashSet<string>();
newNode.Havalue.Add(name);
newNode.Bal = 0;
newNode.HNode = potn;
if (value < potn.Value)
potn.LNode = newNode;
else
potn.RNode = newNode;
TreeNode<int, string> baNode = newNode;
if (value < hn.Value)
{
while (baNode.Value < hn.Value)
{
if (baNode.Value < baNode.HNode.Value)
baNode.HNode.Bal = baNode.HNode.Bal + 1;
else
baNode.HNode.Bal = baNode.HNode.Bal - 1;
baNode = baNode.HNode;
}
}
else
{
while (baNode.Value > hn.Value)
{
if (baNode.Value < baNode.HNode.Value)
baNode.HNode.Bal = baNode.HNode.Bal + 1;
else
baNode.HNode.Bal = baNode.HNode.Bal - 1;
baNode = baNode.HNode;
}
}
}
catch
{
}
}
//根据value和name添加节点
/// <summary>
/// 根据value和name添加节点
/// </summary>
/// <param name="value"></param>
/// <param name="name"></param>
public void AddNode(int value,string name)
{
try
{
TreeNode<int, string> potNode = FindTreeNodeByValue(value);//查找最接近的value值的节点
TreeNode<int, string> hNode = FindTreeNodeByNode(potNode);//根据叶子节点回溯得到最近的不平衡祖先节点
if (potNode != null) //存在最接近value值的节点说明_root不是一棵空树
{
TreeNode<int, string> hhNode = hNode.HNode;//最小不平衡点的父节点。
if (potNode.Value == value) //存在相同value值的节点则将新的name值存入该value值对应的hash列表
{
if (!potNode.Havalue.Contains(name))
potNode.Havalue.Add(name);
}
else
{
TreeNode<int, string> newnode = new TreeNode<int, string>();
if (hNode.Bal == -1)//最近不平衡祖先节点的右子树高于左子树。
{
if (value < hNode.Value)//插入值小于不平衡祖先节点的值插入左子树无需平衡调整，只需修改各级祖先的平衡因子
{
AddNodeBackOper(hNode, potNode, value, name);//回溯到最小不平衡点修改各个祖先的平衡因子
return;
}
else
{
if (value > hNode.RNode.Value)//插入值大于不平衡点的右儿子的值
newnode = rrAdjustment(hNode); //rr调整
else//value<hNode.RNode.Value 插入值小于不平衡点的右儿子的值
newnode = rlAdjustment(hNode, value, name);//rl调整
hNode = newnode; //将返回的平衡节点替换不平衡节点
}
}
else if (hNode.Bal == 1)//最近不平衡祖先节点的左子树高于右子树。
{
if (value > hNode.Value)//插入值大于不平衡祖先节点的值插入右子树无需平衡调整，只需修改各级祖先的平衡因子
{
AddNodeBackOper(hNode, potNode, value, name);//回溯到最小不平衡点修改各个祖先的平衡因子
return;
}
else
{
if (value < hNode.LNode.Value)//LL 调整
newnode = llAdjustment(hNode);
else//value > hNode.LNode.Value//LR调整
newnode = lrAdjustment(hNode, value, name);
hNode = newnode;
}
}
AddNodeBackOper(hNode, potNode, value, name);//回溯到最小不平衡点修改各个祖先的平衡因子
if (hhNode == null)//最近不平衡点的父节点不存在说明最近不平衡点就是根节点
_root = hNode;
else //将最近不平衡点的父节点关联平衡调整后的子节点
{
hNode.HNode = hhNode;
if (hhNode.Value > hNode.Value)
hhNode.LNode = hNode;
else
hhNode.RNode = hNode;
}
}
}
else//不存在最接近value值的节点说明_root树是一棵空树
{
TreeNode<int, string> newnode = new TreeNode<int, string>();
newnode.Bal = 0;
newnode.Value = value;
HashSet<string> has = new HashSet<string>();
has.Add(name);
newnode.Havalue = has;
_root = newnode;
}
}
catch
{
}
}
//右右调整
/// <summary>
/// 右右调整
/// </summary>
public TreeNode<int,string> rrAdjustment(TreeNode<int, string> hnode)
{
try
{
TreeNode<int, string> AH = hnode.HNode;
TreeNode<int, string> A = hnode;
TreeNode<int, string> B = hnode.RNode;
TreeNode<int, string> AL = hnode.LNode;
TreeNode<int, string> BL = hnode.RNode.LNode;
A.RNode = BL;
B.LNode = A;
B.HNode = AH;
A.HNode = B;
A.Bal = 0;
B.Bal = 1;
return B;
}
catch
{
return new TreeNode<int,string>();
}
}
//左左调整
/// <summary>
/// 左左调整
/// </summary>
public TreeNode<int,string> llAdjustment(TreeNode<int,string> hnode)
{
try
{
TreeNode<int, string> BH = hnode.HNode;
TreeNode<int, string> B = hnode;
TreeNode<int, string> A = hnode.LNode;
TreeNode<int, string> AR = hnode.LNode.RNode;
TreeNode<int, string> BR = hnode.RNode;
B.LNode = AR;
A.RNode = B;
A.HNode = BH;
B.HNode = A;
B.Bal = 0;
A.Bal = -1;
return A;
}
catch
{
return new TreeNode<int, string>();
}
}
//左右调整
/// <summary>
/// 左右调整
/// </summary>
/// <param name="hnode">//传入的最近不平衡点</param>
/// <param name="value">新节点的key值</param>
/// <param name="name">新节点的key值新增的对应的hash列表值</param>
/// <returns></returns>
public TreeNode<int, string> lrAdjustment(TreeNode<int, string> hnode,int value,string name)
{
try
{
TreeNode<int, string> CH = hnode.HNode;
TreeNode<int, string> C = hnode;//最近不平衡点
TreeNode<int, string> A = hnode.LNode;//最近不平衡点的左子树
TreeNode<int, string> B = hnode.LNode.RNode;//最近不平衡点的左子树的右子树
if (B != null) //最近不平衡点的左子树的右子树不为空
{
TreeNode<int, string> BL = B.LNode;
TreeNode<int, string> BR = B.RNode;
if (BL != null)
{
A.RNode = BL;
BL.HNode = A;
}
if (BR != null)
{
C.LNode = BR;
BR.HNode = C;
}
}
else //最近不平衡点的左子树的右子树为空 则将新的节点值作为不平衡节点的右子树
{
B = new TreeNode<int, string>();
B.Value = value;
HashSet<string> has = new HashSet<string>();
has.Add(name);
B.Havalue = has;
}
C.LNode = B.RNode;
A.RNode = B.LNode;
B.LNode = A;
B.RNode = C;
A.HNode = B;
C.HNode = B;
int dif = value - B.Value > 0 ? 1 : (value - B.Value<0 ? -1 : 0) ;
switch (dif)
{
case 1:
C.Bal = 0;A.Bal = 1;break;
case -1:
C.Bal = -1;A.Bal = 0;break;
default:
C.Bal = 0;A.Bal = 0;break;
}
return B;
}
catch
{
return new TreeNode<int, string>();
}
}
//右左调整
/// <summary>
/// 右左调整
/// </summary>
public TreeNode<int, string> rlAdjustment(TreeNode<int, string> hnode,int value,string name)
{
try
{
TreeNode<int, string> CH = hnode.HNode;//最近不平衡节点的父节点
TreeNode<int, string> C = hnode; //最近不平衡节点
TreeNode<int, string> A = hnode.RNode; //最近不平衡节点的右子树
TreeNode<int, string> B = hnode.RNode.LNode;//最近不平衡节点的右儿子的左子树
if (B != null)
{
TreeNode<int, string> BL = B.LNode;
TreeNode<int, string> BR = B.RNode;
if (BR != null)
{
A.LNode = BR;
BR.HNode = A;
}
if (BL != null)
{
C.RNode = BL;
BL.HNode = C;
}
}
else
{
B = new TreeNode<int, string>();
B.Value = value;
HashSet<string> has = new HashSet<string>();
has.Add(name);
B.Havalue = has;
}
C.RNode = B.LNode;
A.LNode = B.RNode;
B.LNode = C;
B.RNode = A;
A.HNode = B;
C.HNode = B;
int dif = value - B.Value > 0 ? 1 : (value - B.Value < 0 ? -1 : 0);
switch (dif)
{
case 1:
C.Bal = 0;A.Bal=-1;break;
case -1:
C.Bal = 1;A.Bal=0;break;
default:
C.Bal = 0;A.Bal=0;break;
}
return B;
}
catch
{
return new TreeNode<int, string>();
}
}
public void ReadAVLTreeOper()
{
}
#region//草稿
/// <summary>
/// 向平衡二叉树添加结点。
/// </summary>
/// <param name="Id"></param>
/// <param name="name"></param>
public void Add(int Id, string name)
{
if (null != _root)
{
TreeNode<int, string> potNode = _root;
TreeNode<int, string> hnode = null;
TreeNode<int, string> baNode = null;
while (Id != potNode.Value)
{
if (Id < potNode.Value)
{
if (potNode.LNode!=null)
potNode = potNode.LNode;
else
break;
}
else
{
if (potNode.RNode!=null)
potNode = potNode.RNode;
else
break;
}
}
if (potNode.Value == Id)
{
if (!potNode.Havalue.Contains(name))
potNode.Havalue.Add(name);
}
else//没有找到值为Id的下层节点。
{
while (hnode.Bal == 0)
{
if (null != hnode.HNode)
hnode = hnode.HNode;
else
break;
}
if (hnode!= null)
{
TreeNode<int, string> newNode = new TreeNode<int, string>();
newNode.Value = Id;
newNode.Bal = 0;
newNode.Havalue = new HashSet<string>();
newNode.Havalue.Add(name);
newNode.HNode = potNode;
if (hnode.Bal == -1)
{
if (Id < hnode.Value)
{
if (Id >potNode.Value)
potNode.RNode = newNode;
else
potNode.LNode = newNode;
baNode = newNode;
while (baNode.Value<hnode.Value)
{
if (baNode.Value < baNode.HNode.Value)
baNode.HNode.Bal = baNode.HNode.Bal + 1;
else
baNode.HNode.Bal = baNode.HNode.Bal - 1;
baNode = baNode.HNode;
}
}
else
{
if (Id > hnode.RNode.Value)//rr调整
{
TreeNode<int, string> AH = hnode.HNode;
TreeNode<int, string> A = hnode;
TreeNode<int,string> B=hnode.RNode;
TreeNode<int, string> AL = hnode.LNode;
TreeNode<int, string> BL = hnode.RNode.LNode;
TreeNode<int, string> BR = hnode.RNode.RNode;
A.RNode = BL;
A.HNode = B;
B.HNode = AH;
B.LNode = A;
if (B.Value < AH.Value)
AH.LNode = B;
else
AH.RNode = B;
}
else //（Id <hnode.RNode.Value）rl调整
{
}
}
}
else//hnode.Bal == 1
{
if (Id > hnode.Value)
{
if (Id > potNode.Value)
potNode.RNode = newNode;
else
potNode.LNode = newNode;
baNode = newNode;
while (baNode.Value > hnode.Value)
{
if (baNode.Value < baNode.HNode.Value)
baNode.HNode.Bal = baNode.HNode.Bal + 1;
else
baNode.HNode.Bal = baNode.HNode.Bal - 1;
baNode = baNode.HNode;
}
}
else
{
if (Id > hnode.LNode.Value)//lr调整
{
}
else //（Id <hnode.LNode.Value）ll调整
{
}
}
}
}
}
}
}
#endregion
}
}
//AvL测试入口
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using AVLTreeTool;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
AddNodes();
AddNode();
//test();
}
public static void AddNode()
{
AVLTreeOPer client = new AVLTreeOPer();
client.AddNode(9,"hujiapeng");
}
public static void AddNodes()
{
AVLTreeOPer client = new AVLTreeOPer();
Random ra = new Random();
for (int i = 30; i >= 0; i--)
{
int rdt = ra.Next(100);
client.AddNode(rdt, "hujiapeng" + rdt);
//client.AddNode(i, "hujiapeng" + i);
if (i == 1)
{
continue;
}
}
}
}
}