算法學習--二叉查找樹
創(chuàng)建二叉查找樹、查找二叉樹中的某個節(jié)點、刪除某個節(jié)點、
新增節(jié)點、查找某個節(jié)點的父節(jié)點、查找最小節(jié)點
對二叉樹進行前序遍歷、中序遍歷、后序遍歷
前序遍歷，也叫先根遍歷，遍歷的順序是，根，左子樹，右子樹
中序遍歷，也叫中根遍歷，順序是 左子樹，根，右子樹
后序遍歷，也叫后根遍歷，遍歷順序，左子樹，右子樹，根
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SuanFa
{
public class Order
{
//創(chuàng)建二分查找樹
public Tree CreateBinaryTree(int[] A)
{
if (A == null || A.Length == 0)
{
return null;
}
Tree root = new Tree(A[0]); //根節(jié)點 相當于表頭指針
Tree treeNode,temp;//要添加的節(jié)點和中間節(jié)點
for (int i = 1; i < A.Length; i++)
{
temp = root;
treeNode = new Tree(A[i]);
AddTreeNode(temp, treeNode);
}
return root;
}
//添加樹節(jié)點
private void AddTreeNode(Tree tree, Tree node)
{
if (node.Text < tree.Text)//添加左子節(jié)點
{
if (tree.LeftTree.Count == 0)
{
tree.LeftTree.Add(node);
}
else {
AddTreeNode(tree.LeftTree[0], node);
}
}
else if (node.Text > tree.Text)//添加右子節(jié)點
{
if (tree.RightTree.Count == 0)
{
tree.RightTree.Add(node);
}
else
{
AddTreeNode(tree.RightTree[0], node);
}
}
}
//查找某個節(jié)點
public Tree Find(Tree root,int text) {
if (root == null)//如果當前節(jié)點為null 返回null
{
return null;
}
if (root.Text == text)//如果等于當前節(jié)點就返回當前節(jié)點
{
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
}
//查找某個節(jié)點的父節(jié)點
public Tree FindF(Tree root, int text)
{
if (root == null)//如果當前節(jié)點為null 返回null
{
return null;
}
if (root.LeftTree.Count > 0)
{
if (root.LeftTree[0].Text == text)//如果等于當前節(jié)點的左子節(jié)點就返回當前節(jié)點
{
return root;
}
if (root.Text > text)//遞歸左子樹
{
return FindF(root.LeftTree[0], text);
}
}
if (root.RightTree.Count > 0)
{
if (root.RightTree[0].Text == text)//如果等于當前節(jié)點的右子節(jié)點就返回當前節(jié)點
{
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); //根節(jié)點
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); //根節(jié)點
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); //根節(jié)點
if (tree.RightTree.Count > 0) //右子樹
{
LDR(tree.RightTree[0], list);
}
if (list.Count > 0)
return 1;
return 0;
}
//刪除節(jié)點
//1：節(jié)點不存在
//2：節(jié)點存在且沒有子樹
//3：節(jié)點存在且有左子樹，用以要刪除節(jié)點為根節(jié)點樹的最小節(jié)點代替當前節(jié)點
//4；節(jié)點存在且只有右子樹，用藥刪除節(jié)點的右子節(jié)點代替當前節(jié)點
public Tree Delete(Tree tree, int text)
{
if (tree == null)
{
return null;
}
Tree newTree = tree;
//要刪除節(jié)點的父節(jié)點
Tree delFNode = FindF(newTree, text);
//要刪除的節(jié)點
Tree delNode;
bool isleft = true;//標識被刪節(jié)點是其所在樹的左子節(jié)點還是右子節(jié)點
if (delFNode == null)//要刪除的節(jié)點父節(jié)點為空有兩種情況。1不存在；2是根節(jié)點
{
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;
}//要刪除的節(jié)點是左子樹
else if (delFNode.LeftTree.Count > 0 && delFNode.LeftTree[0].Text == text)
{
delNode = delFNode.LeftTree[0];
isleft = true;
}//要刪除的節(jié)點是右子樹
else if (delFNode.RightTree.Count > 0 && delFNode.RightTree[0].Text == text)
{
delNode = delFNode.RightTree[0];
isleft = false;
}
else//要刪除的節(jié)點不存在
{
return newTree;
}
Tree temp;
//如果存在左子樹，就用左子樹的最小節(jié)點取代要刪除的節(jié)點，并刪除這個最小節(jié)點
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);
//把要刪除節(jié)點的右子樹作為最小節(jié)點的右子樹
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;
}
//查找最小節(jié)點
public Tree FindMin(Tree tree)
{
if (tree == null)
{
return null;
}
//如果當前節(jié)點沒有左子樹就返回他自己
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;
}
//構(gòu)造函數(shù)
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("原先數(shù)組：");
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("刪除跟節(jié)點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() + " ");
}
}
}
}
}
浙公網(wǎng)安備 33010602011771號