《數(shù)據(jù)結(jié)構(gòu)專(zhuān)欄》

一、認(rèn)識(shí)樹(shù)結(jié)構(gòu)

樹(shù)的定義：樹(shù)是指由N（N>=0）個(gè)有限結(jié)點(diǎn)組成的具有層次性關(guān)系的集合，是一種簡(jiǎn)單的非線性結(jié)構(gòu)。當(dāng)N=0時(shí)，稱(chēng)為空樹(shù)。

如何遍歷樹(shù)

前序遍歷

中序遍歷

后序遍歷

對(duì)于前中后序遍歷使用的是根節(jié)點(diǎn)的位置決定前中序。

層序遍歷

對(duì)于層序來(lái)說(shuō)就是一層一層的進(jìn)行遍歷，由上面一層的根節(jié)遍歷后帶入下一層的節(jié)點(diǎn)數(shù)據(jù)?？梢允褂靡粋€(gè)輔助隊(duì)列的容器來(lái)實(shí)現(xiàn)對(duì)于層序遍歷。

代碼實(shí)現(xiàn)

//層序遍歷
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue qu;
	BTNode* cur;

	QueueInit(&qu);

	QueuePush(&qu, root);

	while (! QueueEmpty(&qu))
	{
		cur = QueueFront(&qu);

		putchar(cur->_data);

		if (cur->_left)
		{
			QueuePush(&qu, cur->_left);
		}

		if (cur->_right)
		{
			QueuePush(&qu, cur->_right);
		}

		QueuePop(&qu);
	}

	QueueDestory(&qu);
}

如何創(chuàng)建一個(gè)樹(shù)？

對(duì)于二叉樹(shù)的遍歷就是前、中、后序遍歷。對(duì)于前序和后序遍歷可以快速的找到根節(jié)點(diǎn)。然后通過(guò)中序分辨出左右子樹(shù)。實(shí)現(xiàn)對(duì)于樹(shù)的構(gòu)建。

編一個(gè)程序，讀入用戶輸入的一串先序遍歷字符串，根據(jù)此字符串建立一個(gè)二叉樹(shù)（以指針?lè)绞酱鎯?chǔ)）。 例如如下的先序遍歷字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空樹(shù)。建立起此二叉樹(shù)以后，再對(duì)二叉樹(shù)進(jìn)行中序遍歷，輸出遍歷結(jié)果。
輸入：abc ## de #g ## f ###
輸出：c b e g d f a

構(gòu)建樹(shù)

輸入時(shí)是一個(gè)數(shù)組來(lái)進(jìn)行數(shù)據(jù)存儲(chǔ)的，所以在建立樹(shù)的節(jié)點(diǎn)時(shí)就需要使用一個(gè)數(shù)據(jù)記錄數(shù)組下標(biāo)。

避免在遞歸時(shí)數(shù)組的下標(biāo)使用后，返回下標(biāo)重置，這里需要保持?jǐn)?shù)組下標(biāo)一致向后走，遞歸出來(lái)后才會(huì)對(duì)于整個(gè)數(shù)組遍歷。使用的一個(gè)前序思想建樹(shù)。

typedef  struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char val;
}TreeNode;

TreeNode* makeTree(char* arr,int *count)
{
    if(arr[*count]=='#'||arr[*count]==' ')
    {
        return NULL;
    }

    TreeNode* newnode=(TreeNode*)malloc(sizeof(TreeNode));
    newnode->val=arr[(*count)++];

    newnode->left=makeTree(arr, count);
    (*count)++;
    newnode->right=makeTree(arr, count);

    return newnode;
}

void InOrder(TreeNode*root)
{
    if(root==NULL)
    return ;

    InOrder(root->left);
    printf("%c ",root->val);
    InOrder(root->right);
}

int main()
{

    char arr[101];
    scanf("%s",arr);
    int count=0;
    TreeNode*tree=makeTree(arr, &count);
    InOrder(tree);
    return 0;
}

如何判斷一顆樹(shù)是否是完全二叉樹(shù)？

通過(guò)對(duì)于滿二叉樹(shù)和完全二叉樹(shù)的對(duì)比發(fā)現(xiàn)完全二叉樹(shù)的底層葉子結(jié)點(diǎn)數(shù)目是從左向右依次遞減的，所以高度為n-1層的數(shù)目是不變的滿二叉樹(shù)一樣，對(duì)于完全二叉樹(shù)的最后一層進(jìn)行分析即可。

對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從0開(kāi)始編號(hào)，則對(duì)
于序號(hào)為i的結(jié)點(diǎn)有：

