C語(yǔ)言進(jìn)階二叉樹(shù)的基礎(chǔ)與銷(xiāo)毀及層序遍歷詳解

更新時(shí)間：2022年06月24日 10:20:25 作者：配的上了嗎

朋友們好,這篇播客我們繼續(xù)C++的初階學(xué)習(xí)，現(xiàn)在對(duì)我們對(duì)C++的二叉樹(shù)基礎(chǔ)oj與二叉樹(shù)銷(xiāo)毀和層序遍歷進(jìn)行練習(xí)，讓我們相互學(xué)習(xí),共同進(jìn)步

單值二叉樹(shù)

難度簡(jiǎn)單

如果二叉樹(shù)每個(gè)節(jié)點(diǎn)都具有相同的值，那么該二叉樹(shù)就是單值二叉樹(shù)。

只有給定的樹(shù)是單值二叉樹(shù)時(shí)，才返回true；否則返回false。

示例 1：

輸入：[1,1,1,1,1,null,1]
輸出：true

示例 2：

輸入：[2,2,2,5,2]
輸出：false

提示：

給定樹(shù)的節(jié)點(diǎn)數(shù)范圍是[1, 100]。

每個(gè)節(jié)點(diǎn)的值都是整數(shù)，范圍為[0, 99]。

解1：

最簡(jiǎn)單易懂的解法，先序遍歷一遍，把每個(gè)節(jié)點(diǎn)都和那個(gè)根節(jié)點(diǎn)的val值相比。最后判斷flag是否為真，若為假，則表明樹(shù)中有某節(jié)點(diǎn)的值不符。

其中的return語(yǔ)句是為了避免一些無(wú)意義的比較，但是其實(shí)第一個(gè)if的flag判斷完全可以寫(xiě)在左遞歸之后，判斷一下，如果左遞歸將flag置為了假，則直接return，不會(huì)進(jìn)入右子樹(shù)。如果按照上方解法來(lái)說(shuō)，就是進(jìn)入右子樹(shù)之后，發(fā)現(xiàn)flag為假，再退出。

OJ題里的全局變量需要小心使用，若isUnivalTree里的flag不置為真，則多個(gè)測(cè)試用例時(shí)，可能會(huì)承接上一個(gè)測(cè)試用例假的結(jié)果。發(fā)生錯(cuò)誤。

解法2：

class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        if(root == NULL)
            return true;
        if(root->left != nullptr && root->left->val != root->val)
            return false;
        if(root->right != nullptr && root->right->val != root->val)
            return false;
        return isUnivalTree(root->left) 
            && isUnivalTree(root->right);
    }
};

判斷每個(gè)結(jié)點(diǎn)和其兩個(gè)子節(jié)點(diǎn)是否相同，當(dāng)然，需要確保子節(jié)點(diǎn)非空，若存在不同的，直接返回false，然后遞歸其左右子樹(shù)。

其實(shí)這個(gè)的實(shí)質(zhì)就是前序遍歷，對(duì)每個(gè)結(jié)點(diǎn)的操作就是比較它和兩個(gè)子節(jié)點(diǎn)的值是否相同。每個(gè)結(jié)點(diǎn)如果都和其左右子結(jié)點(diǎn)相同，那么這棵樹(shù)也就都相同了，如果某處不同，則返回false，層層返回，最終也會(huì)返回flase。

解法3：

class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        bool ret = PreOrder(root, root->val);
        return ret;
    }
    bool PreOrder(TreeNode* root, int val)
    {
        if(root == nullptr)
            return true;
        if(root->val != val)
            return false;
        return PreOrder(root->left, val)
            && PreOrder(root->right, val);
    }
};

與2相比沒(méi)什么大的改進(jìn)，只是比較的方式不同而已，仍然是前序遍歷的思想。第三個(gè)return里的&&挺好，左是假則不會(huì)對(duì)右求值。

相同的樹(shù)

難度簡(jiǎn)單844

給你兩棵二叉樹(shù)的根節(jié)點(diǎn)p和q，編寫(xiě)一個(gè)函數(shù)來(lái)檢驗(yàn)這兩棵樹(shù)是否相同。

如果兩個(gè)樹(shù)在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的。

示例 1：

輸入：p = [1,2,3], q = [1,2,3]
輸出：true

示例 2：

輸入：p = [1,2], q = [1,null,2]
???????輸出：false

示例 3：

輸入：p = [1,2,1], q = [1,1,2]
???????輸出：false

提示：

兩棵樹(shù)上的節(jié)點(diǎn)數(shù)目都在范圍[0, 100]內(nèi)
-104<= Node.val <= 104

通過(guò)次數(shù)344,943提交次數(shù)577,105

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == nullptr && q == nullptr)
            return true;
        if(!(p!=nullptr && q!=nullptr && p->val == q->val))
            return false;
        bool retl = isSameTree(p->left,q->left);
        if(retl == false)
            return false;
        bool retr = isSameTree(p->right,q->right);
        if(retr == false)
            return false;
        return true;
