C語言資料結構與演算法----樹和二叉樹全面總結（中）

目錄

一、前言

二、二叉樹的遍歷

1.先序遍歷

2.中序遍歷

3.后序遍歷

4.層次遍歷

三、遍歷演算法的應用

1.建立二叉鏈表存盤的二叉樹

2.輸出葉子結點

3.統計二叉樹葉子結點數目

4.求二叉樹高度

5.按樹狀列印二叉樹

四、線索二叉樹

1.基本概念

2.基本結構

3.建立中序線索化二叉樹

一、前言

• 學習目標：掌握二叉樹的先序、中序、后序、層次遍歷，對于遍歷演算法的五個應用要求掌握、線索二叉樹的基本結構和基本概念
• 重點：先序、中序、后序遍歷、線索二叉樹葉子結點判斷、二叉鏈表存盤
• 難點：線索二叉樹（理解就行）

二、二叉樹的遍歷

1.先序遍歷

動態圖：

演算法講解：

• 遍歷順序：根結點->左子樹->右子樹
• 動態圖解：一個小人從根結點開始，圍繞二叉樹的外圈開始跑，依次輸出序列

遞回代碼：

void  PreOrder(BiTree root) 
/*先序遍歷二叉樹, root為指向二叉樹(或某一子樹)根結點的指標*/
{
	if (root!=NULL)
	{
		Visit(root ->data);  /*訪問根結點*/
		PreOrder(root ->LChild);  /*先序遍歷左子樹*/
		PreOrder(root ->RChild);  /*先序遍歷右子樹*/
	}
}

2.中序遍歷

動態圖：

演算法講解：

• 遍歷順序：左子樹->根結點->右子樹
• 動態圖解：中序遍歷就像投影，將二叉樹從最左側到最右側依次投影到同一水平線線，得到的序列就是二叉樹的中序遍歷

遞回代碼：

void  InOrder(BiTree root)  
/*中序遍歷二叉樹, root為指向二叉樹(或某一子樹)根結點的指標*/
{
	if (root!=NULL)
	{
		InOrder(root ->LChild);   /*中序遍歷左子樹*/
		Visit(root ->data);        /*訪問根結點*/
		InOrder(root ->RChild);   /*中序遍歷右子樹*/
	}
}

3.后序遍歷

動態圖：

演算法講解：

• 遍歷順序：左子樹->右子樹->根結點
• 動態圖解：后序遍歷也是按照先序遍歷的順序輸出，不過后序遍歷就像剪葡萄，只能一個個剪，不能讓超過1個的葡萄一起掉下來，如上圖中的B，剪去B后面的D、E、H、I、J都會掉下來，H剪去只會掉下H

遞回代碼：

void  PostOrder(BiTree root)  
/*后序遍歷二叉樹, root為指向二叉樹(或某一子樹)根結點的指標*/
{
	if (root!=NULL)
	{
		PostOrder(root ->LChild);   /*后序遍歷左子樹*/
		PostOrder(root ->RChild);   /*后序遍歷右子樹*/
    	Visit(root ->data);        /*訪問根結點*/
     }
}

4.層次遍歷

動態圖：

演算法講解：

• 遍歷順序：一層一層開始遍歷（演算法不要求掌握）

三、遍歷演算法的應用

1.建立二叉鏈表存盤的二叉樹

void CreateBiTree(BiTree *bt)
   //按“擴展先序遍歷序列”建立二叉樹的二叉鏈表的演算法
{
    char ch;
    ch = getchar();
    if(ch==‘.’) *bt=NULL;  // 輸入時以點號“. ”表示空結點，
    else 
	{
	      *bt=(BiTree)malloc(sizeof(BiTNode)); //生成一個新結點  
          (*bt)->data=ch;
          CreateBiTree(&((*bt)->LChild)); //生成左子樹
          CreateBiTree(&((*bt)->RChild)); //生成右子樹
	}
}

2.輸出葉子結點

void  PreOrder(BiTree root) 
/*先序遍歷二叉樹, root為指向二叉樹根結點的指標*/
{
	if (root!=NULL)
	{
		if (root ->LChild==NULL && root ->RChild==NULL)
			printf("%c  ",root ->data);  /*輸出葉子結點*/
		PreOrder(root ->LChild);  /*先序遍歷左子樹*/
		PreOrder(root ->RChild);  /*先序遍歷右子樹*/
	}
}

