線索二叉樹及若幹操作

来源:http://www.cnblogs.com/robin-xu/archive/2016/03/06/5248681.html
-Advertisement-
Play Games

1 /* 遍歷二叉樹就是以一定的規則將二叉樹中的節點排列成一個線性 2 * 序列，從而得到二叉樹節點的各種遍歷序列，其實質是：對一個 3 * 非線性的結構進行線性化。使得在這個訪問序列中每一個節點都 4 * 有一個直接前驅和直接後繼。 5 * 傳統的鏈式結構只能體現一種父子關係，￥不能直接得到節點在


  1 /* 遍歷二叉樹就是以一定的規則將二叉樹中的節點排列成一個線性
  2  * 序列，從而得到二叉樹節點的各種遍歷序列，其實質是：對一個
  3  * 非線性的結構進行線性化。使得在這個訪問序列中每一個節點都
  4  * 有一個直接前驅和直接後繼。
  5  * 傳統的鏈式結構只能體現一種父子關係，￥不能直接得到節點在
  6  * 遍歷中的前驅和後繼￥，而我們知道二叉鏈表表示的二叉樹中有
  7  * 大量的空指針，當使用這些空的指針存放指向節點的前驅和後繼
  8  * 的指針時，則可以更加方便的運用二叉樹的某些操作。
  9  * 引入線索二叉樹的目的是： 為了加快查找節點的前驅和後繼。
 10  *
 11  * 對二叉樹的線索化就是對二叉樹進行一次遍歷，在遍歷的過程中
 12  * 檢測節點的左右指針是否為空，如果是空，則將他們改為指向前
 13  * 驅和後繼節點的線索。
 14  * */
 15 #include<stdio.h>
 16 #include<stdlib.h>
 17 
 18 #define OK 1
 19 #define ERROR 0
 20 
 21 typedef char ElemType;
 22 typedef int Status;
 23 
 24 /* 定義枚舉類型，其值只能是Link和Thread
 25  * Link表示的該指針指示的是孩子
 26  * Thread表示的是還指針指示的是前驅或者是尾碼
 27  * */
 28 typedef enum {
 29     Link,Thread
 30 }PointerTag;
 31 
 32 typedef struct ThrBiTrNode{
 33     ElemType data;
 34     struct ThrBiTrNode *lchild, *rchild;
 35     PointerTag rTag, lTag;
 36 }ThrBiTrNode, *ThrBiTree;
 37 
 38 ThrBiTree Pre;
 39 
 40 Status InitThreadBinaryTree(ThrBiTree* T){
 41     *T = NULL;
 42     return OK;
 43 }
 44 //先序建立二叉樹,lchild和rchild都是指示做孩子和右孩子，所以lTag和rTag為Link
 45 Status ThreadBinaryTree_PreOrderInput(ThrBiTree* T){
 46     ElemType c;
 47     scanf("%c", &c);
 48     if( ' ' == c ){
 49         *T = NULL;
 50     }
 51     else{
 52         *T = (ThrBiTrNode*)malloc(sizeof(ThrBiTrNode));
 53         if( !*T ){
 54             return ERROR;
 55         }
 56         (*T)->data = c;
 57         (*T)->lTag = Link;
 58         (*T)->rTag = Link;
 59         ThreadBinaryTree_PreOrderInput(&(*T)->lchild);
 60         ThreadBinaryTree_PreOrderInput(&(*T)->rchild);
 61     }
 62     return OK;
 63 }
 64 //<<中序遍歷>>對二叉樹進行<<線索化>>，但是沒有提供Pre的初始值，只是給出了
 65 //中間的過程，遞歸的思想和思考方式。
 66 //1  線索化左子樹
 67 //2  對雙親節點處理//遞歸中的base
 68 //3  線索化右子樹
 69 Status InOrderThread(ThrBiTree T){
 70     if( T != NULL ){
 71         InOrderThread(T->lchild);        //線索化左子樹
 72         
 73         //對雙親節點進行線索化處理
 74         if( T->lchild == NULL ){    //如果左孩子為空，則將lchild作為索引
 75                         //Pre指向剛剛訪問的節點
 76             T->lTag = Thread;
 77             T->lchild = Pre;
 78         }
 79         if( Pre->rchild == NULL ){    //直到現在才知道Pre的尾碼是T，所以
 80                         //要對Pre進行設置,如果Pre的rchild為空
 81                         //則將Pre的rchild設置為尾碼，指向T
 82             Pre->rTag = Thread;
 83             Pre->rchild = T;
 84         }
 85 
 86         Pre = T;            //標記當前的節點稱為剛剛訪問過的節點
 87                         //Pre最後會指向樹的中序遍歷的最後的
 88                         //一個節點
 89 
 90         InOrderThread(T->rchild);    //線索化右子樹
 91     }
 92     return OK;
 93 }
 94 //創建中序線索二叉樹,為上個函數提供Pre
 95 Status CreateInOrderThreadBinaryTree(ThrBiTree T, ThrBiTree* headOfTree){
 96     *headOfTree = (ThrBiTrNode*)malloc(sizeof(struct ThrBiTrNode));
 97     if( !headOfTree )
 98         return ERROR;
 99     (*headOfTree)->lTag = Link;        //將要指向T
100     (*headOfTree)->rTag = Thread;        //將頭節點的rchild用於索引
101     (*headOfTree)->rchild = *headOfTree;       //指向自身
102     if( T == NULL ){
103         (*headOfTree)->lchild = *headOfTree;    //若T為空樹，則頭節點的lchild
104                             //指向自身
105     }
106     else{
107         (*headOfTree)->lchild = T;
108         Pre = *headOfTree;            //賦值了全局變數Pre
109         InOrderThread(T);                //中序線索化
110         //printf("\n%c\n",Pre->data);
111                         //執行完InOrderThread之後Pre指向最後
112                         //一個節點
113         Pre->rTag = Thread;        
114         Pre->rchild = *headOfTree;
115         //(*headOfTree)->rchild = Pre;
116     }
117     return OK;
118 }
119 //對中序線索化後的線索二叉樹使用<<非遞歸>>的代碼進行中序遍歷
120 //並且原來的遞歸形式的代碼在這裡是不再可以進行遍歷。
121 //    如果二叉樹沒有被線索化，也是使用<<非遞歸>>的代碼進行遍
122 //    歷的，但是那就需要藉助於<<棧>>,但是線上索化之後，對線索
123 //    化的二叉樹進行<<非遞歸>>的遍歷就不再需要棧的輔助。
124 Status visit(ElemType c){
125     printf("%c ", c);
126     return OK;
127 }
128 Status InOrderTeaverse_NoRecursion(ThrBiTree T, ThrBiTree headOfTree){
129 //headOfTree是T的頭節點的指針，headOfTree->lchild = T;
130     while( T != headOfTree ){
131         while( T->lTag == Link ){    //找到樹(子樹)的最左節點
132                         //用while接替if//
133                         //用if理解while//
134             T = T->lchild;
135         }                
136         visit(T->data);
137 
138         while( T->rTag == Thread && T->rchild != headOfTree){
139                         //這個while和下麵的T=T->rchild
140                         //可用ifelse語句理解。
141                         //if(rchild是線索 && 不是最後一個節點) 
142                         //else(rchild不是線索)-->走到右孩子
143                         //也就是代碼T=T->rchild
144             T = T->rchild;
145             visit(T->data);
146         }
147         T = T->rchild;
148     }
149     return OK;
150 }
151 //求中序線索二叉樹中中序序列下的第一個節點
152 ThrBiTrNode* SeekFirstNode_InOrderThrBiTree(ThrBiTree T){
153     if( T != NULL ){
154         while( T->lTag == Link ){
155             T = T->lchild;
156         }
157         return T;
158     }
159     return ERROR;
160 }
161 //求中序線索二叉樹中節點P在中序序列下的下一個節點
162 ThrBiTrNode* GetNextNode(ThrBiTrNode* CurrentP){
163     if( CurrentP->rTag == Link ){    //有右孩子的時候，那麼下一個就是以
164                     //右孩子為root的樹的最左下角元素。
165                     //即seekFirstNode的返回值。
166         return SeekFirstNode_InOrderThrBiTree(CurrentP->rchild);
167     }
168     else{                //沒有右孩子，則rchild指向尾碼
169         return CurrentP->rchild;
170     }
171 }
172 //使用上面兩個函數，SeekFirstNode_InOrderThrBiTree和GetNextNode來實現對
173 //中序先做二叉樹的遍歷
174 Status InOrderTraverse_NoRecursion_Method(ThrBiTree T, ThrBiTree head){
175     for( T = SeekFirstNode_InOrderThrBiTree(T) ; T != head ; T = GetNextNode(T) )
176         visit(T->data);
177     return OK;
178 }
179 
180 //test
181 /* ShowThread函數的目的是想在將T中序線索化之後，使用函數InOrderTraverse
182  * 函數中序遍歷，輸出一下節點中的信息以檢驗線索化，但是失敗。原因是：在
183  * 線索化之後，空指針域都被應用，所有InOrderTraverse函數中的if( T )是滿
184  * 足不了的，故失敗。
185 Status ShowThread(ThrBiTree C){
186     printf("%d %d %d %d\n",(C->lchild)->data,(C->rchild)->data,C->lTag,C->rTag);
187     printf("%d %d\n",C->lTag,C->rTag);
188     return OK;
189  * */
190 
191 //中序遍歷二叉樹
192 Status InOrderTraverse(ThrBiTree T){
193     if( T ){
194         InOrderTraverse(T->lchild);
195         visit(T->data);
196         InOrderTraverse(T->rchild);
197     }
198     return OK;
199 }
200 int main(){
201     ThrBiTree T,R,Head = NULL;
202     InitThreadBinaryTree(&T);
203 
204     printf("Please Input Binary Tree By PreOrder\n    ");
205     ThreadBinaryTree_PreOrderInput(&T);
206 
207     printf("    InOrder Traverse before Thread with Recursion\n");
208     InOrderTraverse(T);
209     printf("\n");
210 
211     CreateInOrderThreadBinaryTree(T,&Head);
212     printf("    InOrder Traverse after Thread with no-Recursion\n");
213     InOrderTeaverse_NoRecursion(T,Head);
214     printf("\n");
215 
216     printf("The root is %c \n", T->data);    //不能夠通過指針形參的值改變指針實參的值
217                         //或者說，對指針形參的改變不會作用到指針
218                         //實參上。
219 
220     ThrBiTrNode *firstOfInOrder = NULL,*secondOfInOrder = NULL;
221     if( SeekFirstNode_InOrderThrBiTree(T) != ERROR ){
222         firstOfInOrder = SeekFirstNode_InOrderThrBiTree(T);
223         printf("the value of First Node of InOrderThreadBinaryTree is %c\n", firstOfInOrder->data);
224     }
225     secondOfInOrder = GetNextNode(firstOfInOrder);
226     printf("the value of Node after D is: %c \n", secondOfInOrder->data);
227     secondOfInOrder = GetNextNode(secondOfInOrder);
228     printf("the value of Node after B is: %c \n", secondOfInOrder->data);
229     secondOfInOrder = GetNextNode(secondOfInOrder);
230     printf("the value of Node after E is: %c \n", secondOfInOrder->data);
231     secondOfInOrder = GetNextNode(secondOfInOrder);
232     printf("the value of Node after A is: %c \n", secondOfInOrder->data);
233     secondOfInOrder = GetNextNode(secondOfInOrder);
234     printf("the value of Node after C is: %c \n", secondOfInOrder->data);
235     secondOfInOrder = GetNextNode(secondOfInOrder);
236     printf("the value of Node after G is: %c \n", secondOfInOrder->data);
237     secondOfInOrder = GetNextNode(secondOfInOrder);
238     printf("the value of Node after root is: %c \n", secondOfInOrder->data);
239 
240     printf("    InOrder Traverse after Thread with no-Recursion Method_2\n");
241     InOrderTraverse_NoRecursion_Method(T,Head);
242 
243     return 0;
244 }

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Verilog(三) multiplexer
    mutiplexer 數據選擇器 1 one-bit wide 2-1 mux wire dout = sel? din1 : din0; // conditional continuous and wire assignment 2 4-1 mux module mux4_1(sel, din0,
  • Verilog(二) register and net
    1 register = storage keyword reg; default x; variable that can hold value 2 net = connection keyword wire; default z; be driven continuously 例 1) D fl
  • Win32的繪圖消息大集合
    AbortPath 拋棄選入指定設備場景中的所有路徑。也取消目前正在進行的任何路徑的創建工作AngleArc 用一個連接弧畫一條線Arc 畫一個圓弧BeginPath 啟動一個路徑分支CancelDC 取消另一個線程里的長時間繪圖操作Chord 畫一個弦CloseEnhMetaFile 關閉指定的增
  • python之信用卡ATM（第五天）
    本節作業 作業需求： 模擬實現一個ATM + 購物商城程式 額度 15000或自定義 實現購物商城，買東西加入 購物車，調用信用卡介面結賬 可以提現，手續費5% 每月22號出賬單，每月10號為還款日，過期未還，按欠款總額 萬分之5 每日計息 支持多賬戶登錄 支持賬戶間轉賬 記錄每月日常消費流水 提供
  • wdcp環境下更新PHP到5.3教程
    在lanmp/wdcp/wdOS的當前版本中,預設的php都是用到5.2.17的版本如需要升級到php5.3的,可使用如下腳本升級(註:此升級無安全漏洞等原因,只為某些追求高版本或應用需求需要高版本,對於無這個必要的同學,可不用升級)wget http://down.wdlinux.cn/in/ph
  • Delphi 信息化管理系統開源框架 @ 介紹
    信息化管理軟體基本上就是基於資料庫的開發，而Delphi在資料庫開發有著顯著優勢， 而正因為Delphi的便捷，很多程式員喜歡信手拈來，擺擺控制項，寫寫代碼， 而隨著開發的需求的多樣化，程式變得越來越臃腫，越來越難以維護，幾乎沒有擴展空間。 我改過一段時間的爛代碼，深受刺激，突然發現有些程式員的思維方
  • 快速排序
    //============================================================================ // Name : QuickSort.cpp // Author : Cheng Song // Version : // Copyrigh
  • 冒泡排序
    //============================================================================ // Name : BubbleSort.cpp // Author : fffff // Version : // Copyright :
