柚子快報邀請碼778899分享：算法 【數(shù)據(jù)結(jié)構(gòu)】二叉樹專題

http://yzkb.51969.com/

前言

本篇博客我們來看一些二叉樹的經(jīng)典題型，也是對上篇博客的補充

? 個人主頁：小張同學zkf

? 文章專欄：數(shù)據(jù)結(jié)構(gòu)

? ? ? 若有問題 評論區(qū)見?

?歡迎大家點贊?收藏?文章 ?

?

?

目錄

1.單值二叉樹

2.檢查兩棵樹是否相同

3.對稱二叉樹

?編輯?

4.二叉樹的前序遍歷

?5.另一棵樹的子樹

?

1.單值二叉樹

?

這道題有兩種思路，一種是最簡單的也是最常見的思路，遍歷，就是把每個節(jié)點遍歷一遍，看是否值相等（代碼過于簡單就不寫了），還有一種思路就是遞歸，通過遞歸，判斷孩子與父親是否相等，若相等進行下次遞歸，直到節(jié)點為空，就代表是單值二叉樹，我們寫下遞歸方式的代碼

代碼如下

2.檢查兩棵樹是否相同

?

?這道題我們可以讓兩顆子樹分別遍歷，直到雙方節(jié)點同時都為空，就相等若是一方節(jié)點先為空則兩棵樹不相等，若遍歷的同時值不相等，那兩棵樹也不相等，代碼如下

3.對稱二叉樹

?

?

?這個對稱二叉樹就判斷左子樹與右子樹是否相等就行了，也就是說把根節(jié)點的左右子樹放到上面那道題函數(shù)里判斷就行了

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

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;

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

}

bool isSymmetric(struct TreeNode* root) {

return isSameTree(root->left,root->right);

}

注意一下，這里要看左子樹與右子樹比較是否相等?，所以傳參的時候注意下

4.二叉樹的前序遍歷

?

前序遍歷我們上篇博客說過，但是這個前序遍歷將所有根節(jié)點的數(shù)據(jù)，存儲到數(shù)組中，以數(shù)組的形式返回，我們先開辟一個動態(tài)數(shù)組的空間，?將數(shù)組首地址與首下表，傳入函數(shù)中，創(chuàng)建前序遍歷函數(shù)，不過在此之前要統(tǒng)計一下二叉樹的節(jié)點個數(shù)，得到數(shù)組里數(shù)據(jù)個數(shù)，然后通過遞歸將每個數(shù)據(jù)放入數(shù)組中，記得下標自增

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

int number(struct TreeNode* root)

{

return root==NULL?0:number(root->left)+number(root->right)+1;

}

void preorder(struct TreeNode* root,int* a,int* pi)

{

if(root==NULL)

return;

a[(*pi)++]=root->val;

preorder(root->left,a,pi);

preorder(root->right,a,pi);

}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {

*returnSize=number(root);

int* a=(int *)malloc(sizeof(int)*(*returnSize));

int i=0;

preorder(root,a,&i);

return a;

}

中序后序亦是如此

?5.另一棵樹的子樹

相當于直接通過前序遍歷把所有子樹找到，然后依次導入我們上邊說的判斷兩棵樹是否相等的函數(shù)里就行了 ，前提倆子樹數(shù)據(jù)相等

代碼如下

結(jié)束語?

典型的二叉樹有關(guān)習題總結(jié)完了，二叉樹主要是遍歷，要想判斷二叉樹里什么什么的可能都得需要遍歷，遍歷那肯定需要遞歸，所以遞歸一定要弄明白

OK，本篇博客結(jié)束，感謝觀看?。?！

?

柚子快報邀請碼778899分享：算法 【數(shù)據(jù)結(jié)構(gòu)】二叉樹專題

http://yzkb.51969.com/

相關(guān)文章