1. 若i>0，i位置節(jié)點(diǎn)的雙親序號(hào)：(i-1)/2；i=0，i為根節(jié)點(diǎn)編號(hào)，無(wú)雙親節(jié)點(diǎn)
2. 若2i+1<n，左孩子序號(hào)：2i+1，2i+1>=n否則無(wú)左孩子
3. 若2i+2<n，右孩子序號(hào)：2i+2，2i+2>=n否則無(wú)右孩子

代碼實(shí)現(xiàn)

int BinaryTreeComplete(BTNode* root)
{
	Queue qu;
	BTNode* cur;
	int tag = 0;

	QueueInit(&qu);

	QueuePush(&qu, root);

	while (! QueueEmpty(&qu))
	{
		cur = QueueFront(&qu);

		putchar(cur->_data);

		if (cur->_right && !cur->_left)
		{
			return 0;
		}

		if (tag && (cur->_right || cur->_left))
		{
			return 0;
		}

		if (cur->_left)
		{
			QueuePush(&qu, cur->_left);
		}

		if (cur->_right)
		{
			QueuePush(&qu, cur->_right);
		}
		else
		{
			tag = 1;
		}

		QueuePop(&qu);
	}

	BinaryTreeDestory(&qu);
	return 1;
}

二、樹(shù)的簡(jiǎn)單算法——遞歸

1.相同樹(shù)

給你兩棵二叉樹(shù)的根節(jié)點(diǎn) p 和 q ，編寫(xiě)一個(gè)函數(shù)來(lái)檢驗(yàn)這兩棵樹(shù)是否相同。 如果兩個(gè)樹(shù)在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的

對(duì)于題目講解的相同理解應(yīng)該是節(jié)點(diǎn)數(shù)據(jù)相同的數(shù)據(jù)，且左右子樹(shù)結(jié)構(gòu)也是相同的，對(duì)于空樹(shù)的判斷應(yīng)該也要討論，其中一顆樹(shù)為空，另外一顆樹(shù)不為空就明顯不是相同的數(shù)。對(duì)于判斷條件就是val值，左右子樹(shù)結(jié)構(gòu)，是否同時(shí)為空（判斷是否都是葉子結(jié)點(diǎn)）。

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==nullptr&&q==nullptr)return true;
        
        if(p==nullptr||q==nullptr)return false;

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


        return isSameTree(q->left,p->left)&&isSameTree(q->right,p->right);
    }
};

2.鏡像樹(shù)

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

鏡像樹(shù)和解法有些類(lèi)似于上面的相同樹(shù)，但是又有些許差別就是對(duì)于樹(shù)的結(jié)構(gòu)比較他們是左子樹(shù)和右子樹(shù)的是對(duì)稱(chēng)的，使用的相同樹(shù)的邏輯解題。

class Solution {
public:
    bool issametree(TreeNode* root,TreeNode* subroot)
    {
        if(root==nullptr && subroot==nullptr)
        {
            return true;
        }
        if(root==nullptr || subroot==nullptr)
        {
            return false;
        }
         
        if(root->val==subroot->val)
        {
            return issametree(root->left,subroot->right) && issametree(root->right,subroot->left);
        }
        else
        {
            return false;
        }
    }
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr) return true;
        return issametree(root->left,root->right);
    }
};

3.單值二叉樹(shù)

題目： 如果二叉樹(shù)每個(gè)節(jié)點(diǎn)都具有相同的值，那么該二叉樹(shù)就是單值二叉樹(shù)。 只有給定的樹(shù)是單值二叉樹(shù)時(shí)，才返回 true；否則返回 false。

對(duì)于二叉樹(shù)中值的查找值是一個(gè)比較常用的算法，使用深度遍歷，從左子樹(shù)到后面右子樹(shù)依次遍歷。不能使用節(jié)點(diǎn)數(shù)據(jù)相加后對(duì)比左右子樹(shù)。會(huì)存在左邊是多節(jié)點(diǎn)，右邊只有一個(gè)節(jié)點(diǎn)數(shù)據(jù)。但是左右子樹(shù)的值依舊相等。所以需要從根得va來(lái)比較判斷左右子樹(shù)。

class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        if(root==nullptr)return true;

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

總結(jié)

樹(shù)的結(jié)構(gòu)使用遞歸算法來(lái)進(jìn)行遍歷很容易理解，但是對(duì)于深度太深的樹(shù)就會(huì)出現(xiàn)棧溢出情況。樹(shù)用來(lái)存儲(chǔ)數(shù)據(jù)顯然不是一個(gè)很好的選擇，容易出現(xiàn)歪脖子樹(shù)，單只樹(shù)。效率不高。可以進(jìn)行后期優(yōu)化成為搜索二叉樹(shù)，AVL樹(shù)……文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-451851.html

到了這里，關(guān)于這是關(guān)于“樹(shù)先生“的故事的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！