数据结构与算法之十 提高二叉搜索树的效率
【摘要】
视频课堂https://edu.csdn.net/course/play/7621
目标
在本章中，您将学习：
应用树来解决编程问题
实现线索二叉树
索引
磁盘文件中的数据一般是按记录方式组织的。一条...
目标
在本章中，您将学习：
应用树来解决编程问题
实现线索二叉树
索引
磁盘文件中的数据一般是按记录方式组织的。一条记录由许多字段组成，其 中一个就是键字段。
这个键字段被用于唯一地标识文件中的每条记录。
索引是从磁盘文件中访问记录的数据访问方法之一。
索引通过称为索引的表来实现。
索引有以下两个条目：
所有记录的键字段
每条记录的位移位置（ Offset position ）
你可以实现一个二叉搜索树来存储这引起索引值。
此方法可以更快速地搜索一个键值。
在线索二叉树上常用的操作之一是遍历。
在链表表示的二叉搜索树中，通常通过递归完成遍历。
因此，栈在内存中被维护。
如果树非常大，实现递归遍历树需要许多内存空间。
如果内存不够，执行递归可能导致内存泄漏。
在这样的情况下， 你 有一些 能够遍历树而不需要实现递归 的机制是很好的。
你可以通过执行线索二叉树来解决此问题。
在二叉搜索树中，有许多节点具有空的左子节点或空的右子节点或两个都空。
在这种情况下，你可以利用这些域以便空的左子节点指向其中序前驱，空的 右子节点指向其中序后继。
在这样的情况下，为了其它一些有用目的利用这些 NULL 域将是很好的。
这种类型的二叉树被称为线索二叉树。
节点中保存中序前驱和中序后继地址的域被称为线索。
线索二叉树中节点的结构与标准二叉树的结构有所不同。
与标准二叉树不同的是线索二叉树的每个节点包含两个额外的信息，被称为 左线索和右线索。
节点的左和右线索域可以有两个值：
1 ：表示正常链接到子节点。
0 ：表示指向中序前驱和中序后继的线索。
线索二叉树中的各种操作以下：
遍历
搜索
插入
删除
运用算法以找到线索二叉树中节点的中序后继。
1. 识别节点，对于它你需要定位中序后继，并且标记它为 currentNode 。
2.
2. 如果 currentNode 的右子节点是线索：
a. 标记 currentNode 的右子节点为后继。
b. 退出。
c.
3. 使 currentNode 指向它的右子节点。
4.
4. 重复步骤 5 直到 currentNode 的左子节点变成线索。
5.
5. 将 currentNode 指向它的左子节点。
6.
6. 标记 currentNode 为后继。
小结
在本章中，你已经学到：
二叉搜索树可用于实现索引。
线索二叉树是这样一个二叉树，在其中有空左子节点的节点存储它的中序前驱 的地址，并且空右子节点存储它的中序后继的地址。
在线索二叉树中，节点的左和右子节点域，它保存它的中序前驱和中序后继的 地址，被称为线索。
你可以遍历线索二叉树而不实现递归。
线索二叉树被表示为头节点的左子树
与标准二叉树相比，在线索二叉树中每个节点由两个额外的域组成以保持节点 的左和右子节点域是线索或链接。
-
/*写一个程序以实现插入、删除且遍历线索二叉搜索树，这里树中的每个节点包含一个字典程序。*/
-
using System;
-
using System.Text;
-
-
namespace Threads
-
{
-
class Node
-
{
-
/*两个线索域；lthread,rthread;1:表示子节点；0：表示线索.*/
-
public int lthread; /*左线索标志*/
-
public Node lchild; /*左子节点/
-
public string info; /*数据域*/
-
public Node rchild; /*右子节点*/
-
public int rthread; /*右线索标志*/
-
-
public Node(int lt, Node lc, string i, Node rc, int rt)
-
{
-
lthread = lt;
-
lchild = lc;
-
info = i;
-
rchild = rc;
-
rthread = rt;
-
}
-
}
-
class Operations
-
{
-
Node head;
-
public Operations()
-
{
-
/*在一个线索二叉树种,我们增加一个节点,即头节点.线索树作为头节点的左子树,即头点指向树的根节点.当树为空的时候,头节点左子节点指向本身*/
-
-
head = new Node(0, head, "头节点", head, 0);
-
head.lchild = head;
-
head.rchild = head;
-
}//构造函数初始化的时候,头节点的左,右子节点指向本身.
-
-
public void find(string element, ref Node parent, ref Node currentNode)
-
{
-
/*搜索方法,查找你要找的节点位置与之父节点的位置.*/
-
if (head.lchild == head)
-
{
-
/*如果没有找到节点为null,且父节点为头节点*/
-
currentNode = null;
-
parent = head;
-
return;
-
}
-
currentNode = head.lchild;
-
parent = head;
-
-
while (currentNode.info != element)
-
{
-
parent = currentNode;
-
if (String.Compare(element,currentNode.info)<0) //如果元素小于当前节点
-
{
-
if (currentNode.lthread == 1) //判断当前节点的左线索标志,如果为1,则指向当前节点的左子节点.
-
currentNode = currentNode.lchild;
-
else //否则,如果左线索标志为0,则设置当前节点为空.
-
{
-
currentNode = null;
-
return;
-
}
-
}
-
else
-
{
-
if (currentNode.rthread == 1) //如果当前节点的右线索标志为1,则指向当前节点的右子节点.
-
currentNode = currentNode.rchild;
-
else //否则,右线索标志为0,则设置当前节点为空
-
{
-
currentNode = null;
-
return;
-
}
-
}
-
}
-
}
-
-
public void insert(string element) /*在二叉树中插入一个节点.*/
-
{
-
Node tmp, parent = null, currentNode = null; //
-
find(element, ref parent, ref currentNode); //调用查找当前元素节点,当前元素父节点.
-
if (currentNode != null)
-
{
-
/*在二叉搜索树中不允许,重复节点.*/
-
Console.WriteLine("\n不允许重复单词.");
-
return;
-
}
-
tmp = new Node(0, null, element, null, 0); //为tmp新节点分配内存.
-
if (parent == head) /*如果父节点为头节点,则插入节点为根节点.*/
-
{
-
head.lthread = 1; /*设置头节点的左线索标志为1*/
-
head.lchild = tmp; /*设置头节点的左子节点为要新节点.*/
-
tmp.lchild = head; /*新节点的左线索为头节点.*/
-
tmp.rchild = head; /*新节点的右线索为头节点.*/
-
}
-
else
-
{
-
if (String.Compare(element,parent.info)<0)
-
{
-
/*要插入的新节点比父节点小*/
-
-
tmp.lchild = parent.lchild;
-
tmp.rchild = parent;
-
parent.lthread = 1;
-
parent.lchild = tmp;
-
}
-
else
-
{
-
/*要插入的新节点比父节点要大!*/
-
-
tmp.rchild = parent.rchild;
-
tmp.lchild = parent;
-
parent.rthread = 1;
-
parent.rchild = tmp;
-
}
-
}
-
}
-
-
public Node Inorder_successor(Node currentNode) //中序编历查找后继节点
-
{
-
/*中序:左子树< 根<右子树 */
-
Node successor;
-
if (currentNode.rthread == 0)
-
successor = currentNode.rchild;
-
else
-
{
-
currentNode = currentNode.rchild;
-
while (currentNode.lthread == 1)
-
{
-
currentNode = currentNode.lchild;
-
}
-
successor = currentNode;
-
}
-
return successor;
-
}
-
-
public Node Inorder_predecessor(Node currentNode) /*利用中序编历查找前驱节点.*/
-
{
-
Node predecessor;
-
if (currentNode.lthread == 0)
-
predecessor = currentNode.lchild;
-
else
-
{
-
currentNode = currentNode.lchild;
-
while (currentNode.rthread == 1)
-
{
-
currentNode = currentNode.rchild;
-
}
-
predecessor = currentNode;
-
}
-
return predecessor;
-
}
-
-
public void Inorder_traversal() /*执行树的中序编历*/
-
{
-
Node currentNode = null;
-
if (head.lchild == head)
-
{
-
Console.WriteLine("树空!");
-
return;
-
}
-
currentNode = head.lchild;
-
while (currentNode.lthread == 1)
-
{
-
currentNode = currentNode.lchild;
-
}
-
Console.Write(currentNode.info + " ");
-
while (true)
-
{
-
currentNode = Inorder_successor(currentNode);
-
if (currentNode == head)
-
break;
-
Console.Write(currentNode.info + " ");
-
}
-
Console.WriteLine();
-
}
-
-
public void remove() /*从树种移除节点*/
-
{
-
if (head.lchild == head)
-
{
-
Console.WriteLine("树空");
-
return;
-
}
-
Node parent = null, currentNode = null;
-
string element;
-
Console.Write("请键入要删除单词:");
-
element = Console.ReadLine();
-
find(element, ref parent, ref currentNode);
-
if (currentNode == null)
-
{
-
Console.WriteLine("\n在字典中没有发现该单词");
-
return;
-
}
-
/*依据不同的状态,来删除不同的子节点.*/
-
if (currentNode.lthread == 0 && currentNode.rthread == 0)
-
case_1(ref parent, ref currentNode);
-
if (currentNode.lthread == 1 && currentNode.rthread == 0)
-
case_2(ref parent, ref currentNode);
-
if (currentNode.lthread == 0 && currentNode.rthread == 1)
-
case_2(ref parent, ref currentNode);
-
if (currentNode.lthread == 1 && currentNode.rthread == 1)
-
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 removed is the leaf node */
-
if (parent == head)
-
{
-
head.lthread = 0;
-
head.lchild = head;
-
}
-
else
-
if (currentNode == parent.lchild)
-
{
-
parent.lthread = 0;
-
parent.lchild = currentNode.lchild;
-
}
-
else
-
{
-
parent.rthread = 0;
-
parent.rchild = currentNode.rchild;
-
}
-
}
-
-
public void case_2(ref Node parent, ref Node currentNode)
-
{
-
/* This function is invoked if the node to be removed has only one child (left or right) */
-
Node child, successor, predecessor;
-
if (currentNode.lthread == 1)
-
child = currentNode.lchild;
-
else
-
child = currentNode.rchild;
-
if (parent == head)
-
head.lchild = child;
-
else
-
if (currentNode == parent.lchild)
-
parent.lchild = child;
-
else
-
parent.rchild = child;
-
successor = Inorder_successor(currentNode);
-
predecessor = Inorder_predecessor(currentNode);
-
-
if (currentNode.rthread == 1)
-
successor.lchild = predecessor;
-
else
-
{
-
if (currentNode.lthread == 1)
-
predecessor.rchild = successor;
-
}
-
}
-
public void case_3(ref Node parent, ref Node currentNode)
-
{
-
/* This function is invoked if the node to be removed has two children */
-
Node inorder_suc, inorder_parent;
-
inorder_parent = currentNode;
-
inorder_suc = currentNode.rchild;
-
while (inorder_suc.lthread == 1)
-
{
-
inorder_parent = inorder_suc;
-
inorder_suc = inorder_suc.lchild;
-
}
-
-
currentNode.info = inorder_suc.info;
-
if (inorder_suc.lthread == 0 && inorder_suc.rthread == 0)
-
case_1(ref inorder_parent, ref inorder_suc);
-
else
-
case_2(ref inorder_parent, ref inorder_suc);
-
}
-
-
-
static void Main(string[] args)
-
{
-
Operations t = new Operations();
-
while (true)
-
{
-
try
-
{
-
Console.WriteLine("\n菜单");
-
Console.WriteLine("1. 插入操作");
-
Console.WriteLine("2.删除操作");
-
Console.WriteLine("3.中序编历操作");
-
Console.WriteLine("4. 退出");
-
Console.Write("\n请输入您的选择(1-4): ");
-
char ch = Convert.ToChar(Console.ReadLine());
-
Console.WriteLine();
-
switch (ch)
-
{
-
case '1':
-
{
-
Console.Write("请输入单词: ");
-
string word = Console.ReadLine();
-
t.insert(word);
-
}
-
break;
-
case '2':
-
{
-
t.remove();
-
}
-
break;
-
case '3':
-
{
-
t.Inorder_traversal();
-
}
-
break;
-
case '4':
-
return;
-
default:
-
{
-
Console.WriteLine("无效选择");
-
}
-
break;
-
}
-
}
-
catch (Exception e)
-
{
-
Console.WriteLine("请检查您的值.");
-
}
-
}
-
}
-
}
-
}
-
/*写一个程序以创建和维护文件中的索引，它包含顾客的纪录。文件中每个纪录包含下面的信息。
-
顾客ID(整型）
-
顾客的姓名（字符串)
-
顾客的电话号码(字符串)
-
*/
-
using System;
-
using System.Collections.Generic;
-
using System.Text;
-
using System.IO;
-
-
namespace Indexing
-
{
-
class Node
-
{
-
-
public int key; //键
-
public int offset; //偏移量
-
public Node lchild; //左子节点
-
public Node rchild; //右子节点.
-
};
-
-
class Customer
-
{
-
public int key;
-
public string name;
-
public string phone;
-
-
public void accept()
-
{
-
Console.Write("\nEnter customer ID: ");
-
key = Int32.Parse(Console.ReadLine());
-
Console.Write("\nEnter name: ");
-
name = Console.ReadLine();
-
Console.Write("\nEnter phone: ");
-
phone = Console.ReadLine();
-
}
-
-
public void read_record(int offset)
-
{
-
FileStream fs = new FileStream("E:/Customer.txt", FileMode.Open, FileAccess.Read);
-
StreamReader r = new StreamReader(fs);
-
fs.Position = offset;
-
string k = r.ReadLine();
-
string nm = r.ReadLine();
-
string ph = r.ReadLine();
-
Console.WriteLine("Customer ID: " + k);
-
Console.WriteLine("\nCustomer name: " + nm);
-
Console.WriteLine("\nPhone number: " + ph);
-
Console.WriteLine("\n");
-
r.Close();
-
fs.Close();
-
}
-
}
-
-
class Tree_Index
-
{
-
Node ROOT;
-
public Tree_Index()
-
{
-
ROOT = null;
-
load_Index();
-
}
-
-
public void find(int key, ref Node parent, ref Node currentNode)
-
{
-
currentNode = ROOT;
-
parent = null;
-
while ((currentNode != null) && (currentNode.key != key))
-
{
-
parent = currentNode;
-
if (key < currentNode.key)
-
currentNode = currentNode.lchild;
-
else
-
currentNode = currentNode.rchild;
-
}
-
}
-
-
void insert(int key, int offset)
-
{
-
Node newnode = new Node();
-
newnode.key = key;
-
newnode.offset = offset;
-
newnode.lchild = null;
-
newnode.rchild = null;
-
Node parent = null, currentNode = null;
-
find(key, ref parent, ref currentNode);
-
{
-
if (parent == null)
-
ROOT = newnode;
-
else
-
if (key < parent.key)
-
parent.lchild = newnode;
-
else
-
parent.rchild = newnode;
-
}
-
}
-
-
int search_key(int key)
-
{
-
Node parent=null, currentNode=null;
-
if(ROOT==null)
-
{
-
Console.WriteLine("Tree is empty\n");
-
}
-
else
-
find(key, ref parent,ref currentNode);
-
if(currentNode==null)
-
{
-
Console.WriteLine("This item is not in the tree\n");
-
return -1;
-
}
-
else
-
{
-
Console.WriteLine("Customer ID found........offset is " + currentNode.offset +"\n");
-
return currentNode.offset;
-
}
-
}
-
-
void load_Index()
-
{
-
FileStream fs = new FileStream("E:/Index.txt", FileMode.OpenOrCreate, FileAccess.Read);
-
StreamReader r = new StreamReader(fs);
-
r.BaseStream.Seek(0, SeekOrigin.Begin);
-
-
while (!r.EndOfStream)
-
{
-
string k = r.ReadLine();
-
string o = r.ReadLine();
-
insert(Convert.ToInt32(k), Convert.ToInt32(o));
-
}
-
r.Close();
-
}
-
-
void inorder(Node ptr)
-
{
-
if (ROOT == null)
-
{
-
Console.WriteLine("Tree is empty\n");
-
return;
-
}
-
if (ptr != null)
-
{
-
-
inorder(ptr.lchild);
-
Console.WriteLine(ptr.key + " " + ptr.offset + "\n");
-
inorder(ptr.rchild);
-
}
-
}
-
void traverse()
-
{
-
Console.WriteLine("........Inorder traversal sequence.........\n");
-
inorder(ROOT);
-
}
-
-
static void Main(string[] args)
-
{
-
Tree_Index tobj=new Tree_Index();
-
Node curr, par;
-
Customer cobj = new Customer();
-
int key, offset;
-
char ch;
-
do
-
{
-
Console.WriteLine("Menu\n");
-
Console.WriteLine("1. Insert a record");
-
Console.WriteLine("2. Read a record");
-
Console.WriteLine("3. View index");
-
Console.WriteLine("4. Exit");
-
Console.Write("\nEnter your choice (1-3): ");
-
ch = Char.Parse(Console.ReadLine());
-
switch (ch)
-
{
-
case '1':
-
{
-
cobj.accept();
-
FileStream fs = new FileStream("E:/Customer.txt", FileMode.Append, FileAccess.Write);
-
StreamWriter w = new StreamWriter(fs);
-
offset = Convert.ToInt32(fs.Position);
-
key = cobj.key;
-
curr = null;
-
par = null;
-
tobj.find(key, ref par, ref curr);
-
if (curr != null)
-
{
-
Console.WriteLine("\nDuplicate Customer IDs not allowed\n");
-
w.Close();
-
fs.Close();
-
break;
-
}
-
Console.WriteLine("offset= " + fs.Position);
-
w.WriteLine(Convert.ToInt32(cobj.key));
-
w.Flush();
-
w.WriteLine(cobj.name);
-
w.Flush();
-
w.WriteLine(cobj.phone);
-
w.Flush();
-
w.Close();
-
fs.Close();
-
FileStream fs1 = new FileStream("E:/Index.txt", FileMode.Append, FileAccess.Write);
-
StreamWriter w1 = new StreamWriter(fs1);
-
w1.WriteLine(Convert.ToInt32(key));
-
w1.Flush();
-
w1.WriteLine(Convert.ToInt32(offset));
-
w1.Flush();
-
w1.Close();
-
fs1.Close();
-
tobj.insert(key, offset);
-
tobj.traverse();
-
}
-
break;
-
case '2':
-
{
-
Console.Write("\nEnter the customer ID of the record to be searched: ");
-
key = Convert.ToInt32(Console.ReadLine());
-
Console.WriteLine("\n");
-
offset = tobj.search_key(key);
-
if (offset != -1)
-
cobj.read_record(offset);
-
}
-
break;
-
case '3':
-
{
-
tobj.traverse();
-
}
-
break;
-
case '4': break;
-
default: Console.WriteLine("Invalid choice.");
-
break;
-
}
-
} while (ch != '4');
-
}
-
}
-
}
文章来源: aaaedu.blog.csdn.net，作者：tea_year，版权归原作者所有，如需转载，请联系作者。
原文链接：aaaedu.blog.csdn.net/article/details/51675081
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）