Jquery中文網 www.uhadif.co
Jquery中文網 >  腳本編程  >  C語言  >  正文 二叉鏈表表示的二叉樹及基本操作

二叉鏈表表示的二叉樹及基本操作

發布時間:2017-12-13   編輯:www.uhadif.co
jquery中文網為您提供二叉鏈表表示的二叉樹及基本操作等資源,歡迎您收藏本站,我們將為您提供最新的二叉鏈表表示的二叉樹及基本操作資源
二叉樹是一個連通的無環圖,并且每一個頂點的度不大于3。有根二叉樹還要滿足根結點的度不大于2。

設計不同的結點結構可構成不同形式的鏈式儲存結構。由二叉樹的結點由一個數據元素和分別指向其左、右子樹的兩個分支構成,則表示二叉樹的鏈表中的結點至少包含三個域:數據域和左、右指針域

一下是二叉鏈表的定義和部分基本操作的函數原型說明:


<pre class="brush:cpp;toolbar:false">#ifndef BINARY_LINKED_LIST_TREE_H #define BINARY_LINKED_LIST_TREE_H //---------二叉樹的二叉鏈表儲存表示----------- #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define MYOVERFLOW -2 typedef int Status; typedef char TElemType; typedef struct BiTNode {     TElemType data;     BiTNode *lchild, *rchild; }*BiTree;  //------------基本操作的函數原型說明(部分)------------ Status CreateBiTree(BiTree &T); //T表示這個樹的根節點的指針 //按先序次序輸入二叉樹中結點的值(一個字符),空格字符表示空樹, //構造二叉鏈表表示的二叉樹T Status VisitBiTree(BiTree); //輸出結點的數據域 Status PreOrderTraverse(BiTree T, Status(*Visit)(BiTree)); //T表示這個樹的根節點的指針 //采用二叉鏈表儲存結構,Visit是對結點操作的對應函數 //先序遍歷二叉樹T,對每個結點調用函數Visit一次且僅一次。 //一旦visit()失敗,則操作失敗 Status InOrderTraverse(BiTree T, Status(*Visit)(BiTree)); //T表示這個樹的根節點的指針 //采用二叉鏈表儲存結構,Visit是對結點操作的對應函數 //中序遍歷二叉樹T,對每個結點調用函數Visit一次且僅一次。 //一旦visit()失敗,則操作失敗 Status InOrderTraverse_2(BiTree T, Status(*Visit)(BiTree)); //采用二叉鏈表儲存結構,Visit是對數據元素操作的應用函數。 //中序遍歷二叉樹T的非遞歸算法,對每個數據元素調用函數Visit Status InOrderTraverse_3(BiTree T, Status(*Visit)(BiTree)); //采用二叉鏈表儲存結構,Visit是對數據元素操作的應用函數。 //中序遍歷二叉樹T的非遞歸算法,對每個數據元素調用函數Visit Status PostOrderTraverse(BiTree T, Status(*Visit)(BiTree)); //T表示這個樹的根節點的指針 //采用二叉鏈表儲存結構,Visit是對結點操作的對應函數 //后序遍歷二叉樹T,對每個結點調用函數Visit一次且僅一次。 //一旦visit()失敗,則操作失敗 Status LevelOrderTraverse(BiTree T, Status(*Visit)(BiTree)); //T表示這個樹的根節點的指針 //采用二叉鏈表儲存結構,Visit是對結點操作的對應函數 //層序遍歷二叉樹T,對每個結點調用函數Visit一次且僅一次。 //一旦visit()失敗,則操作失敗   Status Destroy(BiTree T);//摧毀T這個節點   Status DestroyBiTree(BiTree &T);   //摧毀二叉樹T #endif</pre>




在二叉樹的一些應用中,常常要求在樹中查找具有某種特征的結點,或者對樹中全部結點逐一進行某種處理。這就提出了一個遍歷二叉樹的問題,即如何按某條搜索路徑尋訪樹中每個結點,使得每個結點均被訪問一次,而且僅被訪問一次。二叉樹的遍歷又有很多情況,其中先序、中序、后序、層序遍歷是常見的情況

 

上述操作的實現:


