各位CSDN的uu們你們好呀，今天小雅蘭的內(nèi)容仍然是二叉樹和Leetcode每日一題，下面，就讓我們進(jìn)入二叉樹的世界吧！??！
這個(gè)題目需要重新定義一個(gè)函數(shù)，函數(shù)參數(shù)需要有左子樹和右子樹，題目所給定的函數(shù)無法解決問題。
bool _isSymmetric(struct TreeNode* leftRoot,struct TreeNode* rightRoot) { //左子樹和右子樹同時(shí)為空 if(leftRoot==NULL&&rightRoot==NULL) { return true; } //一棵樹為空，另一棵樹不為空 if((leftRoot==NULL&&rightRoot!=NULL)|| (leftRoot!=NULL&&rightRoot==NULL)) { return false; } //左子樹的根和右子樹的根不相等 //這就必然不對稱 if(leftRoot->val!=rightRoot->val) { return false; } return _isSymmetric(leftRoot->left,rightRoot->right)&& _isSymmetric(leftRoot->right,rightRoot->left); } bool isSymmetric(struct TreeNode* root){ return _isSymmetric(root->left,root->right); }
每個(gè)不為空的結(jié)點(diǎn)，都可以認(rèn)為是一棵子樹的根?
//兩棵樹相同 bool isSameTree(struct TreeNode* p, struct TreeNode* q){ //兩個(gè)都為空 if(p==NULL&&q==NULL) { return true; } //一個(gè)為空，另一個(gè)不為空 if((p==NULL&&q!=NULL)||(p!=NULL&&q==NULL)) { return false; } //根不相等 if(p->val!=q->val) { return false; } return isSameTree(p->left,q->left) &&isSameTree(p->right,q->right); } bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){ if(root==NULL) { return false; } //root和subRoot相同 if(isSameTree(root,subRoot)) { return true; } //root的左子樹與subRoot有相同或者root的右子樹與subRoot有相同 //滿足其中一個(gè)條件即可，所以用|| return isSubtree(root->left,subRoot)|| isSubtree(root->right,subRoot); }?
遞歸里面?zhèn)鲾?shù)組下標(biāo)要注意?。。?/strong>
每個(gè)棧幀里面都有一個(gè)數(shù)組下標(biāo)?。?！?
所以要傳數(shù)組下標(biāo)的地址。
int TreeSize(struct TreeNode* root) { return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1; } //遞歸里面?zhèn)鲾?shù)組下標(biāo)要注意！?。?//每個(gè)棧幀里面都有一個(gè)i 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){ //root是輸入型參數(shù)，returnSize是返回型參數(shù) *returnSize=TreeSize(root); int* a=(int*)malloc(*returnSize*sizeof(int)); int i=0; preorder(root,a,&i); return a; }?
當(dāng)然，這個(gè)題目還有另外一種解法，就是把i作為全局變量，但是這樣要特別注意，稍有不慎就會(huì)出錯(cuò)
int?TreeSize(struct?TreeNode*?root)
{
????return?root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
//遞歸里面?zhèn)鲾?shù)組下標(biāo)要注意?。。?/strong>
//每個(gè)棧幀里面都有一個(gè)i
int?i=0;
void?preorder(struct?TreeNode*?root,int*?a)
{
????if(root==NULL)
????{
????????return;
????}
????a[i++]=root->val;
????preorder(root->left,a);
????preorder(root->right,a);
}
int*?preorderTraversal(struct?TreeNode*?root,?int*?returnSize){
????//root是輸入型參數(shù)，returnSize是返回型參數(shù)
????*returnSize=TreeSize(root);
????int*?a=(int*)malloc(*returnSize*sizeof(int));
????i=0;
????preorder(root,a);
????return?a;
}
int?TreeSize(struct?TreeNode*?root)
{
????return?root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
void?inorder(struct?TreeNode*?root,int*?a,int*?pi)
{
????if(root==NULL)
????{
????????return;
????}
????inorder(root->left,a,pi);
????a[(*pi)++]=root->val;
????inorder(root->right,a,pi);
}
int*?inorderTraversal(struct?TreeNode*?root,?int*?returnSize){
????//root是輸入型參數(shù)，returnSize是返回型參數(shù)
????*returnSize=TreeSize(root);
????int*?a=(int*)malloc(*returnSize*sizeof(int));
????int?i=0;
????inorder(root,a,&i);
????return?a;
}
int?TreeSize(struct?TreeNode*?root)
{
????return?root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
void?postorder(struct?TreeNode*?root,int*?a,int*?pi)
{
????if(root==NULL)
????{
????????return;
????}
????postorder(root->left,a,pi);
????postorder(root->right,a,pi);
?????a[(*pi)++]=root->val;
}
int*?postorderTraversal(struct?TreeNode*?root,?int*?returnSize){
????//root是輸入型參數(shù)，returnSize是返回型參數(shù)
????*returnSize=TreeSize(root);
????int*?a=(int*)malloc(*returnSize*sizeof(int));
????int?i=0;
????postorder(root,a,&i);
????return?a;
}
?
層序遍歷
除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進(jìn)行層序遍歷。設(shè)二叉樹的根節(jié)點(diǎn)所在層數(shù)為1，層序遍歷就是從所在二叉樹的根節(jié)點(diǎn)出發(fā)，首先訪問第一層的樹根節(jié)點(diǎn)，然后從左到右訪問第2層 上的節(jié)點(diǎn)，接著是第三層的節(jié)點(diǎn)，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點(diǎn)的過程就是層序遍歷。
?
1出來帶2和4，2出來帶3和NULL，4出來帶和6?
寫這個(gè)代碼的核心是得有一個(gè)隊(duì)列?。。?/strong>
Queue.h的內(nèi)容：
#pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> typedef struct BinaryTreeNode* QDataType; // 鏈?zhǔn)浇Y(jié)構(gòu)：表示隊(duì)列 typedef struct QueueNode { struct QueueNode* next; QDataType data; }QueueNode; // 隊(duì)列的結(jié)構(gòu) typedef struct Queue { QueueNode* phead;//頭指針 QueueNode* ptail;//尾指針 int size; }Queue; // 初始化隊(duì)列 void QueueInit(Queue* pq); // 銷毀隊(duì)列 void QueueDestroy(Queue* pq); // 隊(duì)尾入隊(duì)列 void QueuePush(Queue* pq, QDataType x); // 隊(duì)頭出隊(duì)列 void QueuePop(Queue* pq); // 獲取隊(duì)列頭部元素 QDataType QueueFront(Queue* pq); // 獲取隊(duì)列隊(duì)尾元素 QDataType QueueBack(Queue* pq); // 獲取隊(duì)列中有效元素個(gè)數(shù) int QueueSize(Queue* pq); // 檢測隊(duì)列是否為空 bool QueueEmpty(Queue* pq);Queue.c的內(nèi)容：
#include"Queue.h" // 初始化隊(duì)列 void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; } // 銷毀隊(duì)列 void QueueDestroy(Queue* pq) { assert(pq); QueueNode* cur = pq->phead; while (cur != NULL) { QueueNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } // 隊(duì)尾入隊(duì)列 void QueuePush(Queue* pq, QDataType x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; //是空隊(duì)列的情況 if (pq->ptail == NULL) { assert(pq->phead == NULL); pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } // 檢測隊(duì)列是否為空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL && pq->ptail == NULL; } // 隊(duì)頭出隊(duì)列 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); //1.一個(gè)結(jié)點(diǎn) //2.多個(gè)結(jié)點(diǎn) if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { //相當(dāng)于頭刪 QueueNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } // 獲取隊(duì)列頭部元素 QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->phead->data; } // 獲取隊(duì)列隊(duì)尾元素 QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->data; } // 獲取隊(duì)列中有效元素個(gè)數(shù) int QueueSize(Queue* pq) { assert(pq); return pq->size; }
層序遍歷源代碼：
//層序遍歷 void LevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root != NULL) { QueuePush(&q, root); } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); printf("%d ", front->data); if (front->left != NULL) { QueuePush(&q, front->left); } if (front->right != NULL) { QueuePush(&q, front->right); } } printf("\n"); QueueDestroy(&q); }
二叉樹銷毀
//二叉樹銷毀 void BTreeDestroy(BTNode* root) { if (root == NULL) { return; } BTreeDestroy(root->left); BTreeDestroy(root->right); free(root); }
通 過 前 序 遍 歷 的 數(shù) 組 " A B D # # E # H # # C F # # G # # " 構(gòu) 建 二 叉 樹
根? ? ? ? 左子樹? ? ? ? 右子樹
#include <stdio.h> #include<stdlib.h> typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode* BuyNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { perror("malloc fail"); return NULL; } node->data = x; node->left = NULL; node->right = NULL; return node; } BTNode* CreatTree(char* a,int* pi) { if(a[*pi]=='#') { (*pi)++; return NULL; } BTNode* root=BuyNode(a[*pi]); (*pi)++; root->left=CreatTree(a,pi); root->right=CreatTree(a,pi); return root; } //中序 void InOrder(BTNode* root) { if (root == NULL) { return; } InOrder(root->left); printf("%c ", root->data); InOrder(root->right); } int main() { char a[100]; scanf("%s",a); int i=0; BTNode*root=CreatTree(a,&i); InOrder(root); printf("\n"); return 0; }?
?
判斷二叉樹是否是完全二叉樹
完全二叉樹的特征是：層序遍歷去走，它是連續(xù)的?。?！
1出來帶2和4，2出來帶3和NULL，4出來帶5和6，3出來帶NULL和NULL，但是，3后面的NULL的后面竟然還有非空，這就證明此樹是一棵非完全二叉樹。
1出來帶2和4，2出來帶3和7，4出來帶5和6，3出來帶8和NULL，7出來帶NULL和NULL，5出來帶NULL和NULL，6出來帶NULL和NULL，8出來帶NULL和NULL，也就是說，隊(duì)列里面的全都是空了，這一定是一棵完全二叉樹。
//判斷二叉樹是否是完全二叉樹 bool BTreeComplete(BTNode* root) { Queue q; QueueInit(&q); if (root != NULL) { QueuePush(&q, root); } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); //遇到空就跳出循環(huán) if (front == NULL) { break; } QueuePush(&q, front->left); QueuePush(&q, front->right); } //檢查后面的結(jié)點(diǎn)有沒有非空 //有非空，就不是完全二叉樹 while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); if (front != NULL) { QueueDestroy(&q); return false; } } QueueDestroy(&q); return true; }
1.某完全二叉樹按層次輸出（同一層從左到右）的序列為 ABCDEFGH 。該完全二叉樹的前序序列為（ A ）
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA
2.二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK;中序遍歷：HFIEJKG.則二叉樹根結(jié)點(diǎn)為（ A ）
A E
B F
C G
D H
此題與中序遍歷無關(guān)（中序遍歷是迷惑人的），光看先序遍歷就可以看出來，先序遍歷就是根? ? ? ? 左子樹? ? ? ? 右子樹，所以E就是根結(jié)點(diǎn)。
但如果是想還原出這棵二叉樹，中序遍歷就很重要啦！??！
3.設(shè)一棵二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹前序遍歷序列為（ D ）。
A adbce
B decab
C debac
D abcde
后序遍歷序列最后一個(gè)是a,所以a就是根節(jié)點(diǎn)！??！
4.某二叉樹的后序遍歷序列與中序遍歷序列相同，均為 ABCDEF ，則按層次輸出（同一層從左到右）的序列為（ A ）
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF
二叉樹的性質(zhì)
整個(gè)二叉樹的源代碼：
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"Queue.h"
typedef int BTDataType;
typedef struct BinaryTreeNode
{
?? ?BTDataType data;
?? ?struct BinaryTreeNode* left;
?? ?struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{
?? ?BTNode* node = (BTNode*)malloc(sizeof(BTNode));
?? ?if (node == NULL)
?? ?{
?? ??? ?perror("malloc fail");
?? ??? ?return NULL;
?? ?}
?? ?node->data = x;
?? ?node->left = NULL;
?? ?node->right = NULL;
?? ?return node;
}BTNode* CreatBinaryTree()
{
?? ?BTNode* node1 = BuyNode(1);
?? ?BTNode* node2 = BuyNode(2);
?? ?BTNode* node3 = BuyNode(3);
?? ?BTNode* node4 = BuyNode(4);
?? ?BTNode* node5 = BuyNode(5);
?? ?BTNode* node6 = BuyNode(6);?? ?node1->left = node2;
?? ?node1->right = node4;
?? ?node2->left = node3;
?? ?node4->left = node5;
?? ?node4->right = node6;
?? ?return node1;
}//前序
void PrevOrder(BTNode* root)
{
?? ?if (root == NULL)
?? ?{
?? ??? ?printf("NULL ");
?? ??? ?return;
?? ?}
?? ?printf("%d ", root->data);
?? ?PrevOrder(root->left);
?? ?PrevOrder(root->right);
}//中序
void InOrder(BTNode* root)
{
?? ?if (root == NULL)
?? ?{
?? ??? ?printf("NULL ");
?? ??? ?return;
?? ?}
?? ?InOrder(root->left);
?? ?printf("%d ", root->data);
?? ?InOrder(root->right);
}//后序
void PostOrder(BTNode* root)
{
?? ?if (root == NULL)
?? ?{
?? ??? ?printf("NULL ");
?? ??? ?return;
?? ?}
?? ?PostOrder(root->left);
?? ?PostOrder(root->right);
?? ?printf("%d ", root->data);
}
?二叉樹結(jié)點(diǎn)個(gè)數(shù)
//int size = 0;//全局變量
//int BTreeSize(BTNode* root)
//{
//?? ?if (root == NULL)
//?? ?{
//?? ??? ?return;
//?? ?}
//?? ?else
//?? ?{
//?? ??? ?++size;
//?? ?}
//?? ?BTreeSize(root->left);
//?? ?BTreeSize(root->right);
//}
二叉樹結(jié)點(diǎn)個(gè)數(shù)
//int BTreeSize(BTNode* root)
//{
//?? ?if (root == NULL)
//?? ?{
//?? ??? ?return 0;
//?? ?}
//?? ?else
//?? ?{
//?? ??? ?return BTreeSize(root->left) + BTreeSize(root->right) + 1;
//?? ?}
//}
//二叉樹結(jié)點(diǎn)個(gè)數(shù)
int BTreeSize(BTNode* root)
{
?? ?return root == NULL ? 0 : BTreeSize(root->left) + BTreeSize(root->right) + 1;
}
//求葉子結(jié)點(diǎn)的個(gè)數(shù)
int BTreeleafSize(BTNode* root)
{
?? ?if (root == NULL)
?? ?{
?? ??? ?return 0;
?? ?}
?? ?if (root->left == NULL && root->right == NULL)
?? ?{
?? ??? ?return 1;
?? ?}
?? ?return BTreeleafSize(root->left) + BTreeleafSize(root->right);
}//求二叉樹的高度
int BTreeHeight(BTNode* root)
{
?? ?if (root == NULL)
?? ?{
?? ??? ?return 0;
?? ?}
?? ?else
?? ?{
?? ??? ?int leftHeight = BTreeHeight(root->left);
?? ??? ?int rightHeight = BTreeHeight(root->right);
?? ??? ?return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
?? ?}
}
// 二叉樹第k層節(jié)點(diǎn)個(gè)數(shù)
int BTreeLevelKSize(BTNode* root, int k)
{
?? ?assert(k > 0);
?? ?if (root == NULL)//無論k是多少
?? ?{
?? ??? ?return 0;
?? ?}
?? ?//root一定不為空
?? ?if (k == 1)
?? ?{
?? ??? ?return 1;
?? ?}
?? ?//root不為空并且k不為1
?? ?return BTreeLevelKSize(root->left, k - 1) + BTreeLevelKSize(root->right, k - 1);
}
// 二叉樹查找值為x的節(jié)點(diǎn)
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
?? ?if (root == NULL)
?? ?{
?? ??? ?return NULL;
?? ?}
?? ?if (root->data == x)
?? ?{
?? ??? ?return root;
?? ?}
?? ?BTNode* ret1 = BTreeFind(root->left, x);
?? ?if (ret1)
?? ?{
?? ??? ?return ret1;
?? ?}
?? ?BTNode* ret2 = BTreeFind(root->right, x);
?? ?if (ret2)
?? ?{
?? ??? ?return ret2;
?? ?}
?? ?return NULL;
}
//層序遍歷
void LevelOrder(BTNode* root)
{
?? ?Queue q;
?? ?QueueInit(&q);
?? ?if (root != NULL)
?? ?{
?? ??? ?QueuePush(&q, root);
?? ?}
?? ?while (!QueueEmpty(&q))
?? ?{
?? ??? ?BTNode* front = QueueFront(&q);
?? ??? ?QueuePop(&q);
?? ??? ?printf("%d ", front->data);
?? ??? ?if (front->left != NULL)
?? ??? ?{
?? ??? ??? ?QueuePush(&q, front->left);
?? ??? ?}
?? ??? ?if (front->right != NULL)
?? ??? ?{
?? ??? ??? ?QueuePush(&q, front->right);
?? ??? ?}
?? ?}
?? ?printf("\n");
?? ?QueueDestroy(&q);
}
//二叉樹銷毀
void BTreeDestroy(BTNode* root)
{
?? ?if (root == NULL)
?? ?{
?? ??? ?return;
?? ?}
?? ?BTreeDestroy(root->left);
?? ?BTreeDestroy(root->right);
?? ?free(root);
}
//判斷二叉樹是否是完全二叉樹
bool BTreeComplete(BTNode* root)
{
?? ?Queue q;
?? ?QueueInit(&q);
?? ?if (root != NULL)
?? ?{
?? ??? ?QueuePush(&q, root);
?? ?}
?? ?while (!QueueEmpty(&q))
?? ?{
?? ??? ?BTNode* front = QueueFront(&q);
?? ??? ?QueuePop(&q);
?? ??? ?//遇到空就跳出循環(huán)
?? ??? ?if (front == NULL)
?? ??? ?{
?? ??? ??? ?break;
?? ??? ?}
?? ??? ?QueuePush(&q, front->left);
?? ??? ?QueuePush(&q, front->right);
?? ?}
?? ?//檢查后面的結(jié)點(diǎn)有沒有非空
?? ?//有非空，就不是完全二叉樹
?? ?while (!QueueEmpty(&q))
?? ?{
?? ??? ?BTNode* front = QueueFront(&q);
?? ??? ?QueuePop(&q);
?? ??? ?if (front != NULL)
?? ??? ?{
?? ??? ??? ?QueueDestroy(&q);
?? ??? ??? ?return false;
?? ??? ?}
?? ?}
?? ?QueueDestroy(&q);
?? ?return true;
}int main()
{
?? ?BTNode* root = CreatBinaryTree();
?? ?PrevOrder(root);
?? ?printf("\n");?? ?InOrder(root);
?? ?printf("\n");?? ?PostOrder(root);
?? ?printf("\n");?? ?/*BTreeSize(root);
?? ?printf("BTreeSize:%d\n", size);?? ?size = 0;
?? ?BTreeSize(root);
?? ?printf("BTreeSize:%d\n", size);?? ?size = 0;
?? ?BTreeSize(root);
?? ?printf("BTreeSize:%d\n", size);*/?? ?printf("BTreeSize:%d\n",BTreeSize(root));
?? ?printf("BTreeleafSize:%d\n", BTreeleafSize(root));
?? ?printf("BTreeHeight:%d\n", BTreeHeight(root));
?? ?printf("BTreeLevelKSize:%d\n", BTreeLevelKSize(root, 3));
?? ?printf("BTreeFind:%p\n", BTreeFind(root, 3));
?? ?LevelOrder(root);
?? ?BTreeDestroy(root);
?? ?root = NULL;?? ?return 0;
}
?
好啦，小雅蘭的今日分享就到這里啦，還要繼續(xù)加油學(xué)習(xí)噢?。?！文章來源：http://www.zghlxwxcb.cn/news/detail-576841.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-576841.html
到了這里，關(guān)于二叉樹（下）+Leetcode每日一題——“數(shù)據(jù)結(jié)構(gòu)與算法”“對稱二叉樹”“另一棵樹的子樹”“二叉樹的前中后序遍歷”的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
