树的高度总是返回0
本文关键字:返回 高度 | 更新日期: 2023-09-27 17:54:42
嗨,我有这个AVLTree,但我只是不能使高度方法工作。它总是给出零。你们谁能看一下,也许能发现我遗漏了什么。正如你所看到的,我尝试了不同的解决方案,但我不知道。那会节省时间的。谢谢!
public class AVLTree2<TKey, TValue> : BinarySearchTree<TKey, TValue>
where TKey : IComparable<TKey>
{
private AVLNode node;
int count;
/// <summary>
/// Initializes a new instance of the AVLTree<TKey, TValue> class that is empty.
/// </summary>
public AVLTree2() { node = null;}
/// <summary>
/// Initializes a new instance of the AVLTree<TKey, TValue> class that contains elements copied from the specified IDictionary<TKey, TValue>.
/// </summary>
/// <param name="collection">The IDictionary<TKey, TValue> whose elements are copied to the new AVLTree<TKey, TValue>.</param>
public AVLTree2(IDictionary<TKey, TValue> collection) : base(collection)
{
foreach (KeyValuePair<TKey, TValue> t in collection)
this.Add(t.Key, t.Value);
}
/// <summary>
/// Adds the specified key and value to the AVLTree<TKey, TValue>.
/// </summary>
/// <param name="key">The key of the element to add.</param>
/// <param name="value">The value of the element to add.</param>
///
public new int Count()
{
return count;
}
public override void Add(TKey key, TValue value)
{
AVLNode node = new AVLNode(key, value);
base.Add(node);
this.Rebalance(node.Parent);
this.count++;
}
public override void Delete(TreeNode current)
{
base.Delete(current);
this.Rebalance((AVLNode)current.Parent);
this.count--;
}
private void Rebalance(AVLNode start)
{
int height, left, right, diff, leftC, rightC, diffC;
while (start != null)
{
height = start.Height;
left = start.Left != null ? start.Left.Height : -1;
right = start.Right != null ? start.Right.Height : -1;
diff = left - right;
if (diff == -2)
{
leftC = start.Right.Left != null ? start.Right.Left.Height : -1;
rightC = start.Right.Right != null ? start.Right.Right.Height : -1;
diffC = leftC - rightC;
if (diffC == 1)
this.RotateRight(start.Right);
this.RotateLeft(start);
start = start.Parent.Parent;
continue;
}
else if (diff == 2)
{
leftC = start.Left.Left != null ? start.Left.Left.Height : -1;
rightC = start.Left.Right != null ? start.Left.Right.Height : -1;
diffC = leftC - rightC;
if (diffC == -1)
this.RotateLeft(start.Left);
this.RotateRight(start);
start = start.Parent.Parent;
continue;
}
start.Height = Math.Max(left, right) + 1;
if (height == start.Height)
break;
else
start = start.Parent;
}
}
protected void RotateLeft(AVLNode start)
{
base.RotateLeft(start);
int left, right;
left = start.Left != null ? start.Left.Height : -1;
right = start.Right != null ? start.Right.Height : -1;
start.Height = Math.Max(left, right) + 1;
left = start.Height;
right = start.Parent.Right != null ? start.Parent.Right.Height : -1;
start.Parent.Height = Math.Max(left, right) + 1;
}
protected void RotateRight(AVLNode start)
{
base.RotateRight(start);
int left, right;
left = start.Left != null ? start.Left.Height : -1;
right = start.Right != null ? start.Right.Height : -1;
start.Height = Math.Max(left, right) + 1;
left = start.Parent.Left != null ? start.Parent.Left.Height : -1;
right = start.Height;
start.Parent.Height = Math.Max(left, right) + 1;
}
public int Height()
{
return height(node);
}
public int height(AVLNode start)
{
AVLNode temp = start;
if (temp == null)
return 0;
else if (start.Left == null && start.Right == null)
return 0;
else
return 1 + Math.Max(height(start.Left), height(start.Right));
}
public class AVLNode : KeyValueTreeNode
{
public AVLNode(TKey key, TValue value) : base(key, value) { this.Height = 0; }
public int Height { get; set; }
public new AVLNode Parent { get { return (AVLNode)base.Parent; } set { base.Parent = value; } }
public new AVLNode Left { get { return (AVLNode)base.Left; } set { base.Left = value; } }
public new AVLNode Right { get { return (AVLNode)base.Right; } set { base.Right = value; } }
}
}
}
您从未初始化node
。Height()
调用height(node)
和node==null
,所以height
返回0