3.統計二叉樹葉子結點數目

/* LeafCount保存葉子結點的數目的全域變數,呼叫之前初始化值為0 */ 
方法一：
void leaf_a(BiTree root)
{
	if(root!=NULL)
	{
		leaf_a(root->LChild);	
            leaf_a(root->RChild);
		if (root ->LChild==NULL && root ->RChild==NULL)
			LeafCount++;
	}
}

4.求二叉樹高度

int PostTreeDepth(BiTree bt)   /* 后序遍歷求二叉樹的高度遞回演算法 */
{
	int hl,hr,max;
	if(bt!=NULL)
	{
		hl=PostTreeDepth(bt->LChild);  /* 求左子樹的深度 */
		hr=PostTreeDepth(bt->RChild);  /* 求右子樹的深度 */
		max=hl>hr?hl:hr;              /* 得到左、右子樹深度較大者*/
		return(max+1);               /* 回傳樹的深度 */
	}
	else return(0);             /* 如果是空樹，則回傳0 */
}

5.按樹狀列印二叉樹

void PrintTree(BiTree bt,int nLayer)  /* 按豎向樹狀列印的二叉樹 */
{
	if(bt == NULL) return;
	PrintTree(bt->RChild,nLayer+1);
	for(int i=0;i<nLayer;i++)
		printf("  ");
	printf("%c\n",bt->data);
	PrintTree(bt->LChild,nLayer+1);
}

四、線索二叉樹

1.基本概念

• 前驅和后繼：在二叉樹先序、中序、后序、層次遍歷之后得到的序列，前一個是前驅，后一個是后繼
• 線索：指向前驅或后繼結點的指標
• 線索化：對二叉樹進行某種遍歷次序，使之變成線索二叉樹的程序
• 線索二叉樹：加上線索的二叉鏈表

2.基本結構

• 
• 孩子指標域：LChild指向左孩子，RChild指向右孩子
• 標志域Ltag：Ltag==1,表示LChild指向左孩子，Ltag==0表示LChild指向前驅
• 標志域Rtag：Rtag==1,表示RChild指向左孩子，Rtag==0表示RChild指向前驅
• 選擇題表示結點p為葉子結點的是：p->Ltag==1&&p->Rtag==1

結構體：

typedef  struct node
{    int  data;
     int ltag, rtag;
     struct node *lchild, *rchild;
}JD;

3.建立中序線索化二叉樹

動態圖：

演算法講解：

• LTag=0, LChild指向根結點
• RTag=1, RChild指向遍歷序列中最后一個結點
• 遍歷序列中第一個結點的LChild域和最后一個結點的RChild域都指向根結點

代碼：

void  Inthread(BiTree root)
/* 對root所指的二叉樹進行中序線索化，其中pre始終指向剛訪問過的結點，其初值為NULL*/
{
	if (root!=NULL)
	{ 
		Inthread(root->LChild);  /* 線索化左子樹 */
		if (root->LChild==NULL)
		{
			root->Ltag=1; 
			root->LChild=pre;  /*置前驅線索 */
		}
		if (pre!=NULL&& pre->RChild==NULL)  /* 置后繼線索 */
		{
			pre->RChild=root;
			pre->Rtag=1;
		}
	        pre=root;
	       Inthread(root->RChild);  /*線索化右子樹*/
	}
}	

文章遍歷的動態圖片參考：

【資料結構】理解二叉樹的三種遍歷--前序、中序、后序 +層序（簡明易懂）

附錄：

• C語言資料結構與演算法----串全面總結

• C語言資料結構與演算法----堆疊全面總結

• C語言資料結構與演算法----佇列全面總結

• C語言資料結構與演算法----陣列和廣義表全面總結

• C語言資料結構與演算法----排序全面總結(一)

• C語言資料結構與演算法----排序全面總結(二)

• C語言資料結構與演算法----樹和二叉樹全面總結（上）

• 歡迎大家訂閱專欄！