二叉樹的結構定義：

typedef struct BiNode {TElemType data;struct BiNode *lchild;struct BiNode *rchild; }BiNode,*BiTree;

這里包含的遞歸算法有：

二叉樹的先序創建；

二叉樹的先序中序后序遍歷；

二叉樹的銷毀算法；

雙序遍歷；

求結點的個數；

求結點值的和；

求樹的深度；

求葉子結點的個數；

求單分支結點的個數；

交換結點的左右子樹；

尋找最小值結點；

判斷是否是相同的二叉樹；

判斷是否是平衡二叉樹；

判斷是對稱二叉樹；

二叉樹的最小深度算法
查看之前的博文
二叉樹的最小深度

二叉樹的層次遍歷
查看之前的博文
二叉樹的層次遍歷
二叉樹的層次遍歷進階

二叉樹的最長路徑
查看之前的博文
二叉樹的最長路徑問題

從葉子結點到根節點的全部路徑
查看之前的博文
從葉子結點到根節點的全部路徑

最底面有全部代碼的合集：
1 二叉樹的先序創建
思路：
和先序遞歸遍歷差不多，二叉樹中每個結點的元素均為一個字符，按先序遍歷的順序建立二叉鏈表。（序列中元素為‘#’時，表示該結點為空）。

void CreateBiTree(BiTree &T)//二叉樹的先序創建 {TElemType ch;scanf("%c",&ch);if(ch=='#')T=NULL;else {T=(BiNode*)malloc(sizeof(BiNode));if(!T)exit(-1);T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);} }

2二叉樹的先序中序后序遍歷
思路：
先序中序后序遞歸算法都類似

int preorderTraverse(BiTree T)//二叉樹的先序遞歸遍歷算法 {if(T==NULL)return 0;else {printf("%c ",T->data);preorderTraverse(T->lchild);preorderTraverse(T->rchild);}} int InorderTraverse(BiTree T)//二叉樹的中序遞歸遍歷算法 {if(T==NULL)return 0;else {InorderTraverse(T->lchild);printf("%c ",T->data);InorderTraverse(T->rchild);}}int PostorderTraverse(BiTree T)//二叉樹的后序遞歸遍歷算法 {if(T==NULL)return 0;else {PostorderTraverse(T->lchild);PostorderTraverse(T->rchild);printf("%c ",T->data);}}

3二叉樹的銷毀算法
思路：
和后序遞歸算法類似

void DestroyBiTree(BiTree &T)//二叉樹的銷毀算法 {if(T==NULL)exit(-1);else{DestroyBiTree(T->lchild);DestroyBiTree(T->rchild);free(T);} }

4雙序遍歷
思路：和普通前序中序遍歷類似

void double_preorderTraverse(BiTree T)//雙序遍歷 {if(T!=NULL){printf("%c ",T->data);double_preorderTraverse(T->lchild);printf("%c ",T->data);double_preorderTraverse(T->rchild);} }

5求結點的個數
思路：僅一個if else

int NodeCount(BiTree &T)//求節點的個數 {if(T==NULL)return 0;elsereturn 1+NodeCount(T->lchild)+NodeCount(T->rchild); }

6求結點值的和
思路：
和求結點個數一樣的算法

int Sum(BiTree &T)//求結點值的和 {if(T==NULL)return 0;elsereturn T->data+Sum(T->lchild)+Sum(T->rchild); }

7求樹的深度
思路：
樹的深度是指樹的最大深度（根節點到最遠葉子結點的層次）

int max(int x,int y)//求兩數的最大值 {if(x>y)return x;elsereturn y; }int BiTree_height1(BiTree &T)//求樹的深度算法1 {if(T==NULL)return 0;elsereturn 1+max(BiTree_height1(T->lchild),BiTree_height1(T->rchild));} int BiTree_height2(BiTree &T)//求樹的深度算法2 {int l_height,r_height;if(T==NULL)return 0;else{l_height=BiTree_height2(T->lchild);r_height=BiTree_height2(T->rchild);return (l_height>r_height)?(l_height+1):(r_height+1);}}

8求葉子結點的個數
思路：
若T為空，則返回0；
若T為葉子結點，則返回1；
若為非葉子結點，則返回（左子樹葉子結點數+右子樹葉子結點數）；

