excel表格里面画斜线方法
629
2022-05-29
数据结构与算法之十 提高二叉搜索树的效率
视频课堂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');
}
}
}
二叉树 数据结构
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
相关文章
推荐文章
最近发表
