一般我們在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時候都會實(shí)現(xiàn)它最基本的增刪查改方式，但是二叉樹這個數(shù)據(jù)結(jié)構(gòu)不太一般，增刪查改沒有什么意義，由于二叉樹的相關(guān)遍歷涉及到遞歸，我們先不學(xué)習(xí)創(chuàng)建二叉樹，而是從遍歷開始

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

簡單的創(chuàng)建一個二叉樹并不難，創(chuàng)建幾個節(jié)點(diǎn)然后當(dāng)作二叉樹連起來即可：

typedef  int   BTDataType;


typedef struct BTNode
{
	BTDataType data;
	struct BTNode* left;
	struct BTNode* right;
}BT;


BT* CreatTree()
{
	BT* n1 = (BT*)malloc(sizeof(BT));
	assert(n1);
	BT* n2 = (BT*)malloc(sizeof(BT));
	assert(n2);
	BT* n3 = (BT*)malloc(sizeof(BT));
	assert(n3);
	BT* n4 = (BT*)malloc(sizeof(BT));
	assert(n4);
	BT* n5 = (BT*)malloc(sizeof(BT));
	assert(n5);
	BT* n6 = (BT*)malloc(sizeof(BT));
	assert(n6);

	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n2->right = NULL;
	n3->left = NULL;
	n3->right = NULL;
	n4->left = n5;
	n4->right = n6;
	n5->left = NULL;
	n5->right = NULL;
	n6->left = NULL;
	n6->right = NULL;


	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;
	n5->data = 5;
	n6->data = 6;

	return n1;
}

邏輯結(jié)構(gòu)如下圖：

二叉樹的遍歷：

前序遍歷：

void preOrder(BT* root)
{

	if (root == NULL)
	{
		printf("NULL ");
		return;
	}


	printf("%d ", root->data);
	preOrder(root->left);
	preOrder(root->right);
}

中序遍歷：

void MidOrder(BT* root)
{

	if (root == NULL)
	{
		printf("NULL ");
		return;
	}


	preOrder(root->left);
	printf("%d ", root->data);

	preOrder(root->right);
}

后序遍歷:

//后序遍歷
void leftOrder(BT* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}


	preOrder(root->left);
	preOrder(root->right);
	printf("%d ", root->data);

}

二叉樹功能實(shí)現(xiàn)：

二叉樹節(jié)點(diǎn)個數(shù)：

int TreeSize(BT* root)
{
	if (root == NULL)
		return 0;

	return TreeSize(root->left) + TreeSize(root->right) + 1;
}

二叉樹葉子節(jié)點(diǎn)個數(shù)：

int BinaryTreeLeafSize(BT* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;

	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

二叉樹高度：

int BinaryTreeLeafHeight(BT* root)
{
	if (root == NULL)
		return 0;

	int left = BinaryTreeLeafHeight(root->left) + 1;
	int right = BinaryTreeLeafHeight(root->right) + 1;

	if (left >right)
		return left;
	else
		return right;

}

二叉樹第k層節(jié)點(diǎn)個數(shù)：

int BinaryTreeLevelKSize(BT* root, int k)
{
	assert(k >0);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;

	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);


}

二叉樹查找值為x的節(jié)點(diǎn)：

BT* BinaryTreeFind(BT* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

	if (root->data == x)
		return root;

	BT* leftret = BinaryTreeFind(root->left, x);

	if (leftret)
		return leftret;

	BT* rightret  = BinaryTreeFind(root->right, x);

	if (rightret)
		return rightret;
	return NULL;

}

?一些有關(guān)二叉樹的題目

相信不少的讀者在第一次接觸到二叉樹的時候?qū)f歸的把握并不深刻，在這里，其實(shí)遞歸的本質(zhì)就是拋去了我們平常寫代碼注重全局的思想，改成了注重每次遞歸的時候應(yīng)該做的事情，我個人沒法詳細(xì)表述的很好，在這里推薦一篇文章：三道題套路解決遞歸問題 | lyl's blog

單值二叉樹：

鏈接：力扣

if(root== NULL)
        return true;


        if(root->left && root->val != root ->left ->val )
        return false;
        if(root->right && root->val != root ->right ->val)
        return false;

        bool lefret = isUnivalTree(root ->left);
        bool rightret = isUnivalTree(root ->right);


        return lefret && rightret;

同遍歷整個二叉樹查找某個值的邏輯相同。

翻轉(zhuǎn)二叉樹：

鏈接：力扣

思路：面對遞歸類型的題目，不應(yīng)該直接專注于解決一整顆樹上，而是每一步應(yīng)該做什么，這題的主體每步的邏輯就是置換左右子樹，那么我們不需要多想，直接交換左右子樹，剩下的交給遞歸處理，不需要過度的照顧全局。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {

        if(root == NULL)
        return NULL;

        struct TreeNode* tmp = root->left;
        root ->left = root->right;

        invertTree(root->left);
        invertTree(root->right);

        return root;

    }
};

相同的樹：

鏈接：力扣

思路：同上的翻轉(zhuǎn)相同，我們只需要關(guān)注每一個節(jié)點(diǎn)對比的值是否符合要求即可，剩下的交給遞歸

bool?isSameTree(struct?TreeNode*?p,?struct?TreeNode*?q){
????if(p?==?NULL?&&?q?==?NULL)
????return?true;


????if(p?==?NULL?||?q?==?NULL)
????return?false;


????if(p->val?!=?q->val)
????return?false;


????bool?leftret?=?isSameTree(p->left,q->left);
????bool?rightret?=?isSameTree(p->right,q->right);


????return?leftret?&&?rightret?;


}

層序遍歷：

由于遞歸的棧幀消耗還是比較大的，所以用非遞歸的方法來遍歷二叉樹還是非常有必要的，借助隊列的先進(jìn)先出的特性可以很好的實(shí)現(xiàn)非遞歸遍歷。

思路：二叉樹無非就是跟和左子樹右子樹的問題，邏輯上來說，在我們在到達(dá)一個節(jié)點(diǎn)的時候接下來就是得到它的值或者是左子樹右子樹，那么我們就只需要先將根節(jié)點(diǎn)入隊列，再將根的左子樹右子樹入隊列，把根出隊列后，再把其左右子樹視作新根，再拆開成為左右子樹，以達(dá)到層序遍歷的效果。

void BinaryTreeLevelOrder(BTNode* root)// 層序遍歷
{
	Queue q;
	QueueInit(&q);
	if (root)//root不為空，放數(shù)據(jù)
		QueuePush(&q,root);
 
	while (!QueueEmpty(&q))//如果隊列不為空，則循環(huán)
	{
		BTNode* front = QueueFront(&q);//拿隊頭數(shù)據(jù)
		printf("%d ", front->data);
		QueuePop(&q);
		if (front->left)
			QueuePush(&q, front->left);
 
		if (front->right)
			QueuePush(&q, front->right);
	}
 
	QueueDestroy(&q);
}

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

分享題目：數(shù)據(jù)結(jié)構(gòu)7：基本的二叉樹遍歷及題目-創(chuàng)新互聯(lián)
分享URL：http://weahome.cn/article/dhopoi.html