<pre class="brush:cpp;toolbar:false">#include"stdafx.h" #include"ADT.h" #include<deque> #include<stack> //------------基本操作的函數原型說明(部分)------------ Status CreateBiTree(BiTree &T) //T表示這個樹的根節點的指針 //按先序次序輸入二叉樹中結點的值(一個字符),字符為空表示空樹, //構造二叉鏈表表示的二叉樹T {     char ch;     ch = getchar();     if (ch == ' '){         T = NULL; return OK;     }     else     {         if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))exit(MYOVERFLOW);         T->data = ch;         CreateBiTree(T->lchild);         CreateBiTree(T->rchild);     }     return OK; } Status VisitBiTree(BiTree T) //輸出結點的數據域 {         cout << T->data << " ";     return OK; } Status Destroy(BiTree T){//摧毀T這個節點     if (T){         free(T);     }     return OK; } Status PreOrderTraverse(BiTree T, Status(*Visit)(BiTree)) //T表示這個樹的根節點的指針 //采用二叉鏈表儲存結構,Visit是對結點操作的對應函數 //先序遍歷二叉樹T,對每個結點調用函數Visit一次且僅一次。 //一旦visit()失敗,則操作失敗 {     if (T){         BiTree lchild = T->lchild, rchild = T->rchild;         if(Visit(T))         if (PreOrderTraverse(lchild,Visit))         if (PreOrderTraverse(rchild, Visit))return OK;         return ERROR;     }     return OK; } Status InOrderTraverse(BiTree T, Status(*Visit)(BiTree)) //T表示這個樹的根節點的指針 //采用二叉鏈表儲存結構,Visit是對結點操作的對應函數 //中序遍歷二叉樹T,對每個結點調用函數Visit一次且僅一次。 //一旦visit()失敗,則操作失敗 {     if (T){         BiTree lchild = T->lchild, rchild = T->rchild;         if (InOrderTraverse(lchild, Visit))         if (Visit(T))         if (InOrderTraverse(rchild, Visit))return OK;         return ERROR;     }     return OK; } Status InOrderTraverse_2(BiTree T, Status(*Visit)(BiTree)) //采用二叉鏈表儲存結構,Visit是對數據元素操作的應用函數。 //中序遍歷二叉樹T的非遞歸算法,對每個數據元素調用函數Visit {     stack<BiTree> sta;     sta.push(T);     BiTree p;     while (!sta.empty()){         while (p = sta.top())sta.push(p->lchild);         sta.pop();         if (!sta.empty()){             p = sta.top();             sta.pop();             if (!Visit(p))return ERROR;             sta.push(p->rchild);         }     }     return OK; } Status InOrderTraverse_3(BiTree T, Status(*Visit)(BiTree)) //采用二叉鏈表儲存結構,Visit是對數據元素操作的應用函數。 //中序遍歷二叉樹T的非遞歸算法,對每個數據元素調用函數Visit {     stack<BiTree> sta;     BiTree p = T;     while (p || !sta.empty()){         if (p){ sta.push(p); p = p->lchild; }         else{             p = sta.top();             sta.pop();             if (!Visit(p))return ERROR;             p = p->rchild;         }     }     return OK; } Status PostOrderTraverse(BiTree T, Status(*Visit)(BiTree)) //T表示這個樹的根節點的指針 //采用二叉鏈表儲存結構,Visit是對結點操作的對應函數 //后序遍歷二叉樹T,對每個結點調用函數Visit一次且僅一次。 //一旦visit()失敗,則操作失敗 {     if (T){         BiTree lchild = T->lchild, rchild = T->rchild;         if (PostOrderTraverse(lchild, Visit))         if (PostOrderTraverse(rchild, Visit))         if (Visit(T))return OK;         return ERROR;     }     return OK; } Status LevelOrderTraverse(BiTree T, Status(*Visit)(BiTree)) //T表示這個樹的根節點的指針 //采用二叉鏈表儲存結構,Visit是對結點操作的對應函數 //層序遍歷二叉樹T,對每個結點調用函數Visit一次且僅一次。 //一旦visit()失敗,則操作失敗 {     deque<BiTree> deq;     if (T){         deq.push_back(T);         while (!deq.empty()){             auto temp  = deq.at(0);             Visit(temp);             if (temp->lchild)                 deq.push_back(temp->lchild);             if (temp->rchild)                 deq.push_back(temp->rchild);             deq.pop_front();         }     }     cout << endl;     return OK; } Status DestroyBiTree(BiTree &T) //摧毀二叉樹T {     if (PreOrderTraverse(T, Destroy))return OK;     return FALSE; }</pre>




主函數:


<pre class="brush:cpp;toolbar:false">// 二叉鏈表.cpp : 定義控制臺應用程序的入口點。 // #include "stdafx.h" int _tmain(int argc, _TCHAR* argv[]) {     BiTree T;     cout << "中序輸入二叉樹,如果某個節點的左右子樹為空,則輸入兩個空格:" << endl;     CreateBiTree(T);     cout << "先序遍歷" << endl;     PreOrderTraverse(T, VisitBiTree);     cout << endl;     cout << "中序遍歷"<<endl;     InOrderTraverse(T, VisitBiTree);     cout << endl;     InOrderTraverse_2(T, VisitBiTree);     cout << endl;     InOrderTraverse_3(T, VisitBiTree);     cout << endl;     cout << "后序遍歷"<<endl;     PostOrderTraverse(T, VisitBiTree);     cout << endl;     cout << "層序遍歷"<<endl;     LevelOrderTraverse(T, VisitBiTree);     DestroyBiTree(T);     return 0; }</pre>




結果:(在vs2013中實現,注意要在stadfx.h中包含相應的頭文件)




用二叉鏈表實現二叉樹的基本操作(構造及遍歷等)c  

