数据结构（C#）-二叉查找树的先序，中序，后序的遍历有关问题以及最大值，最小值，插入，删除
// 学习小结 吴新强于2013年3月18日17:22:55 桂电 2057 实验室
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace ConsoleApplication1
{
class Program
{
// static void Main(string[] args)
static void Main()
{
BinarySearchTree nums = new BinarySearchTree();
// /*
nums.Insert(23);
nums.Insert(45);
nums.Insert(16);
nums.Insert(37);
nums.Insert(3);
nums.Insert(99);
nums.Insert(22);
// nums.GetSuccessor(nums.root);
Console.WriteLine("中序排序： ");//Inorder traversal
nums.InOrder(nums.root);
Console.WriteLine();
Console.WriteLine("先序排序： ");
nums.PreOrder(nums.root);
Console.WriteLine();
Console.WriteLine("后序排序: ");//Postorder traversal
nums.PostOrder(nums.root);
Console.WriteLine();
Console.WriteLine("序列中的最大值: " + nums.FindMax());//Max traversal
Console.WriteLine();
Console.WriteLine("序列中的最小值: " + nums.FindMin());//Min traversal:
Console.WriteLine();
Console.WriteLine("Find traversal: "+nums .Find(99));
Console.WriteLine();
Console.WriteLine("删除节点 99 : " + nums.Delete(99)+"\n反回true表示删除成功");//Delete traversal
Console.WriteLine("删除节点 4 : " + nums.Delete(4) + "\n反回flash表示删除序列中不存在这个值");
Console.WriteLine("删除后的中序排序： ");
nums.InOrder(nums.root);
Console.WriteLine();
// Console.WriteLine("Delete traversal: " + nums.GetSuccessor());
Console.WriteLine();
}
}
public class Node
{
public int Data;
public Node Left;
public Node Right;
public void DisplayNode()
{
Console.Write(Data + " ");
}
}
public class BinarySearchTree
{
public Node root;
public BinarySearchTree()
{
root = null;
}
public Node GetSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.Right;
while (!(current == null))
{
successorParent = current;
successor = current;
current = current.Left;
}
if (!(successor == delNode.Right))
{
successorParent.Left = successor.Right;
successor.Right = delNode.Right;
}
return successor;
}
public void PreOrder(Node theRoot)
{
if (!(theRoot == null))
{
theRoot.DisplayNode();
PreOrder(theRoot.Left);
PreOrder(theRoot.Right);
}
}
public void PostOrder(Node theRoot)
{
if (!(theRoot == null))
{
PostOrder(theRoot.Left);
PostOrder(theRoot.Right);
theRoot.DisplayNode();
}
}
public void InOrder(Node theRoot)
{
if (!(theRoot == null))
{
InOrder(theRoot.Left);
theRoot.DisplayNode();
InOrder(theRoot.Right);
}
}
public int FindMin()
{
Node current = root;
while (!(current.Left == null))
current = current.Left;
return current.Data;
}
public int FindMax()
{
Node current = root;
while (!(current.Right == null))
current = current.Right;
return current.Data;
}
public Node Find(int key)
{
Node current = root;
while (current.Data != key)
{
if (key < current.Data)
current = current.Left;
else
current = current.Right;
if (current == null)
return null;
}
return current;
}
public bool Delete(int key)
{
Node current = root;
Node parent = root;
bool isLeftChild = true;
while (current.Data != key)
{
parent = current;
if (key < current.Data)
{
isLeftChild = true;
current = current.Right;
}
else
{
isLeftChild = false;
current = current.Right;
}
if (current == null)
return false;
}
if ((current.Left == null) & (current.Right == null))
if (current == root)
root = null;
else if (isLeftChild)
parent.Left = null;
else if (current.Right == null)
if (current == root)
root = current.Left;
else if (isLeftChild)
parent.Left = current.Left;
else
parent.Right = current.Right;
else if (current.Left == null)
if (current == root)
root = current.Right;
else if (isLeftChild)
parent.Left = parent.Right;
else
parent.Right = current.Right;
else
{
Node successor = GetSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.Left = successor;
else
parent.Right = successor;
successor.Left = current.Left;
}
return true;
}
public void Insert(int i)
{
Node newNode = new Node();
newNode.Data = i;
if (root == null)
root = newNode;
else
{
Node current = root;
Node parent;
while (true)
{
parent = current;
if (i < current.Data)
{
current = current.Left;
if (current == null)
{
parent.Left = newNode;
break;
}
}
else
{
current = current.Right;
if (current == null)
{
parent.Right = newNode;
break;
}
}
}
}
}
}
}
运行结果截图：