數據結構與算法之十 提高二叉搜索樹的效率
      
    
      
        網友投稿
        724
        2025-03-31
		    
      
    
                    
      視頻課堂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小時內刪除侵權內容。

      
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

      
    
      
         
        

    
       
    
                    
      
        
      
                        上一篇:上海低代碼開發平臺（低代碼開發的平臺）
                    
      
        
      
                        下一篇:AI——自然語言預訓練模型(Bert模型)之Transformer詳解
                    
      
    
      

      

      
    
      
        相關文章
    
      
    

      
    
                            
      
          
      
               
      
      
    
      
  
      

  

      
       
  
      
    
  
      
  
      










亚洲国产综合91精品麻豆|
久久久久久亚洲av无码蜜芽|
亚洲日韩国产AV无码无码精品|
亚洲卡一卡2卡三卡4卡无卡三|
亚洲三区在线观看无套内射|
久久久久久久亚洲精品|
国产亚洲精品不卡在线|
中文字幕精品亚洲无线码二区|
亚洲中文字幕无码爆乳av中文|
亚洲日韩VA无码中文字幕
|
亚洲免费在线观看视频|
亚洲国产精品午夜电影
|
亚洲一区精品伊人久久伊人|
无码天堂亚洲国产AV|
国产亚洲精品国产福利在线观看|
久久精品国产亚洲av品善|
亚洲不卡AV影片在线播放|
亚洲人成网站在线观看青青|
区久久AAA片69亚洲|
国产亚洲精品精华液|
亚洲AV成人片色在线观看|
亚洲国产国产综合一区首页|
99亚洲精品高清一二区|
亚洲日本视频在线观看|
国产成人精品亚洲2020|
亚洲一区二区三区写真|
久久久久久亚洲精品无码|
亚洲精品456播放|
亚洲精品国精品久久99热一|
久久亚洲精品成人综合|
亚洲精品欧洲精品|
国产精品亚洲综合久久|
国产午夜亚洲精品不卡免下载
|
亚洲а∨天堂久久精品|
亚洲人成伊人成综合网久久久
|
色天使色婷婷在线影院亚洲|
亚洲国产一级在线观看|
国产亚洲精品va在线|
亚洲黄色在线电影|
亚洲久悠悠色悠在线播放|
噜噜综合亚洲AV中文无码|