数据结构与算法之十 提高二叉搜索树的效率

网友投稿 603 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小时内删除侵权内容。

上一篇:MySQL逻辑架构
下一篇:xml系列之数据库中数据的导入导出
相关文章