二叉樹的三種遍歷(雙鏈表實(shí)現(xiàn))以及遞歸思想的個(gè)人理解--C語(yǔ)言-創(chuàng)新互聯(lián)

文章目錄

• 二叉樹
• 實(shí)現(xiàn)一個(gè)數(shù)組的二叉樹插入遍歷
• 創(chuàng)建一個(gè)二叉樹雙鏈表
• 插入結(jié)點(diǎn)
• 三種遍歷
• • 前序遍歷
  • 中序遍歷
  • 后序遍歷
  • 遞歸思想

在海拉爾等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供做網(wǎng)站、成都網(wǎng)站建設(shè) 網(wǎng)站設(shè)計(jì)制作按需網(wǎng)站建設(shè),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),高端網(wǎng)站設(shè)計(jì),成都營(yíng)銷網(wǎng)站建設(shè),外貿(mào)網(wǎng)站制作,海拉爾網(wǎng)站建設(shè)費(fèi)用合理。二叉樹

二叉樹（Binary tree）是樹形結(jié)構(gòu)的一個(gè)重要類型。許多實(shí)際問(wèn)題抽象出來(lái)的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹形式，即使是一般的樹也能簡(jiǎn)單地轉(zhuǎn)換為二叉樹，而且二叉樹的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡(jiǎn)單，因此二叉樹顯得特別重要。二叉樹特點(diǎn)是每個(gè)節(jié)點(diǎn)最多只能有兩棵子樹，且有左右之分。所以實(shí)現(xiàn)二叉樹的遍歷用雙鏈表比較簡(jiǎn)單。

實(shí)現(xiàn)一個(gè)數(shù)組的二叉樹插入遍歷

data_type arr[] = {35,45,23,44,33,65,13,54};

創(chuàng)建一個(gè)二叉樹雙鏈表

根據(jù)二叉樹的特點(diǎn)，我們定義一個(gè)包含左右孩子和本身數(shù)據(jù)的結(jié)構(gòu)體作為根結(jié)點(diǎn)

typedef int data_type;

typedef struct treeNode
{struct treeNode *lchild;
	struct treeNode *rchild;
	data_type data;
}tree;

寫一個(gè)申請(qǐng)根節(jié)點(diǎn)的函數(shù)，返回申請(qǐng)到的空間的首地址

tree *createTree(data_type item)
{tree *pRoot = NULL;
	pRoot = (tree *)malloc(sizeof(tree));
	if(pRoot == NULL)
	{return NULL;
	}
	memset(pRoot,0,sizeof(tree));
	pRoot->data = item;

	return pRoot;
}

插入結(jié)點(diǎn)

插入結(jié)點(diǎn)時(shí)，我們要先判斷插入的值和根結(jié)點(diǎn)值誰(shuí)更大，比根結(jié)點(diǎn)大我們將他插入到左孩子中，否則插入到右孩子中

int insertTree(tree *pRoot,data_type item)
{tree *pNew = NULL;
	pNew = (tree *)malloc(sizeof(tree));
	if(pNew == NULL)
	{return -1;
	}
	memset(pNew,0,sizeof(tree));
	pNew->data = item;
	while(1)
	{		if(pNew->data< pRoot->data)//插入左孩子處
		{	if(pRoot->lchild != NULL)
			{		pRoot = pRoot->lchild;
			}
			else
			{		pRoot->lchild = pNew;
				return 0;
			}
		}
		else
		{	if(pRoot->rchild != NULL)//插入右孩子處
			{		pRoot = pRoot->rchild;
			}
			else
			{		pRoot->rchild = pNew;
				return 0;
			}
		}
	}
}

三種遍歷

二叉樹的遍歷分為以下三種：

• 先序遍歷：遍歷順序規(guī)則為【根左右】

• 中序遍歷：遍歷順序規(guī)則為【左根右】

• 后序遍歷：遍歷順序規(guī)則為【左右根】

利用遞歸思想，實(shí)現(xiàn)二叉樹的遍歷。會(huì)在末尾講解二叉樹的遞歸

前序遍歷

//前序遍歷
int preOrder(tree *pRoot)
{if(pRoot == NULL)
	{return -1;
	}
	//先訪問(wèn)根結(jié)點(diǎn)
	printf("%d ",pRoot->data);
	//訪問(wèn)左子樹
	preOrder(pRoot->lchild);
	//訪問(wèn)右子樹
	preOrder(pRoot->rchild);
}

中序遍歷

//中序遍歷
int inOrder(tree *pRoot)
{if(pRoot == NULL)
	{return -1;
	}
	inOrder(pRoot->lchild);
	printf("%d ",pRoot->data);
	inOrder(pRoot->rchild);
}

后序遍歷

//后序遍歷
int postOrder(tree *pRoot)
{if(pRoot == NULL)
	{return -1;
	}
	postOrder(pRoot->lchild);
	postOrder(pRoot->rchild);
	printf("%d ",pRoot->data);
}

遞歸思想

拿我們的前序遍歷來(lái)講解

if(pRoot == NULL)
	{return -1;
	}
	//先訪問(wèn)根結(jié)點(diǎn)
	printf("%d ",pRoot->data); // 1
	//訪問(wèn)左子樹
	preOrder(pRoot->lchild); // 2
	//訪問(wèn)右子樹
	preOrder(pRoot->rchild); // 3

接下來(lái)用一張自己畫的圖來(lái)詳細(xì)說(shuō)明

以上是我對(duì)遞歸思想的理解，如有錯(cuò)誤請(qǐng)指正！

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁(yè)名稱：二叉樹的三種遍歷(雙鏈表實(shí)現(xiàn))以及遞歸思想的個(gè)人理解--C語(yǔ)言-創(chuàng)新互聯(lián)
地址分享：http://muchs.cn/article22/dhcojc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、網(wǎng)站內(nèi)鏈、面包屑導(dǎo)航、網(wǎng)站排名、營(yíng)銷型網(wǎng)站建設(shè)、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)