说明:我做的这个部门表因为设计的部门多,修改频繁,所以可能双亲方法不是最好的!
树被应用于数据元素之间的关系以层级关系来表示的应用程序中。
一个二叉树就是每个节点只能最多拥有2个子节点的树结构。这些子节点一般被视为左子节点和右子节点。 二叉树有各种类型： 严格二叉树 满二叉树
完整二叉树
满二叉树 深度d的二叉树拥有刚好2d–1个节点。
完整二叉树： 指有 n 个节点且深度为 d，且其节点对应深度为k的完整二叉树中序号从0到n1 的节点。
假设有一家移动电话公司保存着它遍及全世界的数百万的客户信息。每个客户都分配有一个唯一的身份号（id）。可以通过各自id来读取每个客户的记录。这些id需要以排序后的方式进行存储，这样你就能轻松对这些数据进行事务操作，如搜索、插入和删除
你会用什么数据结构来存储客户的id？ 你可以使用一个数组吗？ 在数组中搜索操作是很快的。 然而，在数组中插入和删除却是很复杂的。 在这种情况下，要存储的客户id的数量是很大的。因此，插入和删除将会非常耗时。 你可以使用一个链接列表吗？ 在链接列表中插入和删除操作是很快的。 然而，链接列表仅允许顺序搜索。
如果你需要访问一个特定客户id（位于列表末端），那么就要求你访问所有前面的节点，这也将非常耗时。
二叉搜索树是每个节点都满足以下条件的二叉树： 节点的左子树的所有值小于该节点的值。(左子树的所有节点）
节点的右子树的所有值大于该节点的值。(右子树的所有节点）
你可以在二叉搜索树上执行各种操作： 遍历 搜索 插入
删除
要搜索特定值，你需要执行以下步骤： 1.将currentNode指向根节点。 2.如果 currentNode是null： a.显示”没发现“ b.退出 3.将需要搜索的值与currentNode的值进行比较。取决于比较结果，有三种可能性： a.如果该值等于currentNode的值： i. 显示”发现“ ii. 退出 b.如果该值小于currentNode的值： i. 将 currentNode指向它的左子节点 ii. 跳转到步骤 2 c.如果该值大于currentNode的值： i. 将 currentNode指向它的右子节点 ii. 跳转到步骤 2
在实施插入操作前，需要首先检查树是否为空。 如果树是空的，新节点将成为根节点。 如果树不是空的，就需要为要插入的新节点找到合适的位置。 这就要求你查找要插入的新节点的父节点。 一旦找到父节点，新节点就作为父节点的左子节点或右子节点被插入。 要找到要插入的新节点的父节点，你需要在树中执行搜索操作。
活动：实现一个二叉搜索树
问题描述： 编写程序来实现在含有字典中单词的二叉搜索树上的插入和遍历操作。 小结
在本章中，你已经学到： 一个树结构就是以非线型数据结构来表示不同数据元素之间的层级关系。 一个二叉树就是一个特定类型的树，其中的每个节点最多只能有2个子节点。 二叉树可以使用数组来实施，也可以使用链接列表，取决于需求。 树的遍历操作就是访问树中所有节点一遍。有三种类型的遍历，中序、前序和后序遍历。 二叉搜索树的特点就是树中节点的左子节点的值永远小于该节点的值，而节点的右子节点的值永远大于该节点。
向二叉搜索树插入节点需要首先找到节点中适于插入的位置。 需要在从二叉搜索树中删除节点前，检查下列三个条件： 要删除的节点是否为叶子节点 要删除的节点是否只有一个子节点（左或右子节点） 要删除的节点是否含有两个子节点
using System;
using System.Collections.Generic;
using System.Text;
namespace BinarySearchTree
{
// 二叉排序树节点类
public class Node
{
public string info;//存放节点的值
public Node lchild;//存放左子树的引用
public Node rchild;//存放右子树的引用
public Node(string info, Node lchild, Node rchild)
{
this.info = info;
this.lchild = lchild;
this.rchild = rchild;
}
}
// 二叉排序树类
public class BinaryTree
{
//存放二叉排序树的根节点
public Node root;
public BinaryTree()
{
root = null;//表示二叉排序树是一棵空树
}
//在查找某个元素或插入某个元素时使用
public void find(string element, ref Node parent, ref Node currentNode)
{
currentNode = root;
parent = null;
/*
在二叉排序树查找是否有节点的值等于element。
如果存在，当退出此循环时currentNode就指向这个要查找的节点，
parent指向此节点的父亲节点；
如果不存在，当退出此循环时currentNode就指null，
parent指向要插入节点的父亲节点；
*/
while (currentNode != null)
{
//让父亲指向当前节点
parent = currentNode;
//如果要查找元素的值小于当前节点的值
if (string.Compare(element , currentNode.info)<0)
{
//让当前节点指向当前节点左子树
currentNode = currentNode.lchild;
}
//如果要查找元素的值大于当前节点的值
else if (string.Compare(element, currentNode.info) > 0)
{
//让当前节点指向当前节点右子树
currentNode = currentNode.rchild;
}
else//如果要查找元素的值等于当前节点的值
{
//表明找到，退出循环
break;
}
}
}
//在二叉排序树中插入元素
public void insert(string element)
{
Node tmp;//存放要插入的节点
Node parent = null;//存放要插入节点的父亲节点
Node currentNode = null;//存放当前节点
//第一步，找到要插入元素的父亲节点
find(element, ref parent, ref currentNode);
//第二步，在二叉排序树中插入新节点
//如果要插入元素不在二叉排序树，就可以插入此元素，
//currentNode等于null，parent就指向要插入元素的父亲节点
if (currentNode == null)
{
//创建新节点对象
tmp = new Node(element, null, null);
//如果是空树
if (parent == null)
{
root = tmp;
}
else
{
//如果要插入元素的值小于父亲节点的值
if (string.Compare(element, parent.info) < 0)
{
//将新节点插入到父亲节点的左子树
parent.lchild = tmp;
}
else//如果要插入元素的值大于父亲节点的值
{
//将新节点插入到父亲节点的右子树
parent.rchild = tmp;
}
}
}
//如果要插入元素已经在二叉排序树，currentNode就不等于null
else
{
throw new Exception("二叉树中已经存在值为 " + element +" 的节点");
}
}
//将节点值等于element的节点从二叉排序树中删除
public void delete(string element)
{
Node parent = null, currentNode = null;
//第一步：找到要删除的节点
find(element, ref parent, ref currentNode);
//如果currentNode != null，表明找到要删除的节点
if (currentNode != null)
{
//如果要删除的节点为叶子节点
if ((currentNode.lchild == null) && (currentNode.rchild == null))
{
//如果要删除的节点为根节点
if (currentNode == root)
{
//删除后，就为空树
root = null;
}
//如果要删除的节点是父亲节点的左子树
else if (currentNode == parent.lchild)
{
//将父亲节点的左子树置null
parent.lchild = null;
}
//如果要删除的节点是父亲节点的右子树
else
{
//将父亲节点的右子树置null
parent.rchild = null;
}
}
else if ((currentNode.lchild != null) && (currentNode.rchild != null))//要删除的节点有两个子节点
{
//中序继任节点
Node inorder_suc;
//中序继任节点的父节点
Node inorder_suc_parent;
//让中序继任节点指向要删除节点的右子树
inorder_suc = currentNode.rchild;
//让中序继任节点的父节点指向要删除节点
inorder_suc_parent = currentNode;
//如果中序继任节点不是要删除节点的右儿子节点
if (inorder_suc.lchild != null)
{
//找到中序继任节点，
//说白了就是不断左移的过程，
//直到找到最左边的叶子节点或者只有右子树的节点
while (inorder_suc.lchild != null)
{
//让中序继任节点的父节点指向中序继任节点
inorder_suc_parent = inorder_suc;
//让中序继任节点指向中序继任节点的左子节点
inorder_suc = inorder_suc.lchild;
}
//用中序继任节点的值替换要删除节点的值
currentNode.info = inorder_suc.info;
//删除中序继任节点
inorder_suc_parent.lchild = inorder_suc.rchild;
}
//如果中序继任节点是要删除节点的右儿子节点
else
{
//用中序继任节点的值替换要删除节点的值
currentNode.info = inorder_suc.info;
//删除中序继任节点
inorder_suc_parent.rchild = inorder_suc.rchild;
}
}
else//要删除的节点只有一个子节点
{
Node child;//要删除节点的子节点
//如果要删除的节点只有左子树
if (currentNode.lchild != null)
{
//将要删除节点的左子树赋给child
child = currentNode.lchild;
}
//如果要删除的节点只有右子树
else
{
//将要删除节点的右子树赋给child
child = currentNode.rchild;
}
//如果要删除的节点为父节点的左子节点
if (currentNode == parent.lchild)
{
//让父节点左子节点引用指向child
parent.lchild = child;
}
//如果要删除的节点为父节点的右子节点
else
{
//让父节点右子节点引用指向child
parent.rchild = child;
}
}
}
//如果currentNode == null，表明没有找到要删除的节点
else
{
throw new Exception("没有找到要删除的节点");
}
}
//中序遍历，输入参数为要遍历树的根节点
public void inorder(Node ptr)
{
if (root == null)
{
Console.WriteLine("tree is empty");
}
if(ptr != null)
{
//中序遍历左子树
inorder(ptr.lchild);
//访问根节点的值
Console.Write(ptr.info + " ");
//中序遍历右子树
inorder(ptr.rchild);
}
}
//先序遍历，输入参数为要遍历树的根节点
public void preorder(Node ptr)
{
if (root == null)
{
Console.WriteLine("tree is empty");
}
if (ptr != null)
{
//访问根节点的值
Console.Write(ptr.info + " ");
//先序遍历左子树
preorder(ptr.lchild);
//先序遍历右子树
preorder(ptr.rchild);
}
}
//后序遍历，输入参数为要遍历树的根节点
public void postorder(Node ptr)
{
if (root == null)
{
Console.WriteLine("tree is empty");
}
if (ptr != null)
{
//后序遍历左子树
postorder(ptr.lchild);
//后序遍历右子树
postorder(ptr.rchild);
//访问根节点的值
Console.Write(ptr.info + " ");
}
}
}
}
using System;
using System.Text;
namespace BinarySearchTree
{
/* A Node class consists of three things, the information, reference to the
right child, and reference to the left child. */
class Node
{
public string info;
public Node lchild;
public Node rchild;
public Node(string i, Node l, Node r) /* Constructor for the Node class */
{
info = i;
lchild = l;
rchild = r;
}
}
class BinaryTree
{
public Node ROOT;
public BinaryTree()
{
ROOT = null; /* Initializing ROOT to null */
}
public void insert(string element) /* Inserts a Node in the Binary Search Tree */
{
Node tmp, parent = null, currentNode = null;
find(element, ref parent, ref currentNode);
if (currentNode != null) /* Checks if the node to be inserted is already present or not */
{
Console.WriteLine("Duplicates words not allowed");
return;
}
else /* If the specified Node is not present */
{
tmp = new Node(element, null, null); /* creates a Node */
if (parent == null) /* If the tree is empty */
ROOT = tmp;
else
if (String.Compare(element,parent.info) < 0)
parent.lchild = tmp;
else
parent.rchild = tmp;
}
}
public void find(string element, ref Node parent, ref Node currentNode)
{
/* This function finds the currentNode of the specified Node as well as the
currentNode of its parent. */
currentNode = ROOT;
parent = null;
while ((currentNode != null) && (currentNode.info != element))
{
parent = currentNode;
if (String.Compare(element,currentNode.info)<0)
currentNode = currentNode.lchild;
else
currentNode = currentNode.rchild;
}
}
public void inorder(Node ptr) /* Performs the inorder traversal of the tree */
{
if (ROOT == null)
{
Console.WriteLine("Tree is empty");
return;
}
if (ptr != null)
{
inorder(ptr.lchild);
Console.Write(ptr.info + " ");
inorder(ptr.rchild);
}
}
public void preorder(Node ptr) /* Performs the preorder traversal of the tree */
{
if (ROOT == null)
{
Console.WriteLine("Tree is empty");
return;
}
if (ptr != null)
{
Console.Write(ptr.info + " ");
preorder(ptr.lchild);
preorder(ptr.rchild);
}
}
public void postorder(Node ptr) /* Performs the postorder traversal of the tree */
{
if (ROOT == null)
{
Console.WriteLine("Tree is empty");
return;
}
if (ptr != null)
{
postorder(ptr.lchild);
postorder(ptr.rchild);
Console.Write(ptr.info + " ");
}
}
public void remove() /* Deletes the specified Node from the tree */
{
if (ROOT == null) /* Checks whether the tree is empty */
{
Console.WriteLine("Tree is empty");
return;
}
Node parent = null, currentNode = null;
string element;
Console.Write("Enter the word to be deleted: ");
element = Console.ReadLine();
find(element, ref parent, ref currentNode); /* Finds the currentNode of the Node and its parent */
if (currentNode == null)
{
Console.WriteLine("\nWord not found in the dictionary");
return;
}
/* Depending upon the status of the child nodes, the lines of code below
call the appropriate function for performing the deletion of the specified
node from the tree. */
if (currentNode.lchild == null && currentNode.rchild == null)
case_1(ref parent, ref currentNode);
else if (currentNode.lchild != null && currentNode.rchild == null)
case_2(ref parent, ref currentNode);
else if (currentNode.lchild == null && currentNode.rchild != null)
case_2(ref parent, ref currentNode);
else
case_3(ref parent, ref currentNode);
}
public void case_1(ref Node parent, ref Node currentNode) /* This function is invoked if the Node to be deleted is the leaf Node */
{
if (parent == null)
ROOT = null;
else
{
if (currentNode == parent.lchild)
parent.lchild = null;
else
parent.rchild = null;
}
}
public void case_2(ref Node parent, ref Node currentNode) /* This function is invoked if the node to be deleted has one child (left or right) */
{
Node child;
if (currentNode.lchild != null)
child = currentNode.lchild;
else
child = currentNode.rchild;
if (parent == null)
ROOT = child;
else
if (currentNode == parent.lchild)
parent.lchild = child;
else
parent.rchild = child;
}
public void case_3(ref Node parent, ref Node currentNode) /* This function is invoked when the Node to be deleted has two children */
{
Node inorder_suc, inorder_parent;
inorder_parent = currentNode;
inorder_suc = currentNode.rchild;
while (inorder_suc.lchild != null)
{
inorder_parent = inorder_suc;
inorder_suc = inorder_suc.lchild;
}
currentNode.info = inorder_suc.info;
if (inorder_suc.lchild == null && inorder_suc.rchild == null)
case_1(ref inorder_parent, ref inorder_suc);
else
case_2(ref inorder_parent, ref inorder_suc);
}
static void Main(string[] args)
{
BinaryTree b = new BinaryTree();
while (true)
{
Console.WriteLine("\nMenu");
Console.WriteLine("1. Implement insert operation");
Console.WriteLine("2. Perform inorder traversal");
Console.WriteLine("3. Perform preorder traversal");
Console.WriteLine("4. Perform postorder traversal");
Console.WriteLine("5. Implement delete operation");
Console.WriteLine("6. Exit");
Console.Write("\nEnter your choice (1-6): ");
char ch = Convert.ToChar(Console.ReadLine());
Console.WriteLine();
switch (ch)
{
case '1':
{
Console.Write("Enter a word: ");
string word = Console.ReadLine();
b.insert(word);
}
break;
case '2':
{
b.inorder(b.ROOT);
}
break;
case '3':
{
b.preorder(b.ROOT);
}
break;
case '4':
{
b.postorder(b.ROOT);
}
break;
case '5':
{
b.remove();
}
break;
case '6':
return;
default:
{
Console.WriteLine("Invalid option");
break;
}
}
}
}
}
}
- 顶
- 1
- 踩
- 0