代碼參考《妙趣橫生的算法.C語言實(shí)現(xiàn)》

文章目錄

• 前言
• • 1、樹的概念
  • 2、二叉樹
  • 3、二叉樹的遍歷
  • 4、創(chuàng)建二叉樹
  • 5、實(shí)例分析

---

前言

本章總結(jié)：樹的概念、二叉樹的創(chuàng)建、遍歷

---

1、樹的概念

樹結(jié)構(gòu)是以分支關(guān)系定義得一種層次結(jié)構(gòu)。
樹的定義：樹是由n(n>=0)個結(jié)點(diǎn)組成的有窮集合。在任意的一棵非空樹中：
1、有且僅有一個稱為根(root)的結(jié)點(diǎn)
2、當(dāng)n>1時，其余的結(jié)點(diǎn)分為m(m>0)個互不相交的有限集合T1,T2,T3,…Tm.其中每個集合本身又是一棵樹，并稱為跟的子樹(SubTree)

以上圖為例，A是root，BCD是A的child，以BCD為根節(jié)點(diǎn)構(gòu)成3棵樹，為A的字·SubTree。
樹的存儲形式：多重鏈表，在多重鏈表中每個結(jié)點(diǎn)由一個數(shù)據(jù)域和若干個指針域組成，其中每個指針域指向該結(jié)點(diǎn)的一個孩子結(jié)點(diǎn)。
多重鏈表結(jié)點(diǎn)類型描述：

#define MaxChild 10 typedef struct node {ElemType data;struct node* child[MaxChild]; //指向孩子結(jié)點(diǎn)的指針數(shù)組，將父節(jié)結(jié)點(diǎn)和子結(jié)點(diǎn)聯(lián)系起來 };

在利用多重鏈表表示樹結(jié)構(gòu)時分定長結(jié)點(diǎn)（每個結(jié)點(diǎn)的指針域個數(shù)固定）和不定長結(jié)點(diǎn)（每個結(jié)點(diǎn)的指針域個數(shù)不固定）

對于二叉樹來說，一個結(jié)點(diǎn)至多可以有左右兩個孩子結(jié)點(diǎn)，或者只有一個孩子結(jié)點(diǎn)，或者沒有孩子結(jié)點(diǎn)。
T是一個指針，指向二叉樹的根結(jié)點(diǎn)。只有得到T，才能訪問整個樹結(jié)構(gòu)。

2、二叉樹

二叉樹的遞歸定義：二叉樹是這樣的樹結(jié)構(gòu)，它或者為空，或者由一個根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右字?jǐn)?shù)的互不相交的二叉樹組成。

二叉樹結(jié)點(diǎn)有三個域,lchild、rchild為指針域，用來指向該結(jié)點(diǎn)的左孩子和右孩子。data是數(shù)據(jù)域，用來存放該結(jié)點(diǎn)中包含的數(shù)據(jù)。

//二叉樹結(jié)點(diǎn)定義 typedef struct BiTNode {ElemType data;struct BiTNode* lchild, * rchild; }BiTNode,*BiTreee; //二叉樹結(jié)點(diǎn)類BiTNode,二叉樹每個結(jié)點(diǎn)都屬于該類型 //BiTree是一個指向BiTNode類型數(shù)據(jù)的指針

3、二叉樹的遍歷

從一個結(jié)點(diǎn)(一般來說是根結(jié)點(diǎn))出發(fā)，按一定規(guī)律訪問二叉樹的全部結(jié)點(diǎn)，每個結(jié)點(diǎn)只訪問一次。

應(yīng)用二叉樹遞歸地邏輯特性，采用遞歸方法遍歷二叉樹。

1、先序遍歷

1、訪問根結(jié)點(diǎn)

2、先序遍歷左子樹

3、先序遍歷右子樹

2、中序遍歷

1、中序遍歷左子樹

2、訪問根結(jié)點(diǎn)

3、中序遍歷右子樹

//定義visit函數(shù) //訪問結(jié)點(diǎn),輸出結(jié)點(diǎn)的層數(shù) void visit(char c) {printf("%c is at %d the level of BiTree\n"); } //**********************遍歷二叉樹*********************// //先序遍歷 void PreOrderTraverse(BiTreee T) {if (T) //遞歸結(jié)束條件，T為空{visit(T->data); //訪問根結(jié)點(diǎn)PreOrderTraverse(T->lchild); //先序遍歷左子樹PreOrderTraverse(T->rchild); //先序遍歷右子樹} } //中序遍歷 void InOrderTraverse(BiTreee T) {if (T) //遞歸結(jié)束條件，T為空{InOrderTraverse(T->lchild); //先序遍歷左子樹visit(T->data); //訪問根結(jié)點(diǎn)InOrderTraverse(T->rchild); //先序遍歷右子樹} } //后序遍歷 void PosOrderTraverse(BiTreee T) {if (T) //遞歸結(jié)束條件，T為空{PosOrderTraverse(T->lchild); //先序遍歷左子樹PosOrderTraverse(T->rchild); //先序遍歷右子樹visit(T->data); //訪問根結(jié)點(diǎn)} }

4、創(chuàng)建二叉樹

借鑒二叉樹的遍歷算法也可以逐個生成結(jié)點(diǎn)，從而創(chuàng)建出一個二叉樹。

