目錄

單值二叉樹?

相同的樹?

另一棵樹的子樹

二叉樹的前序遍歷

?二叉樹的構(gòu)造及遍歷

給大家推薦一款刷題，找工作的好網(wǎng)站——?？途W(wǎng)

?？途W(wǎng) - 找工作神器|筆試題庫(kù)|面試經(jīng)驗(yàn)|實(shí)習(xí)招聘內(nèi)推，求職就業(yè)一站解決_?？途W(wǎng)

?

單值二叉樹?

思路：根節(jié)點(diǎn)跟左子樹比較，若相等則繼續(xù)比，一值比到左子樹為空，比完之后再跟右子樹比較

bool isUnivalTree(struct TreeNode* root){
 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;
 return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

相同的樹?

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p==NULL&&q==NULL)
    return true; //如果都為空則返回真
    if(p==NULL||q==NULL)
    return false; //一個(gè)為空，一個(gè)不為空，則false
    if(p->val!=q->val)
    return false;//不相等，fasle
    return isSameTree(p->left,q->left)&&isSameTree(q->right,p->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->left)&&isSameTree(q->right,p->right);

}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
 if(root==NULL)
 return false;
 if(isSameTree(root,subRoot))
 return true;
 return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

二叉樹的前序遍歷

思路：1.先統(tǒng)計(jì)出該二叉樹節(jié)點(diǎn)的個(gè)數(shù)

? ? ? ? ? ? 2.創(chuàng)建一個(gè)新的數(shù)組，數(shù)組大小為二叉樹總結(jié)點(diǎn)大小

? ? ? ? ? ? 3.進(jìn)行前序遍歷根，左，右

int TreeSize(struct TreeNode* root)
{
    if(root==NULL)
    return 0;
    return TreeSize(root->left)+TreeSize(root->right)+1;
} //統(tǒng)計(jì)個(gè)數(shù)
 void preorder(struct TreeNode* root,int *a,int *pi)
 {
     if(root==NULL)
     return;
    a[*pi]=root->val;
    (*pi)++;
    preorder(root->left,a,pi);
     preorder(root->right,a,pi);
 }//遍歷
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize){
 int n=TreeSize(root);
 int *a=(int*)malloc(sizeof(int)*n);
 int i=0;
 preorder(root,a,&i);
 *returnSize=n;
 return a;
}

?二叉樹的構(gòu)造及遍歷

?二叉樹遍歷_?？皖}霸_牛客網(wǎng) (nowcoder.com)

1.建立一個(gè)數(shù)組，給數(shù)組輸入數(shù)據(jù)，#代表NULL

2.構(gòu)建一個(gè)二叉樹，把數(shù)組的值輸按前序遍歷輸入到二叉樹中，當(dāng)遇到#時(shí)，代表該節(jié)點(diǎn)為空

3.將前序遍歷好的二叉樹，進(jìn)行中序遍歷

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-515207.html

#include<stdio.h>
#include<stdlib.h>
typedef char Datatypedef;
typedef struct BinaryTreeNode
{
    Datatypedef data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}TreeNode;//定義二叉樹

TreeNode* CreateTree(char* arr, int* pi)
{
    if (arr[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    TreeNode* tmp = (TreeNode*)malloc(sizeof(TreeNode));
    tmp->data = arr[*pi];
    (*pi)++;
    tmp->left = CreateTree(arr, pi);
    tmp->right = CreateTree(arr, pi);
    return tmp;
}//創(chuàng)建二叉樹，并把數(shù)組的值賦值給二叉樹，按前序遍歷賦值

void InorDer(TreeNode* tmp)
{
    if (tmp == NULL)
        return;
    InorDer(tmp->left);
    printf("%c ", tmp->data);

    InorDer(tmp->right);
}//前序遍歷換為中序遍歷

int main()
{
    char arr[100];
    scanf("%s", arr);
    int i = 0;
    TreeNode* root = CreateTree(arr, &i);
    InorDer(root);
    return 0;
}

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——二叉樹練習(xí)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！