一周排行
    -Advertisement-
    Play Games
  • WPF 已知問題 監聽 WMI 事件導致觸摸失效
    示例項目結構 在 Visual Studio 中創建一個 WinForms 應用程式後，項目結構如下所示： MyWinFormsApp/ │ ├───Properties/ │ └───Settings.settings │ ├───bin/ │ ├───Debug/ │ └───Release/ ...
  • [STAThread]特性
    [STAThread] 特性用於需要與 COM 組件交互的應用程式，尤其是依賴單線程模型（如 Windows Forms 應用程式）的組件。在 STA 模式下，線程擁有自己的消息迴圈，這對於處理用戶界面和某些 COM 組件是必要的。 [STAThread] static void Main(stri ...
  • UWP WinUI3 傳入 AddHandler 的 RoutedEventHandler 類型與事件所需不匹配將拋出參數異常
    在WinForm中使用全局異常捕獲處理 在WinForm應用程式中，全局異常捕獲是確保程式穩定性的關鍵。通過在Program類的Main方法中設置全局異常處理，可以有效地捕獲並處理未預見的異常，從而避免程式崩潰。 註冊全局異常事件 [STAThread] static void Main() { / ...
  • .NET 多版本 WinForm 開源控制項庫 SunnyUI
    前言 給大家推薦一款開源的 Winform 控制項庫，可以幫助我們開發更加美觀、漂亮的 WinForm 界面。 項目介紹 SunnyUI.NET 是一個基於 .NET Framework 4.0+、.NET 6、.NET 7 和 .NET 8 的 WinForm 開源控制項庫，同時也提供了工具類庫、擴展 ...
  • .net core8 使用Swagger（附當前源碼）
    說明 該文章是屬於OverallAuth2.0系列文章，每周更新一篇該系列文章（從0到1完成系統開發）。 該系統文章，我會儘量說的非常詳細，做到不管新手、老手都能看懂。 說明：OverallAuth2.0 是一個簡單、易懂、功能強大的許可權+可視化流程管理系統。 有興趣的朋友，請關註我吧(*^▽^*) ...
  • WPF 什麼時候 VisualTreeHelper.GetDescendantBounds 將返回無窮大
    一、下載安裝 1.下載git 必須先下載並安裝git，再TortoiseGit下載安裝 git安裝參考教程：https://blog.csdn.net/mukes/article/details/115693833 2.TortoiseGit下載與安裝 TortoiseGit，Git客戶端，32/6 ...
  • C# 開源教程帶你輕鬆掌握數據結構與演算法
    前言 在項目開發過程中，理解數據結構和演算法如同掌握蓋房子的秘訣。演算法不僅能幫助我們編寫高效、優質的代碼，還能解決項目中遇到的各種難題。 給大家推薦一個支持C#的開源免費、新手友好的數據結構與演算法入門教程：Hello演算法。 項目介紹 《Hello Algo》是一本開源免費、新手友好的數據結構與演算法入門 ...
  • 第22篇 生成proto文件bat腳本
    1.生成單個Proto.bat內容 @rem Copyright 2016, Google Inc. @rem All rights reserved. @rem @rem Redistribution and use in source and binary forms, with or with ...
  • 記一次 .NET某上位機視覺程式 卡死分析
    一：背景 1. 講故事 前段時間有位朋友找到我，說他的窗體程式在客戶這邊出現了卡死，讓我幫忙看下怎麼回事？dump也生成了，既然有dump了那就上 windbg 分析吧。 二：WinDbg 分析 1. 為什麼會卡死 窗體程式的卡死，入口門檻很低，後續往下分析就不一定了，不管怎麼說先用 !clrsta ...
  • 醫學DICOM文件與PACS系統進行數據傳輸
    前言 人工智慧時代，人臉識別技術已成為安全驗證、身份識別和用戶交互的關鍵工具。 給大家推薦一款.NET 開源提供了強大的人臉識別 API，工具不僅易於集成，還具備高效處理能力。 本文將介紹一款如何利用這些API，為我們的項目添加智能識別的亮點。 項目介紹 GitHub 上擁有 1.2k 星標的 C# ...
所有分類