/*
        return isSameTree(p->left,q->left)
            && isSameTree(p->right,q->right);
*/
    }
};

億億億億億億億億億億舊是前序遍歷,只是兩棵樹(shù)同時(shí)遍歷而已，判斷是否相同，兩個(gè)遞歸和最后那個(gè)注釋的是效果相同的。

對(duì)稱(chēng)二叉樹(shù)

難度簡(jiǎn)單1942

給你一個(gè)二叉樹(shù)的根節(jié)點(diǎn)root，檢查它是否軸對(duì)稱(chēng)。

示例 1：

輸入：root = [1,2,2,3,4,4,3]
???????輸出：true

示例 2：

輸入：root = [1,2,2,null,3,null,3]
???????輸出：false

提示：

樹(shù)中節(jié)點(diǎn)數(shù)目在范圍[1, 1000]內(nèi)
-100 <= Node.val <= 100

進(jìn)階：你可以運(yùn)用遞歸和迭代兩種方法解決這個(gè)問(wèn)題嗎？

通過(guò)次數(shù)603,527提交次數(shù)1,044,923

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return isSame(root->left, root->right);
    }
    bool isSame(TreeNode* root1, TreeNode* root2)
    {
        if(root1 == nullptr && root2 == nullptr)  // 都是空，結(jié)束遞歸，且符合條件
            return true;
        // 兩者根節(jié)點(diǎn)不相等，結(jié)束，不需要進(jìn)一步判斷了。
        if(!(root1 != nullptr && root2 != nullptr && root1->val == root2->val))  
            return false;
        // 進(jìn)一步判斷
        return isSame(root1->left,root2->right) && isSame(root1->right,root2->left);
    }
};

依舊是前序遍歷。。。。。。。。。

另一棵樹(shù)的子樹(shù)

難度簡(jiǎn)單739

給你兩棵二叉樹(shù)root和subRoot。檢驗(yàn)root中是否包含和subRoot具有相同結(jié)構(gòu)和節(jié)點(diǎn)值的子樹(shù)。如果存在，返回true；否則，返回false。

二叉樹(shù)tree的一棵子樹(shù)包括tree的某個(gè)節(jié)點(diǎn)和這個(gè)節(jié)點(diǎn)的所有后代節(jié)點(diǎn)。tree也可以看做它自身的一棵子樹(shù)。

示例 1：

輸入：root = [3,4,5,1,2], subRoot = [4,1,2]
???????輸出：true

示例 2：

輸入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
???????輸出：false

提示：

root樹(shù)上的節(jié)點(diǎn)數(shù)量范圍是[1, 2000]
???????subRoot樹(shù)上的節(jié)點(diǎn)數(shù)量范圍是[1, 1000]
???????-104<= root.val <= 104
-104<= subRoot.val <= 104

通過(guò)次數(shù)125,811提交次數(shù)264,360

class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(root == nullptr)
            return false;
        if(isSameTree(root, subRoot);)
            return true;
        if(isSubtree(root->left,subRoot);)
            return true;
        if(isSubtree(root->right,subRoot);)
            return true;
        return false;
    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == nullptr && q == nullptr)
            return true;
        if(!(p!=nullptr && q!=nullptr && p->val == q->val))
            return false;
        bool retl = isSameTree(p->left,q->left);
        if(retl == false)
            return false;
        bool retr = isSameTree(p->right,q->right);
        if(retr == false)
            return false;
        return true;
    }
};

判斷一個(gè)樹(shù)是不是另一個(gè)的子樹(shù)，這里的解法仍然是前序遍歷，思路就是遍歷每一個(gè)非空結(jié)點(diǎn)，把這個(gè)結(jié)點(diǎn)看成某一個(gè)樹(shù)的根節(jié)點(diǎn)，只是這些根節(jié)點(diǎn)或大或小而已，然后調(diào)用isSameTree函數(shù)判斷兩個(gè)樹(shù)是否相同。思路還是那么一個(gè)思路，沒(méi)什么兩樣。

給出個(gè)錯(cuò)誤解法吧：

class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(root == nullptr)
            return false;
        bool ret = isSameTree(root, subRoot);
        if(ret == true)
            return true;
        ret = isSameTree(root->left,subRoot);
        if(ret == true)
            return true;
        ret = isSameTree(root->right,subRoot);
        if(ret == true)
            return true;
        return false;
    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == nullptr && q == nullptr)
            return true;
        if(!(p!=nullptr && q!=nullptr && p->val == q->val))
            return false;
        bool retl = isSameTree(p->left,q->left);
        if(retl == false)
            return false;
        bool retr = isSameTree(p->right,q->right);
        if(retr == false)
            return false;
        return true;
    }
};

這是起初寫(xiě)的錯(cuò)誤解法，仔細(xì)想想還是容易理解的，34，不同，IsSameTree函數(shù)第二個(gè)if直接返回false，不會(huì)遞歸，然后進(jìn)入3函數(shù)的左子樹(shù)調(diào)用，仍然直接返回false，再走到3的右子樹(shù)，也是直接返回false。并沒(méi)有起到遞歸的作用。