<pre class="brush:cpp;toolbar:false">/*  先序遍歷二叉樹      若二叉樹為空,則空操作;否則     (1) 訪問根結點;     (2) 先序遍歷左子樹;     (3) 先序遍歷右子樹。     若二叉樹為空,則空操作;     中序遍歷二叉樹     若二叉樹為空,則空操作;否則     (1) 中序遍歷左子樹;     (2) 訪問根結點;     (3) 中序遍歷右子樹。     若二叉樹為空,則空操作;     后序遍歷二叉樹     若二叉樹為空,則空操作;否則     (1) 后序遍歷左子樹;     (2) 后序遍歷右子樹;     (3) 訪問根結點。  */ #include <iostream> using std::cin; using std::cout; using std::endl; typedef struct BiTNode {     char data;     struct BiTNode *Lchild, *Rchild; // 左、右孩子指針 } *BiTree; void CreateBiTree(BiTree &T){     // 在先序遍歷二叉樹的過程中輸入二叉樹的"先序字符串",     // 建立根指針為 T的二叉鏈表存儲結構。在先序字符串中,     // 字符'#'表示空樹,其它字母字符為結點的數據元素     char ch;     cin >> ch ;     if (ch=='#'){         T=NULL; // 建空樹     }else {         T = new BiTNode ;      // "訪問"操作為生成根結點         T->data = ch;         CreateBiTree(T->Lchild);    // 遞歸建(遍歷)左子樹         CreateBiTree(T->Rchild);    // 遞歸建(遍歷)右子樹     }//else }//CreateBiTree //先序遍歷以T為根指針的二叉樹 void PreOrder(BiTree &T){     if(T){                      // T=NULL時,二叉樹為空樹,不做任何操作         cout<< T->data << " ";  // 通過函數指針 *visit 訪問根結點         PreOrder(T->Lchild);    // 先序遍歷左子樹         PreOrder(T->Rchild);    // 先序遍歷右子樹     }// if } //中序遍歷以T為根指針的二叉樹 void InOrder(BiTree &T){     if(T){                    // T=NULL時,二叉樹為空樹,不做任何操作            InOrder(T->Lchild); // 先序遍歷左子樹         cout<< T->data << " "; // 通過函數指針 *visit 訪問根結點         InOrder(T->Rchild); // 先序遍歷右子樹     }// if } //后序遍歷以T為根指針的二叉樹 void PostOrder(BiTree &T){     if(T){                    // T=NULL時,二叉樹為空樹,不做任何操作            PostOrder(T->Lchild); // 先序遍歷左子樹         PostOrder(T->Rchild); // 先序遍歷右子樹                cout<< T->data << " "; // 通過函數指針 *visit 訪問根結點             }// if } // 先序遍歷二叉樹,以 count 返回二叉樹中葉子結點的數目 void CountLeaf(BiTree &T, int &count){     if (T) {         if ((!T->Lchild)&& (!T->Rchild))             count ;    // 對葉子結點計數         CountLeaf( T->Lchild, count);         CountLeaf( T->Rchild, count);     } // if } // CountLeaf // T指向二叉樹的根,level 為 T 所指結點所在層次, // 其初值為1,depth 為當前求得的最大層次,其初值為0 void BiTreeDepth(BiTree T, int level, int &depth){     if (T){         if (level>depth) depth=level;         BiTreeDepth(T->Lchild, level 1, depth);         BiTreeDepth(T->Rchild, level 1, depth);     }// if }// BiTreeDepth int main() {     cout << "請依次輸入字符: AB#CD###E#F##" << endl;     BiTree T;     CreateBiTree(T);     cout << "先序遍歷: " << endl;     PreOrder(T);     cout << endl << "中序遍歷: " << endl;     InOrder(T);     cout << endl << "后序遍歷: " << endl;     PostOrder(T);         int count = 0;     CountLeaf (T,count);     cout << endl << "此二叉樹葉子節點個數: " << count << endl;         int depth = 0;     BiTreeDepth(T,1,depth);     cout << endl << "此二叉樹深度: " << depth << endl;     return (0); }</pre>


您可能感興趣的文章:
二叉鏈表表示的二叉樹及基本操作
教你如何使用JSP繪制餅圖
jQuery 表格插件整理
mysql常用sql語句大全
javascript排序算法代碼解析
獲得優質高pr外鏈的方法
Mysql 多表聯合查詢效率分析及優化
php實現冒泡排序算法的代碼
怎么讓百度快速收錄新網站
Eclipse下jQuery文件報錯出現錯誤提示紅叉

[關閉]
北京pk赛车历史 白小姐资讯官方下载 黑龙江6+1开奖结果查询表近100期 云南时时彩图片 极速赛车前五后五技巧 北京快中彩开奖记录 河北20选5大星走势图 四川金7乐基本走势图 华东15选5玩法 金猎人配资 陕西快乐10分开奖结果走势图 黑龙江p62开奖视频 郑州期货配资哪家靠谱 if股指配资 广东36选7最新开奖结果查询结果 二分彩 海南4 1下载安装