閑著無事，寫寫二叉查找樹用C#的簡單實現。 二叉查找樹是二叉樹的一種特別類型，特點是小值在父節點的左邊，其余值在其右邊，對排序、值查找有很好的支持。據說應用很廣泛，但是我還沒在項目中用到過。 1，結構分析 樹由節點組成，首先對節點結構進行分析。這里使用雙向鏈表的思想來確定節點與節點間的關系。 a，屬性： 1，父級節點 2，左子節點 3，右子節點 4，節點數據 為了方便，還加上HasChild屬性、重寫ToString方法。下面是泛型代碼： public class TreeNode<T>
{
public T Data
{
get;
set;
}

public TreeNode<T> Parent
{
get;
set;
}

public TreeNode<T> Left
{
get;
set;
}

public TreeNode<T> Right
{
get;
set;
}

public bool HasChild
{
get
{
if (this.Left != null || this.Right != null)
{
return true;
}
return false;
}
}

public override string ToString()
{
return string.Format("Data:{0} Parent:{1} Left:{2} Right:{3} HasChild:{4}", Data, Parent == null ? "null" : Parent.Data.ToString(), Left == null ? "null" : Left.Data.ToString(), Right == null ? "null" : Right.Data.ToString(), HasChild.ToString());
}
} 然后，對樹本身結構進行分析。為了防止數據結構在外部被破壞，3個屬性都為只讀。 a，私有字段： 1，根節點 a，只讀屬性： 1，節點數量 2，最大值 3，最小值 b，方法 1，插入 2，查找 3，刪除 5，遍歷 2，算法分析 插入： a，如果根節點為null，設為根節點。 b，把根節點設為當前節點，如果新節點的值小于當前節點的值，把當前節點設為當前節點的左子節點。反側，設為其右子節點。直到當前節點的左（右）子節點為null，把新節點插入到這個位置，并把新節點的父級節點設為當前節點。 c，節點數量加1。 public void Insert(T item)
{
TreeNode<T> node = new TreeNode<T>()
{
Data = item
};
if (root == null)
{
root = node;
}
else
{
TreeNode<T> current = root;
while (current != null)
{
if (current.Data.CompareTo(item) > -1)
{
if (current.Left == null)
{
node.Parent = current;
current.Left = node;
current = null;
}
else
{
current = current.Left;
}
}
else
{
if (current.Right == null)
{
node.Parent = current;
current.Right = node;
current = null;
}
else
{
current = current.Right;
}
}
}
}
count++;
} 最大值、最小值：二叉查找樹找最大值和最小值是再容易不過的事了，最底層最左的節點有最小值，最右的節點有最大值。 public T Min
{
get
{
TreeNode<T> current = root;
while (current.Left != null)
{
current = current.Left;
}
return current.Data;
}
}

public T Max
{
get
{
TreeNode<T> current = root;
while (current.Right != null)
{
current = current.Right;
}
return current.Data;
}
} 查找特定值： a，把根節點設為當前節點，如果查找值等于當前節點的值，返回當前節點。 b，如果查找的值小于當前節點的值，把當前節點設為其右子節點。反側，設為其左子節點。直到當前節點為null，返回null。 public TreeNode<T> Find(T item)
{
TreeNode<T> current = root;
while (!current.Data.Equals(item))
{
if (current.Data.CompareTo(item) < 0)
{
current = current.Right;
}
else
{
current = current.Left;
}
if (current == null)
{
return null;
}
}
return current;
} 遍歷： 二叉查找樹常用的3種遍歷方法：中序遍歷、先序遍歷和后序遍歷。中序遍歷是按照值的升序順序訪問所有節點的，雖然我很想寫清楚這3個方法，無賴語文不怎么好，直接上代碼吧。 /// <summary>
/// 中序遍歷
/// </summary>
/// <param name="node"></param>
private void InOrder(TreeNode<T> node)
{
if (node != null)
{
InOrder(node.Left);
Console.Write(node.Data.ToString() + " ");
InOrder(node.Right);
}
}

/// <summary>
/// 先序遍歷
/// </summary>
/// <param name="node"></param>
private void PreOrder(TreeNode<T> node)
{
if (node != null)
{
Console.Write(node.Data.ToString() + " ");
InOrder(node.Left);
InOrder(node.Right);
}
}

/// <summary>
/// 后序遍歷
/// </summary>
/// <param name="node"></param>
private void PostOrder(TreeNode<T> node)
{
if (node != null)
{
InOrder(node.Left);
InOrder(node.Right);
Console.Write(node.Data.ToString() + " ");
}
} 刪除： 由于二叉查找樹特殊的結構，刪除時需要對樹進行重構，因此刪除算法是比較復雜的。 a，要刪除的節點如果沒有子節點，直接刪除（去除引用）。 b，如果有一個子節點，用子節點頂替該節點位置。 c，如果有兩個子節點，使用中序遍歷，用該節點的右子節點的最左節點頂替該節點位置。 d，節點數量減1。 其實刪除和頂替，還可以分解為更細的算法步驟，為了理解，所以就不說那么細，直接看代碼： public void Remove(T item)
{
TreeNode<T> current = this.Find(item);
if (current == null)
{
return;
}
this.count--;
bool isLeftNode = false;
if (current != root)
{
isLeftNode = current.Parent.Data.CompareTo(item) == 1;
}
if (current.HasChild)
{
if (current.Left != null && current.Right != null)
{
TreeNode<T> temp = current.Right;
TreeNode<T> node = current.Right;
while (temp != null)
{
node = temp;
temp = temp.Left;
}
if (node.HasChild)
{
node.Right.Parent = node.Parent;
node.Parent.Left = node.Right;
}
else
{
node.Parent.Left = null;
}
node.Parent = current.Parent;

if (node != current.Right)
{
node.Right = current.Right;
current.Right.Parent = node;
}

node.Left = current.Left;
current.Left.Parent = node;

if (current != root)
{
if (isLeftNode)
{
current.Parent.Left = node;
}
else
{
current.Parent.Right = node;
}
}
else
{
this.root = node;
}
}
else
{
if (current == root)
{
this.root = current.Left == null ? current.Right : current.Left;
}
else
{
if (isLeftNode)
{
current.Parent.Left = current.Left == null ? current.Right : current.Left;
}
else
{
current.Parent.Right = current.Right == null ? current.Left : current.Right;
}
}
}
}
else
{
if (current == this.root)
{
this.root = null;
}
else if (isLeftNode)
{
current.Parent.Left = null;
}
else
{
current.Parent.Right = null;
}
}
}

轉載于:https://www.cnblogs.com/jameslu/archive/2011/04/11/2012340.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的二叉查找树(一)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。