int leafCount(BiTree &T)//求葉子結點的個數 {if(T==NULL)return 0;if(T->lchild==NULL&&T->rchild==NULL)return 1;else{return leafCount(T->lchild)+leafCount(T->rchild);}}

9求單分支結點的個數
思路：

int DegreeOne(BiTree T) {if(NULL == T)return 0;if(NULL == T->lchild && NULL == T->rchild)//為葉子結點 return 0;if(NULL != T->lchild && NULL != T->rchild)//為雙分支結點 return DegreeOne(T->lchild) + DegreeOne(T->rchild);//此時為單分支結點 return 1 + DegreeOne(T->lchild) + DegreeOne(T->rchild);} int DegreeOne1(BiTree &T)//求單分支節點的個數 算法2 {int lnum, rnum, n;if(T == NULL)return 0;else{if((T->lchild == NULL && T->rchild != NULL) ||(T->lchild != NULL && T->rchild == NULL))n = 1; //為單分支結點elsen = 0; //其他結點lnum = DegreeOne1(T->lchild); //遞歸求左子樹中單分支結點數rnum = DegreeOne1(T->rchild); //遞歸求右子樹中單分支結點數return (lnum + rnum + n);}}

10交換結點的左右子樹
另一個單獨的問題的博文
數據結構——二叉樹交換左右子樹
代碼：

void Exchange_lchild_rchild(BiTree &T)//????×óóòo￠×ó?áμ? {if(T!=NULL) if(T->lchild!=NULL||T->rchild!=NULL){BiTree temp;temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;Exchange_lchild_rchild(T->lchild);Exchange_lchild_rchild(T->rchild);}}

11尋找最小值結點
代碼：

void Findminnode(BiTree &T,char &min)//?°?ò×?D??μ?áμ? {if(T!=NULL){if(T->data<min){min=T->data;}Findminnode(T->lchild,min);Findminnode(T->rchild,min);}

12判斷是否是相同的二叉樹

思路：
1判斷這兩棵樹是否都空，如果都空，則是相同的樹，如果有一棵樹不空另一棵樹為空，則不是相同的樹
2這兩棵樹都不空，判斷這個節點對應的值相等嗎？
3若這兩個節點的值相等，遞歸同時判斷這兩棵樹的左子樹，右子樹。

status BiTree_is_same(BiTree &T,BiTree &S)//ê?·?ê??àí?μ??t2?ê÷ {if(T==NULL&&S==NULL)return 1;if(T==NULL||S==NULL)return 0;if(T->data!=S->data)return 0;return(BiTree_is_same(T->lchild,S->lchild)&&BiTree_is_same(T->rchild,S->rchild)); }

13判斷是否是平衡二叉樹
思路：
1如果這顆樹為空，則返回1
2此時（這棵樹不為空），判斷該節點的左右子樹的高度差的絕對值|（左子樹的高度—右子樹的高度）|>1,如果大于1，則返回0
3此時（該節點的左右子樹的高度差<1），遞歸遍歷該節點的左右子樹。

int BiTree_height1(BiTree &T)//?óê÷μ?é??è??·¨1 {if(T==NULL)return 0;elsereturn 1+max(BiTree_height1(T->lchild),BiTree_height1(T->rchild));} status BiTree_is_Balanced(BiTree T)//?D??ê?·?ê???oa?t2?ê÷ {if(T==NULL)return 1;if(abs(BiTree_height1(T->lchild)-BiTree_height1(T->rchild))>1)return 0;return BiTree_is_Balanced(T->lchild)&&BiTree_is_Balanced(T->rchild); }

14判斷是對稱二叉樹
思路：
1用BiTree_symmetry(BiTree T)函數調用T的左右子樹
2調用 BiTree_check(BiTree root1,BiTree root2)函數核實他的左右子樹是否滿足左右對稱，鏡像：如果左右子樹都空則返回1，若果僅有一棵樹為空,則返回0，若兩棵樹都不空，則返回（判斷左右子樹對應根節點的值是否相等，遞歸調用BiTree_check(BiTree root1,BiTree root2)判斷該節點的左右子樹）BiTree_check(root1->lchild,root2->rchild)&&BiTree_check(root1->rchild,root2->lchild)

status BiTree_check(BiTree root1,BiTree root2) {if(root1==NULL&&root2==NULL) return 1;if(root1==NULL||root2==NULL) return 0;return root1->data==root2->data&&BiTree_check(root1->lchild,root2->rchild)&&BiTree_check(root1->rchild,root2->lchild); }status BiTree_symmetry(BiTree T)// {return BiTree_check(T->lchild,T->rchild);}

全部代碼（可執行）

#include<stdio.h> #include<bits/stdc++.h> typedef char TElemType; typedef int status; typedef struct BiNode {TElemType data;struct BiNode *lchild;struct BiNode *rchild; }BiNode,*BiTree; void CreateBiTree(BiTree &T)//?t2?ê÷μ??èDò′′?¨ {TElemType ch;scanf("%c",&ch);if(ch=='#')T=NULL;else {T=(BiNode*)malloc(sizeof(BiNode));if(!T)exit(-1);T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);} } void CreateBiTree2(BiTree &T)//?t2?ê÷μ??DDò′′?¨ {TElemType ch;scanf("%c",&ch);if(ch=='#')T=NULL;else {T=(BiNode*)malloc(sizeof(BiNode));if(!T)exit(-1);CreateBiTree(T->lchild);T->data=ch;CreateBiTree(T->rchild);} } void DestroyBiTree(BiTree &T)//?t2?ê÷μ??ú?ù??·¨ {if(T==NULL)exit(-1);else{DestroyBiTree(T->lchild);DestroyBiTree(T->rchild);free(T);} }void double_preorderTraverse(BiTree T)//??Dò±éàú {if(T!=NULL){printf("%c ",T->data);double_preorderTraverse(T->lchild);printf("%c ",T->data);double_preorderTraverse(T->rchild);} }int preorderTraverse(BiTree T)//?t2?ê÷μ??èDòμY1é±éàú??·¨ {if(T==NULL)return 0;else {printf("%c ",T->data);preorderTraverse(T->lchild);preorderTraverse(T->rchild);}} int InorderTraverse(BiTree T)//?t2?ê÷μ??DDòμY1é±éàú??·¨ {if(T==NULL)return 0;else {InorderTraverse(T->lchild);printf("%c ",T->data);InorderTraverse(T->rchild);}}int PostorderTraverse(BiTree T)//?t2?ê÷μ?oóDòμY1é±éàú??·¨ {if(T==NULL)return 0;else {PostorderTraverse(T->lchild);PostorderTraverse(T->rchild);printf("%c ",T->data);}}int NodeCount(BiTree &T)//?ó?úμ?μ???êy {if(T==NULL)return 0;elsereturn 1+NodeCount(T->lchild)+NodeCount(T->rchild); }int Sum(BiTree &T)//?ó?áμ??μμ?oí {if(T==NULL)return 0;elsereturn T->data+Sum(T->lchild)+Sum(T->rchild); }int max(int x,int y)//?óá?êyμ?×?′ó?μ {if(x>y)return x;elsereturn y; }int BiTree_height1(BiTree &T)//?óê÷μ?é??è??·¨1 {if(T==NULL)return 0;elsereturn 1+max(BiTree_height1(T->lchild),BiTree_height1(T->rchild));} int BiTree_height2(BiTree &T)//?óê÷μ?é??è??·¨2 {int l_height,r_height;if(T==NULL)return 0;else{l_height=BiTree_height2(T->lchild);r_height=BiTree_height2(T->rchild);return 1+max(l_height,r_height);}}int leafCount(BiTree &T)//?óò?×ó?áμ?μ???êy {if(T==NULL)return 0;if(T->lchild==NULL&&T->rchild==NULL)return 1;else{return leafCount(T->lchild)+leafCount(T->rchild);}} void Exchange_lchild_rchild(BiTree &T)//????×óóòo￠×ó?áμ? {if(T!=NULL) if(T->lchild!=NULL||T->rchild!=NULL){BiTree temp;temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;Exchange_lchild_rchild(T->lchild);Exchange_lchild_rchild(T->rchild);}} void Findminnode(BiTree &T,char &min)//?°?ò×?D??μ?áμ? {if(T!=NULL){if(T->data<min){min=T->data;}Findminnode(T->lchild,min);Findminnode(T->rchild,min);}} int DegreeOne(BiTree T) {if(NULL == T)return 0;if(NULL == T->lchild && NULL == T->rchild)//?aò?×ó?áμ? return 0;if(NULL != T->lchild && NULL != T->rchild)//?a??·??§?áμ? return DegreeOne(T->lchild) + DegreeOne(T->rchild);//′?ê±?aμ￥·??§?áμ? return 1 + DegreeOne(T->lchild) + DegreeOne(T->rchild);} int DegreeOne1(BiTree &T)//?óμ￥·??§?úμ?μ???êy ??·¨2 {int lnum, rnum, n;if(T == NULL)return 0;else{if((T->lchild == NULL && T->rchild != NULL) ||(T->lchild != NULL && T->rchild == NULL))n = 1; //?aμ￥·??§?áμ?elsen = 0; //?????áμ?lnum = DegreeOne1(T->lchild); //μY1é?ó×ó×óê÷?Dμ￥·??§?áμ?êyrnum = DegreeOne1(T->rchild); //μY1é?óóò×óê÷?Dμ￥·??§?áμ?êyreturn (lnum + rnum + n);}}status BiTree_is_same(BiTree &T,BiTree &S)//ê?·?ê??àí?μ??t2?ê÷ {if(T==NULL&&S==NULL)return 1;if(T==NULL||S==NULL)return 0;if(T->data!=S->data)return 0;return(BiTree_is_same(T->lchild,S->lchild)&&BiTree_is_same(T->rchild,S->rchild)); }status BiTree_is_Balanced(BiTree T)//?D??ê?·?ê???oa?t2?ê÷ {if(T==NULL)return 1;if(abs(BiTree_height1(T->lchild)-BiTree_height1(T->rchild))>1)return 0;return BiTree_is_Balanced(T->lchild)&&BiTree_is_Balanced(T->rchild); }status BiTree_check(BiTree root1,BiTree root2) {if(root1==NULL&&root2==NULL) return 1;if(root1==NULL||root2==NULL) return 0;return root1->data==root2->data&&BiTree_check(root1->lchild,root2->rchild)&&BiTree_check(root1->rchild,root2->lchild); }status BiTree_symmetry(BiTree T)//??3??t2?ê÷ {return BiTree_check(T->lchild,T->rchild);} int main() { int x;int node_number,BiTree_height;BiTree T;char min;printf("′′?¨ê÷ê?è?ê÷Tμ??èDòDòáD(???Dê1ó?#′ú±í???úμ?)\n");CreateBiTree(T);printf("---2?μ￥---\n"); printf("[1]:?èDò±éàú??·¨\n");printf("[2]:?DDò±éàú??·¨\n");printf("[3]:oóDò±éàú??·¨\n");printf("[4]:?ó?áμ???êy??·¨\n");printf("[5]:?óê÷μ?é??è??·¨\n");printf("[6]:????×óóòo￠×ó?úμ???·¨\n");printf("[7]:?°?ò×?D??μ?áμ???·¨\n"); printf("[8]:?óμ￥·??§?úμ?μ???êy??·¨\n");printf("[9]?D??ê?·?ê??àí?μ?ê÷\n");printf("[10]:?D??ê?·?ê???oa?t2?ê÷\n"); printf("[11]:?D??ê?·?ê???3??t2?ê÷\n"); while(1){int n; printf("\nê?è?òa??DDμ?2ù×÷:");scanf("%d",&n);switch(n){case 1:preorderTraverse(T);break;case 2:InorderTraverse(T);break;case 3:PostorderTraverse(T);break;case 4:node_number=NodeCount(T);printf("%d",node_number);break;case 5:BiTree_height=BiTree_height1(T);printf("%d",BiTree_height);break;case 6:Exchange_lchild_rchild(T);break;case 7:min=T->data;Findminnode(T,min);//±?D??úμ÷ó?oˉêy?°?33??μ printf("%c",min);break;case 8:printf("?óμ￥·??§?áμ???êy￡o");printf("%d",DegreeOne1(T)); break;case 9:if(BiTree_is_same(T,T)) printf("ê??àí?μ?ê÷\n");else printf("2?ê??àí?μ?ê÷\n");break; case 10:if(BiTree_is_Balanced(T)) printf("ê???oa?t2?ê÷\n");else printf("2?ê???oa?t2?ê÷\n");break; case 11:if(BiTree_symmetry(T)) printf("ê???3??t2?ê÷\n");else printf("2?ê???3??t2?ê÷\n");break;}} }

總結

以上是生活随笔為你收集整理的数据结构——二叉树的递归算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。