//先序創(chuàng)建一棵二叉樹 void CreateBiTree(BiTreee* T) {char c;scanf("%c",&c);if (c == ' ') *T = NULL;else{*T = (BiTNode *)malloc(sizeof(BiTNode)); //創(chuàng)建根結(jié)點(diǎn)(*T)->data = c; //向根結(jié)點(diǎn)中輸入數(shù)據(jù)CreateBiTree(&((*T)->lchild)); //遞歸地創(chuàng)建左子樹CreateBiTree(&((*T)->rchild)); //遞歸地創(chuàng)建右子樹} } //依次輸入：ABC D E F // //空格是遞歸結(jié)束的標(biāo)志，當(dāng)創(chuàng)建到葉子結(jié)點(diǎn)時，因?yàn)槿~子結(jié)點(diǎn)的左右子樹都為空，因此要輸入空格表示結(jié)束。在創(chuàng)建二叉樹的過程中，程序總是按照：創(chuàng)建根結(jié)點(diǎn)-創(chuàng)建左子樹-創(chuàng)建右子樹順序進(jìn)行

5、實(shí)例分析

用先序創(chuàng)建一棵樹，并輸出每個字符位于二叉樹的層數(shù)

#include "stdio.h" #include "malloc.h" #include "conio.h" #include <stdlib.h> #include <math.h> typedef char ElemType ; #define MaxChild 10 typedef struct node {ElemType data;struct node* child[MaxChild]; //指向孩子結(jié)點(diǎn)的指針數(shù)組，將父節(jié)結(jié)點(diǎn)和子結(jié)點(diǎn)聯(lián)系起來 }; //在利用多重鏈表表示樹結(jié)構(gòu)時分定長結(jié)點(diǎn)（每個結(jié)點(diǎn)的指針域個數(shù)固定）和不定長結(jié)點(diǎn)（每個結(jié)點(diǎn)的指針域個數(shù)不固定） //對于二叉樹來說，一個結(jié)點(diǎn)至多可以有左右兩個孩子結(jié)點(diǎn)，或者只有一個孩子結(jié)點(diǎn)，或者沒有孩子結(jié)點(diǎn)。 //T是一個指針，指向二叉樹的根結(jié)點(diǎn)。只有得到T，才能訪問整個樹結(jié)構(gòu)。//二叉樹結(jié)點(diǎn)定義 typedef struct BiTNode {ElemType data;struct BiTNode* lchild, * rchild; }BiTNode,*BiTreee; //二叉樹結(jié)點(diǎn)類BiTNode,二叉樹每個結(jié)點(diǎn)都屬于該類型 //BiTree是一個指向BiTNode類型數(shù)據(jù)的指針//定義visit函數(shù) //訪問結(jié)點(diǎn),輸出結(jié)點(diǎn)的層數(shù) void visit(char c,int level) {printf("%c is at %d the level of BiTree\n",c, level); } //**********************遍歷二叉樹*********************// //先序遍歷 void PreOrderTraverse(BiTreee T,int level) {if (T) //遞歸結(jié)束條件，T為空{visit(T->data,level); //訪問根結(jié)點(diǎn)PreOrderTraverse(T->lchild, level+1); //先序遍歷左子樹,層數(shù)+1PreOrderTraverse(T->rchild, level+1); //先序遍歷右子樹,層數(shù)+1} } //中序遍歷 void InOrderTraverse(BiTreee T, int level) {if (T) //遞歸結(jié)束條件，T為空{InOrderTraverse(T->lchild, level + 1); //中序遍歷左子樹,層數(shù)+1visit(T->data, level); //訪問根結(jié)點(diǎn)InOrderTraverse(T->rchild, level+1); //中序遍歷右子樹,層數(shù)+1} } //后序遍歷 void PosOrderTraverse(BiTreee T, int level) {if (T) //遞歸結(jié)束條件，T為空{PosOrderTraverse(T->lchild, level + 1); //中序遍歷左子樹,層數(shù)+1PosOrderTraverse(T->rchild, level+1); //中序遍歷右子樹,層數(shù)+1visit(T->data, level); //訪問根結(jié)點(diǎn)} } //先序創(chuàng)建一棵二叉樹 void CreateBiTree(BiTreee* T) {char c;scanf("%c",&c);if (c == '@') *T = NULL;else{*T = (BiTNode *)malloc(sizeof(BiTNode)); //創(chuàng)建根結(jié)點(diǎn)(*T)->data = c; //向根結(jié)點(diǎn)中輸入數(shù)據(jù)CreateBiTree(&((*T)->lchild)); //遞歸地創(chuàng)建左子樹CreateBiTree(&((*T)->rchild)); //遞歸地創(chuàng)建右子樹} } //依次輸入：ABC D E F // //空格是遞歸結(jié)束的標(biāo)志，當(dāng)創(chuàng)建到葉子結(jié)點(diǎn)時，因?yàn)槿~子結(jié)點(diǎn)的左右子樹都為空，因此要輸入空格表示結(jié)束。在創(chuàng)建二叉樹的過程中，程序總是按照：創(chuàng)建根結(jié)點(diǎn)-創(chuàng)建左子樹-創(chuàng)建右子樹順序進(jìn)行//測試程序 int main() {int level = 1;BiTreee T = NULL;printf("創(chuàng)建二叉樹\n");CreateBiTree(&T); //創(chuàng)建二叉樹printf("==================先序遍歷==========================\n");PreOrderTraverse(T,level); //先序遍歷level = 1;printf("==================中序遍歷==========================\n");InOrderTraverse(T, level); //先序遍歷level = 1;printf("==================后序遍歷==========================\n");PosOrderTraverse(T, level); //先序遍歷level = 1;_getche();return 0; }

效果：

結(jié)果顯然對的，并且能夠顯示出三種遍歷方式的具體遍歷過程

總結(jié)

以上是生活随笔為你收集整理的【数据结构基础笔记】【树】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。