网站怎么运营推广,达美网站建设,seo有名气的优化公司,企业类网站模版二叉树的结构定义#xff1a;
typedef struct BiNode
{TElemType data;struct BiNode *lchild;struct BiNode *rchild;
}BiNode,*BiTree;这里包含的递归算法有#xff1a;
二叉树的先序创建#xff1b;二叉树的先序中序后序遍历#xff1b;二叉树的销毁算法#xff1b;双…二叉树的结构定义
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#)TNULL;else {T(BiNode*)malloc(sizeof(BiNode));if(!T)exit(-1);T-datach;CreateBiTree(T-lchild);CreateBiTree(T-rchild);}
}2二叉树的先序中序后序遍历 思路 先序中序后序递归算法都类似 int preorderTraverse(BiTree T)//二叉树的先序递归遍历算法
{if(TNULL)return 0;else {printf(%c ,T-data);preorderTraverse(T-lchild);preorderTraverse(T-rchild);}} int InorderTraverse(BiTree T)//二叉树的中序递归遍历算法
{if(TNULL)return 0;else {InorderTraverse(T-lchild);printf(%c ,T-data);InorderTraverse(T-rchild);}}int PostorderTraverse(BiTree T)//二叉树的后序递归遍历算法
{if(TNULL)return 0;else {PostorderTraverse(T-lchild);PostorderTraverse(T-rchild);printf(%c ,T-data);}}3二叉树的销毁算法 思路 和后序递归算法类似
void DestroyBiTree(BiTree T)//二叉树的销毁算法
{if(TNULL)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(TNULL)return 0;elsereturn 1NodeCount(T-lchild)NodeCount(T-rchild);
}6求结点值的和 思路 和求结点个数一样的算法
int Sum(BiTree T)//求结点值的和
{if(TNULL)return 0;elsereturn T-dataSum(T-lchild)Sum(T-rchild);
}7求树的深度 思路 树的深度是指树的最大深度根节点到最远叶子结点的层次
int max(int x,int y)//求两数的最大值
{if(xy)return x;elsereturn y;
}int BiTree_height1(BiTree T)//求树的深度算法1
{if(TNULL)return 0;elsereturn 1max(BiTree_height1(T-lchild),BiTree_height1(T-rchild));} int BiTree_height2(BiTree T)//求树的深度算法2
{int l_height,r_height;if(TNULL)return 0;else{l_heightBiTree_height2(T-lchild);r_heightBiTree_height2(T-rchild);return (l_heightr_height)?(l_height1):(r_height1);}}8求叶子结点的个数 思路 若T为空则返回0 若T为叶子结点则返回1 若为非叶子结点则返回左子树叶子结点数右子树叶子结点数 int leafCount(BiTree T)//求叶子结点的个数
{if(TNULL)return 0;if(T-lchildNULLT-rchildNULL)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)//½»»»×óÓÒº¢×Ó½áµã
{if(T!NULL) if(T-lchild!NULL||T-rchild!NULL){BiTree temp;tempT-lchild;T-lchildT-rchild;T-rchildtemp;Exchange_lchild_rchild(T-lchild);Exchange_lchild_rchild(T-rchild);}}
11寻找最小值结点 代码
void Findminnode(BiTree T,char min)//Ñ°ÕÒ×îСֵ½áµã
{if(T!NULL){if(T-datamin){minT-data;}Findminnode(T-lchild,min);Findminnode(T-rchild,min);}12判断是否是相同的二叉树
思路 1判断这两棵树是否都空如果都空则是相同的树如果有一棵树不空另一棵树为空则不是相同的树 2这两棵树都不空判断这个节点对应的值相等吗 3若这两个节点的值相等递归同时判断这两棵树的左子树右子树。
status BiTree_is_same(BiTree T,BiTree S)//ÊÇ·ñÊÇÏàͬµÄ¶þ²æÊ÷
{if(TNULLSNULL)return 1;if(TNULL||SNULL)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(TNULL)return 0;elsereturn 1max(BiTree_height1(T-lchild),BiTree_height1(T-rchild));} status BiTree_is_Balanced(BiTree T)//ÅжÏÊÇ·ñÊÇƽºâ¶þ²æÊ÷
{if(TNULL)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(root1NULLroot2NULL) return 1;if(root1NULL||root2NULL) return 0;return root1-dataroot2-dataBiTree_check(root1-lchild,root2-rchild)BiTree_check(root1-rchild,root2-lchild);
}status BiTree_symmetry(BiTree T)//
{return BiTree_check(T-lchild,T-rchild);} 全部代码可执行
#includestdio.h
#includebits/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)//¶þ²æÊ÷µÄÏÈÐò´´½¨
{TElemType ch;scanf(%c,ch);if(ch#)TNULL;else {T(BiNode*)malloc(sizeof(BiNode));if(!T)exit(-1);T-datach;CreateBiTree(T-lchild);CreateBiTree(T-rchild);}
}
void CreateBiTree2(BiTree T)//¶þ²æÊ÷µÄÖÐÐò´´½¨
{TElemType ch;scanf(%c,ch);if(ch#)TNULL;else {T(BiNode*)malloc(sizeof(BiNode));if(!T)exit(-1);CreateBiTree(T-lchild);T-datach;CreateBiTree(T-rchild);}
}
void DestroyBiTree(BiTree T)//¶þ²æÊ÷µÄÏú»ÙËã·¨
{if(TNULL)exit(-1);else{DestroyBiTree(T-lchild);DestroyBiTree(T-rchild);free(T);}
}void double_preorderTraverse(BiTree T)//Ë«Ðò±éÀú
{if(T!NULL){printf(%c ,T-data);double_preorderTraverse(T-lchild);printf(%c ,T-data);double_preorderTraverse(T-rchild);}
}int preorderTraverse(BiTree T)//¶þ²æÊ÷µÄÏÈÐòµÝ¹é±éÀúËã·¨
{if(TNULL)return 0;else {printf(%c ,T-data);preorderTraverse(T-lchild);preorderTraverse(T-rchild);}} int InorderTraverse(BiTree T)//¶þ²æÊ÷µÄÖÐÐòµÝ¹é±éÀúËã·¨
{if(TNULL)return 0;else {InorderTraverse(T-lchild);printf(%c ,T-data);InorderTraverse(T-rchild);}}int PostorderTraverse(BiTree T)//¶þ²æÊ÷µÄºóÐòµÝ¹é±éÀúËã·¨
{if(TNULL)return 0;else {PostorderTraverse(T-lchild);PostorderTraverse(T-rchild);printf(%c ,T-data);}}int NodeCount(BiTree T)//Çó½ÚµãµÄ¸öÊý
{if(TNULL)return 0;elsereturn 1NodeCount(T-lchild)NodeCount(T-rchild);
}int Sum(BiTree T)//Çó½áµãÖµµÄºÍ
{if(TNULL)return 0;elsereturn T-dataSum(T-lchild)Sum(T-rchild);
}int max(int x,int y)//ÇóÁ½ÊýµÄ×î´óÖµ
{if(xy)return x;elsereturn y;
}int BiTree_height1(BiTree T)//ÇóÊ÷µÄÉî¶ÈËã·¨1
{if(TNULL)return 0;elsereturn 1max(BiTree_height1(T-lchild),BiTree_height1(T-rchild));} int BiTree_height2(BiTree T)//ÇóÊ÷µÄÉî¶ÈËã·¨2
{int l_height,r_height;if(TNULL)return 0;else{l_heightBiTree_height2(T-lchild);r_heightBiTree_height2(T-rchild);return 1max(l_height,r_height);}}int leafCount(BiTree T)//ÇóÒ¶×Ó½áµãµÄ¸öÊý
{if(TNULL)return 0;if(T-lchildNULLT-rchildNULL)return 1;else{return leafCount(T-lchild)leafCount(T-rchild);}} void Exchange_lchild_rchild(BiTree T)//½»»»×óÓÒº¢×Ó½áµã
{if(T!NULL) if(T-lchild!NULL||T-rchild!NULL){BiTree temp;tempT-lchild;T-lchildT-rchild;T-rchildtemp;Exchange_lchild_rchild(T-lchild);Exchange_lchild_rchild(T-rchild);}} void Findminnode(BiTree T,char min)//Ñ°ÕÒ×îСֵ½áµã
{if(T!NULL){if(T-datamin){minT-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)//ΪҶ×Ó½áµã 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);}}status BiTree_is_same(BiTree T,BiTree S)//ÊÇ·ñÊÇÏàͬµÄ¶þ²æÊ÷
{if(TNULLSNULL)return 1;if(TNULL||SNULL)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)//ÅжÏÊÇ·ñÊÇƽºâ¶þ²æÊ÷
{if(TNULL)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(root1NULLroot2NULL) return 1;if(root1NULL||root2NULL) return 0;return root1-dataroot2-dataBiTree_check(root1-lchild,root2-rchild)BiTree_check(root1-rchild,root2-lchild);
}status BiTree_symmetry(BiTree T)//¶Ô³Æ¶þ²æÊ÷
{return BiTree_check(T-lchild,T-rchild);} int main()
{ int x;int node_number,BiTree_height;BiTree T;char min;printf(´´½¨Ê÷ÊäÈëÊ÷TµÄÏÈÐòÐòÁÐ(ÆäÖÐʹÓÃ#´ú±í¿Õ½Úµã)\n);CreateBiTree(T);printf(---²Ëµ¥---\n); printf([1]:ÏÈÐò±éÀúËã·¨\n);printf([2]:ÖÐÐò±éÀúËã·¨\n);printf([3]:ºóÐò±éÀúËã·¨\n);printf([4]:Çó½áµã¸öÊýËã·¨\n);printf([5]:ÇóÊ÷µÄÉî¶ÈËã·¨\n);printf([6]:½»»»×óÓÒº¢×Ó½ÚµãËã·¨\n);printf([7]:Ñ°ÕÒ×îСֵ½áµãËã·¨\n); printf([8]:Çóµ¥·ÖÖ§½ÚµãµÄ¸öÊýËã·¨\n);printf([9]ÅжÏÊÇ·ñÊÇÏàͬµÄÊ÷\n);printf([10]:ÅжÏÊÇ·ñÊÇƽºâ¶þ²æÊ÷\n); printf([11]:ÅжÏÊÇ·ñÊǶԳƶþ²æÊ÷\n); while(1){int n; printf(\nÊäÈëÒª½øÐеIJÙ×÷:);scanf(%d,n);switch(n){case 1:preorderTraverse(T);break;case 2:InorderTraverse(T);break;case 3:PostorderTraverse(T);break;case 4:node_numberNodeCount(T);printf(%d,node_number);break;case 5:BiTree_heightBiTree_height1(T);printf(%d,BiTree_height);break;case 6:Exchange_lchild_rchild(T);break;case 7:minT-data;Findminnode(T,min);//±ØÐëÔÚµ÷Óú¯ÊýÇ°¸³³õÖµ printf(%c,min);break;case 8:printf(Çóµ¥·ÖÖ§½áµã¸öÊý£º);printf(%d,DegreeOne1(T)); break;case 9:if(BiTree_is_same(T,T)) printf(ÊÇÏàͬµÄÊ÷\n);else printf(²»ÊÇÏàͬµÄÊ÷\n);break; case 10:if(BiTree_is_Balanced(T)) printf(ÊÇƽºâ¶þ²æÊ÷\n);else printf(²»ÊÇƽºâ¶þ²æÊ÷\n);break; case 11:if(BiTree_symmetry(T)) printf(ÊǶԳƶþ²æÊ÷\n);else printf(²»ÊǶԳƶþ²æÊ÷\n);break;}} }
