创建二叉查找树、查找二叉树中的某个节点、删除某个节点、
新增节点、查找某个节点的父节点、查找最小节点
对二叉树进行前序遍历、中序遍历、后序遍历
前序遍历，也叫先根遍历，遍历的顺序是，根，左子树，右子树
中序遍历，也叫中根遍历，顺序是 左子树，根，右子树
后序遍历，也叫后根遍历，遍历顺序，左子树，右子树，根
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SuanFa
{
public class Order
{
//创建二分查找树
public Tree CreateBinaryTree(int[] A)
{
if (A == null || A.Length == 0)
{
return null;
}
Tree root = new Tree(A[0]); //根节点 相当于表头指针
Tree treeNode,temp;//要添加的节点和中间节点
for (int i = 1; i < A.Length; i++)
{
temp = root;
treeNode = new Tree(A[i]);
AddTreeNode(temp, treeNode);
}
return root;
}
//添加树节点
private void AddTreeNode(Tree tree, Tree node)
{
if (node.Text < tree.Text)//添加左子节点
{
if (tree.LeftTree.Count == 0)
{
tree.LeftTree.Add(node);
}
else {
AddTreeNode(tree.LeftTree[0], node);
}
}
else if (node.Text > tree.Text)//添加右子节点
{
if (tree.RightTree.Count == 0)
{
tree.RightTree.Add(node);
}
else
{
AddTreeNode(tree.RightTree[0], node);
}
}
}
//查找某个节点
public Tree Find(Tree root,int text) {
if (root == null)//如果当前节点为null 返回null
{
return null;
}
if (root.Text == text)//如果等于当前节点就返回当前节点
{
return root;
}
if (root.LeftTree.Count > 0)//递归左子树
{
if (root.Text > text)
{
return Find(root.LeftTree[0],text);
}
}
if (root.RightTree.Count > 0)//递归右子树
{
if (root.Text<text)
{
return Find(root.LeftTree[0], text);
}
}
return null;//没找到返回null
}
//查找某个节点的父节点
public Tree FindF(Tree root, int text)
{
if (root == null)//如果当前节点为null 返回null
{
return null;
}
if (root.LeftTree.Count > 0)
{
if (root.LeftTree[0].Text == text)//如果等于当前节点的左子节点就返回当前节点
{
return root;
}
if (root.Text > text)//递归左子树
{
return FindF(root.LeftTree[0], text);
}
}
if (root.RightTree.Count > 0)
{
if (root.RightTree[0].Text == text)//如果等于当前节点的右子节点就返回当前节点
{
return root;
}
if (root.Text < text)//递归右子树
{
return FindF(root.RightTree[0], text);
}
}
return null;//没找到返回null
}
//前序遍历
public int DLR(Tree tree,List<int> list)
{
if (tree == null || list == null)
{
return 0;
}
list.Add(tree.Text); //根节点
if (tree.LeftTree.Count > 0) //先遍历左子树
{
DLR(tree.LeftTree[0],list);
}
if (tree.RightTree.Count > 0) //右子树
{
DLR(tree.RightTree[0], list);
}
if (list.Count > 0)
return 1;
return 0;
}
//后序遍历
public int LRD(Tree tree, List<int> list)
{
if (tree == null || list == null)
{
return 0;
}
if (tree.LeftTree.Count > 0) //先遍历左子树
{
LRD(tree.LeftTree[0], list);
}
if (tree.RightTree.Count > 0) //右子树
{
LRD(tree.RightTree[0], list);
}
list.Add(tree.Text); //根节点
if (list.Count > 0)
return 1;
return 0;
}
//中序遍历
public int LDR(Tree tree, List<int> list)
{
if (tree == null || list == null)
{
return 0;
}
if (tree.LeftTree.Count > 0) //先遍历左子树
{
LDR(tree.LeftTree[0], list);
}
list.Add(tree.Text); //根节点
if (tree.RightTree.Count > 0) //右子树
{
LDR(tree.RightTree[0], list);
}
if (list.Count > 0)
return 1;
return 0;
}
//删除节点
//1：节点不存在
//2：节点存在且没有子树
//3：节点存在且有左子树，用以要删除节点为根节点树的最小节点代替当前节点
//4；节点存在且只有右子树，用药删除节点的右子节点代替当前节点
public Tree Delete(Tree tree, int text)
{
if (tree == null)
{
return null;
}
Tree newTree = tree;
//要删除节点的父节点
Tree delFNode = FindF(newTree, text);
//要删除的节点
Tree delNode;
bool isleft = true;//标识被删节点是其所在树的左子节点还是右子节点
if (delFNode == null)//要删除的节点父节点为空有两种情况。1不存在；2是根节点
{
delNode = Find(newTree, text);
if (delNode == null)//不存在
{
return newTree;
}
Tree tmp;
if (delNode.LeftTree.Count > 0)//存在左子树
{
tmp = FindMin(delNode);
Tree tmpF = FindF(delNode, tmp.Text);
tmpF.LeftTree.Remove(tmp);
tmp.LeftTree.Add(delNode.LeftTree[0]);
if (delNode.RightTree.Count > 0)
{
tmp.RightTree.Add(delNode.RightTree[0]);
}
newTree = tmp;
}
else if (delNode.RightTree.Count > 0)//只有右子树
{
newTree = delNode.RightTree[0];
}
return newTree;
}//要删除的节点是左子树
else if (delFNode.LeftTree.Count > 0 && delFNode.LeftTree[0].Text == text)
{
delNode = delFNode.LeftTree[0];
isleft = true;
}//要删除的节点是右子树
else if (delFNode.RightTree.Count > 0 && delFNode.RightTree[0].Text == text)
{
delNode = delFNode.RightTree[0];
isleft = false;
}
else//要删除的节点不存在
{
return newTree;
}
Tree temp;
//如果存在左子树，就用左子树的最小节点取代要删除的节点，并删除这个最小节点
if (delNode.LeftTree.Count > 0)
{
temp = FindMin(delNode);
Tree tempDelNode = delNode;
while (tempDelNode.LeftTree.Count > 0)
{
tempDelNode = tempDelNode.LeftTree[0];
}
if (temp.Text != delNode.LeftTree[0].Text)
{
temp.LeftTree.Add(delNode.LeftTree[0]);
}
delNode.LeftTree.Remove(tempDelNode);
//把要删除节点的右子树作为最小节点的右子树
if (delNode.RightTree.Count > 0)
{
temp.RightTree.Add(delNode.RightTree[0]);
}
if (isleft)
{
delFNode.LeftTree.Add(temp);
delFNode.LeftTree.Remove(delNode);
}
else
{
delFNode.RightTree.Add(temp);
delFNode.RightTree.Remove(delNode);
}
}
else if (delNode.RightTree.Count > 0)
{
delFNode.RightTree.Add(delNode.RightTree[0]);
}
return newTree;
}
//查找最小节点
public Tree FindMin(Tree tree)
{
if (tree == null)
{
return null;
}
//如果当前节点没有左子树就返回他自己
if (tree.LeftTree.Count == 0)
{
return tree;
}
//递归左子树
return FindMin(tree.LeftTree[0]);
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SuanFa
{
public class Tree
{
//显示的值
public int Text
{
set;
get;
}
//构造函数
public Tree(int text) {
this.Text = text;
if (LeftTree == null)
{
LeftTree = new List<Tree>();
}
if (RightTree == null)
{
RightTree = new List<Tree>();
}
}
//左子树
public List<Tree> LeftTree
{
set;
get;
}
//右子树
public List<Tree> RightTree
{
set;
get;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SuanFa
{
class Program
{
static void Main(string[] args)
{
int[] B = new int[] { 50,25,75,15,35,65,85,10,20,30,40,60,70,80,90 };
Order order = new Order();
Tree tree= order.CreateBinaryTree(B);
Console.Write("原先数组：");
foreach (int i in B)
{
Console.Write(i.ToString() + " ");
}
Console.WriteLine();
Console.Write("----------------------------形成二叉查找树--------------------------");
Console.WriteLine();
Console.WriteLine("删除前:");
Console.WriteLine();
Show(B, order, tree);
Console.WriteLine();
Console.WriteLine();
Tree newTree = order.Delete(tree,50);
Console.WriteLine("删除跟节点50后:");
Console.WriteLine();
Show(B, order, newTree);
Console.WriteLine();
Console.WriteLine();
Tree newTree1 = order.Delete(newTree, 65);
Console.WriteLine("删除65后:");
Console.WriteLine();
Show(B, order, newTree1);
Console.ReadLine();
}
private static void Show(int[] B, Order order, Tree tree)
{
List<int> listDlr = new List<int>();
if (order.DLR(tree, listDlr) > 0)
{
Console.Write("前序遍历：");
foreach (int i in listDlr)
{
Console.Write(i.ToString() + " ");
}
Console.WriteLine();
Console.WriteLine();
}
List<int> listLrd = new List<int>();
if (order.LRD(tree, listLrd) > 0)
{
Console.Write("后序遍历：");
foreach (int i in listLrd)
{
Console.Write(i.ToString() + " ");
}
Console.WriteLine();
Console.WriteLine();
}
List<int> listLdr = new List<int>();
if (order.LDR(tree, listLdr) > 0)
{
Console.Write("中序遍历：");
foreach (int i in listLdr)
{
Console.Write(i.ToString() + " ");
}
}
}
}
}