小總結(jié)：

簡(jiǎn)單來(lái)說(shuō)就是遍歷了一遍，你可以直接把這個(gè)對(duì)結(jié)點(diǎn)的操作忽略掉，然后只看左遞歸和右遞歸，你就會(huì)發(fā)現(xiàn)，這兩個(gè)函數(shù)恰好遍歷了一遍整個(gè)樹(shù)，然后你可以在適當(dāng)?shù)奈恢脤?xiě)一些操作，就是對(duì)每個(gè)結(jié)點(diǎn)的操作，比如572這個(gè)題，就是比較兩個(gè)樹(shù)是否相等。

#include<iostream>
#include<assert.h>
#include<string>
using namespace std;
typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = new BTNode();
	assert(newnode);
	newnode->data = x;
	newnode->right = nullptr;
	newnode->left = nullptr;
	return newnode;
}
BTNode* CreateTree(string s, int* pi)
{
    if(s[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root = BuyNode(s[(*pi)++]);
    root->left = CreateTree(s, pi);
    root->right = CreateTree(s, pi);
    return root;
}
void InOrder(BTNode* root)
{
    if(root == NULL)
        return;
    InOrder(root->left);
    cout<<root->data<<" ";
    InOrder(root->right);
}
int main()
{
    string s;
    cin >> s;
    int i = 0;
    BTNode* root = CreateTree(s, &i);
    InOrder(root);
    return 0;
}

這個(gè)題相對(duì)而言就有點(diǎn)新穎了，創(chuàng)建正確的樹(shù)是關(guān)鍵。后面的中序遍歷就是一些基本操作了。

有關(guān)根據(jù)給定字符串創(chuàng)建合適的二叉樹(shù)：其實(shí)根本上還是一種前序遍歷的思路，可以直接把這個(gè)字符串看作一個(gè)正確的二叉樹(shù)，s和pi的結(jié)合可以逐個(gè)遍歷每個(gè)字符，每次進(jìn)入函數(shù)都會(huì)創(chuàng)建對(duì)應(yīng)的結(jié)點(diǎn)。而遇到#則返回空結(jié)點(diǎn)，作為上一個(gè)結(jié)點(diǎn)的左子樹(shù)或者右子樹(shù)，并同時(shí)結(jié)束遞歸。。。。。

銷(xiāo)毀二叉樹(shù)

void DestroyTree(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	// 后序銷(xiāo)毀，先銷(xiāo)毀左子樹(shù)，再銷(xiāo)毀右子樹(shù)，最后銷(xiāo)毀根節(jié)點(diǎn)，對(duì)于每一棵樹(shù)都是這樣的操作。
	DestroyTree(root->left);
	DestroyTree(root->right);
	delete root;
}

后序銷(xiāo)毀。。

層序遍歷

// 層序遍歷 利用隊(duì)列
void LevelOrder(BTNode* root)
{
	queue<BTNode*> q;
	if (root != NULL)
	{
		q.push(root);
	}
	while (!q.empty())
	{
		BTNode* root = q.front();
		cout << root->data << " ";
		q.pop();
		if (root->left)
		{
			q.push(root->left);
		}
		if (root->right)
		{
			q.push(root->right);
		}
	}
	cout << endl;
}

利用隊(duì)列，先將根節(jié)點(diǎn)插入隊(duì)列，然后出根節(jié)點(diǎn)，進(jìn)根節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)，當(dāng)然也有可能是一個(gè)個(gè)，也有可能只有一個(gè)根節(jié)點(diǎn)。每次都是出一個(gè)結(jié)點(diǎn)，進(jìn)這個(gè)結(jié)點(diǎn)的子節(jié)點(diǎn)。達(dá)到層序遍歷的目的。

利用層序遍歷判斷一顆二叉樹(shù)是否是完全二叉樹(shù)

bool BinaryTreeComplete(BTNode* root)
{
	queue<BTNode*> q;
	if (root != NULL)
	{
		q.push(root);
	}
	while (!q.empty())
	{
		BTNode* root = q.front();
		q.pop();
		if (root)
		{
			q.push(root->left);
			q.push(root->right);
		}
		else
		{
			break;
		}
	}
	while (!q.empty())
	{
		if (q.front() != NULL)
			return false;
		q.pop();
	}
	return true;
}

完全二叉樹(shù)的特點(diǎn)：層序遍歷后，前方遍歷的一定全是非空結(jié)點(diǎn)，后方一定全是空結(jié)點(diǎn)，利用這一特點(diǎn)進(jìn)行判斷。即：遇到空結(jié)點(diǎn)之后再判斷隊(duì)列中是否后續(xù)都是空結(jié)點(diǎn)。

到此這篇關(guān)于C語(yǔ)言進(jìn)階二叉樹(shù)的基礎(chǔ)與銷(xiāo)毀及層序遍歷詳解的文章就介紹到這了,更多相關(guān)C語(yǔ)言二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: