淺談線索二叉樹

淺談線索二叉樹摘要：數(shù)據(jù)結(jié)構(gòu)中二叉樹有很多的遍歷算法，但本質(zhì)都是將屬性結(jié)構(gòu)轉(zhuǎn)換為線性序列，簡化問題。在遍歷序列中，每個節(jié)點都有自己的前驅(qū)和后去，但在二叉樹遍歷過程中尋求答案卻因為時間復(fù)雜度等因素使操作效率低下。線索二叉樹很好地解決了這一問題，本文是在二叉樹的基礎(chǔ)上加入線索二又樹實現(xiàn)數(shù)據(jù)的快速可操作性。關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；線索二叉樹；應(yīng)用前言為了實現(xiàn)在遍歷序列中快速查找節(jié)點的前驅(qū)、后繼，利用二叉鏈表中空的指針域，指向結(jié)點在遍歷序列中的前驅(qū)、后繼，這些指向前驅(qū)、后繼的指針就是線索。1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)起源于程序設(shè)計，主要是計算機中數(shù)據(jù)的組織方式、存儲結(jié)構(gòu)和處理方法。在程序的編程中，寫一個“好”的程序，就是要選擇一個合理的數(shù)據(jù)結(jié)構(gòu)和算法。數(shù)據(jù)的邏輯結(jié)構(gòu)常用結(jié)構(gòu)圖來描述，將每一個數(shù)據(jù)元素看做一個結(jié)點，在計算處理數(shù)據(jù)的時候，算法同樣很關(guān)鍵。一種算法的有窮性，必須對任何合法的輸入在執(zhí)行有窮之后結(jié)束，并且每1步都在有窮時間內(nèi)完成。樹形結(jié)構(gòu)就是用于有層次關(guān)系的數(shù)據(jù)表示，表達(dá)大多數(shù)問題求解的思路，而二叉樹的結(jié)點數(shù)和深度，為二叉樹存儲結(jié)構(gòu)的選擇提供了預(yù)備知識和思考線索。線索二又樹借助二又樹遍歷的程序框架建立，通過函數(shù)將整個二叉樹的線索化分解，求后繼、前驅(qū)結(jié)點的算法增加數(shù)據(jù)操作的效率，縮短時間，提高數(shù)據(jù)的操作性。2、樹的結(jié)構(gòu)定義樹形結(jié)構(gòu)是信息的重要組織形式之一，樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n(n>=1)個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做“樹”是因為它看起來像1棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：(1)每個結(jié)點有零個或多個子結(jié)點；(2)每一個子結(jié)點只有一個父結(jié)點；(3)沒有前驅(qū)的結(jié)點為根結(jié)點；(4)除了根結(jié)點外，每個子結(jié)點可以分為多個不相交的子樹。樹的應(yīng)用非常廣泛，在程序設(shè)計中實現(xiàn)通用樹的基本功能需要考慮很多功能，比如內(nèi)存分配，添加節(jié)點，修改節(jié)點，刪除節(jié)點，移動節(jié)點，遍歷，查詢，保存，讀取問題。STL提供了豐富容器，非常遺憾地是沒有提供樹。不過使用STL可以非常方便地實現(xiàn)1棵通用樹，完全可以避免直接使用內(nèi)存分配函數(shù)和遍歷釋放內(nèi)存。3、線索二又樹的實現(xiàn)和建立運用Vc++編寫一個程序?qū)崿F(xiàn)前序線索二叉樹、中序線索二叉樹和后序線索二叉樹，其中遍歷要求用先左后右的遞歸或非遞歸算法來實現(xiàn)，通過線索二叉樹提高數(shù)據(jù)操作效率。線索二叉樹建立與中序遍歷的c語言實現(xiàn)程序如下：#include<stdio.h>#include<malloc.h>Typedefenum{Link，Thread}PointerTag；//指針標(biāo)志typedefintDataType；typedefstructBiThreTreef//定義結(jié)點元素PointerTagLTag，RTag；DataTypedata；struetBiThreTree*lehild，*rchild；}BiThreTree；BiThreTree*pre；//全局變量，用于二叉樹的線索化BiThre-Tree*CreateTree()//按前序輸入建立二叉樹{BiThreTree*T：DataTypee：Scanf(“％d”，&e)；If(e==0)T=NULL；Else{T=(BiThreTree*)malloc(sizeof(BiThreTree))；T->data=e；T->LTag=Link；／／初始化時指針標(biāo)志均為LinkT->RTag=Link；T->lchild=CreateTree()；T->rchild=CreateTree()；}returnT：}voidInThread(BiThreTree*T){BiThreTree*p；p=T；if(p){InThread(p->lchild)；if(!p->lchild){p->LTag=Thread；p->lchild=pre；}if(!pre->rehild){pre->RTag=Thread；pre->rchild=p；}Pre=p；InThread(p->rehild)；}}BiThreTree*InOrderThrTree(BiThreTree*T)//中序線索化二叉樹{BiThreTree*Thre；//Thre為頭結(jié)點的指針Thre=(BiThreTree)malloc(sizeof(BiThreTree))；對與數(shù)據(jù)線索二叉樹的插征和性能進行了一個籠統(tǒng)的分析，線索二叉樹通過設(shè)置Ltag，Rtag標(biāo)志，并事先線索化來提高整個二叉樹的遍歷速度，是個典型的通過犧牲空間來提升速度例子。但是二叉樹到底在空間與速度的博弈中占著怎樣的地位，發(fā)生著怎樣的功能，在實際的應(yīng)用中空間值不值得需要深入地研究。以上如有不當(dāng)之處，還懇請大家指正。參考文獻(xiàn)：[1]吉根林林波數(shù)據(jù)結(jié)構(gòu)教程(c++版)[MJ．北京：電