目录一. 二叉树介绍1.1 二叉树定义1.2 特殊的二叉树该部分借鉴数据结构树(Tree)【详解】_数据结构 树-CSDN博客1.2.1 斜树1.2.2 满二叉树1.2.3 完全二叉树1.2.4 二叉排序树1.2.5 平衡二叉树二. 二叉树性质三. 二叉树存储3.1 顺序存储基于一维数组3.1.1分析3.1.2 实现整体结构初始化查询数据插入数据效果演示3.2 链式存储类似上一节孩子兄弟表示法3.2.1 分析​编辑3.2.2 实现整体结构结点结构体初始化查询数据添加数据效果演示一. 二叉树介绍1.1 二叉树定义二叉树是每个结点最多有两个子树的树结构即二叉树不允许存在度⼤于2的结点二叉树是有序树子树结点分左右二叉树的五种形态空二叉树只有根结点的二叉树只有左子树的二叉树只有右子树的二叉树一般的二叉树1.2 特殊的二叉树该部分借鉴数据结构树(Tree)【详解】_数据结构 树-CSDN博客1.2.1 斜树所有结点都只有同一侧的子树的二叉树称为斜树只有左子树的叫左斜树只有右子树的叫右子树1.2.2 满二叉树在一棵二叉树中如果所有分支结点都存在左子树和右子树并且所有叶子结点都在同一层上这样的二叉树称为满二叉树推理可得一棵深度为k且有(2^k)-1(等比数列求和)个结点的二叉树称为满二叉树( k ≥ 11.2.3 完全二叉树如果一棵深度为k有n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应的 二叉树称为完全二叉树。即一个满二叉树从序号最大的结点往下删除而得到的删除的结点不能跳着删除不删7但删6推理可得所有的叶结点都出现在第k层或k1层若任一结点如果其右子树的最⼤层次为i则其左子树的最⼤层次为i或i11.2.4 二叉排序树左子树上的所有结点的数据值小于根结点的数据值右子树上的所有结点的数据值大于根结点的数据值的二叉树二叉排序树又称为二叉查找树或二叉搜索树其查找性能优秀1.2.5 平衡二叉树树上任一结点的左子树和右子树的深度之差不超过1的二叉二. 二叉树性质性质1. 在二叉树的第i(i ≥ 1)层上的结点最多为2^{n-1}个满二叉树性质2. 深度为k(k≥ 1)的二叉树最多有2^k-1个结点。满二叉树性质3. 在一棵二叉树中叶结点的数目比度为2的结点数目多一个。证明:设二叉树中有0,1,2个子结点的结点个数为n_0,n_1,n_2,总结点个数为n则有nn_0n_1n_2①换个角度除了根结点每个结点都有一个父结点的分支线那么分支线的总数为n-1,也为各结点的结点个数*子结点个数的总 和即0n_01n_12n_2得n-10n_01n_12n_2(②)联立式①②得n_0n_21性质4. 具有n个结点的完全二叉树的深度为 log_2(n1)向上取整等价于 log_2n1向下取整证明:树高h则有2^{h-1}-1(上一层)n≤2^h-1(满二叉树)所以有h-1log_2(n1)≤h所以h\lceil log_2(n1)\rceil(向上取整)同理有2^{h-1}上一层≤n2^h满二叉树所以有h-1≤log_2(n)h所以h\lfloor log_2(n)1\rfloor性质5. 如果有一棵n个结点的完全二叉树其结点编号按照层次序从上到下从左到右则除根结点外满足[父结点本结点左子节点右子节点][i/2 , i, 2i, 2i1]的规则。如图三. 二叉树存储3.1 顺序存储基于一维数组3.1.1分析根据上面的的性质5我们可以将普通的二叉树补成完全二叉树这样我们就可以直接根据下标来找结点之间的关系而不需额外维系。同时也存在一个缺点就是浪费空间因为不在树结构的空间不能存数据3.1.2 实现整体结构只使用一维数组来储存数据同时通过下标维系关系。因此不需要结点的结构体由于存在左子结点和右子结点所以还需要定义一个flag来记录孩子是那一个初始化1. 将整个数组赋为空格方便区分补的数据2.将root放入数组下标1位置查询数据遍历数组查询数据插入数据1.查询父结点的下标fxi2.当插入节点为左子结点放在下标fxi*2处3.当插入节点为右子结点放在下标fxi*21处效果演示#includestdio.h #includestdlib.h #define maxx 100//数组大小 ​ int flag;//0为左子结点1为右子结点 char data[maxx];//存储数据从下标1开始存 ​ //初始化 void initTree(char root){ for(int i0;imaxx;i){ data[i] ;//将整个数组赋为空方便区分补的数据 } data[1]root;//下标1放root } ​ //查询 int find(char fx){ //遍历查询 for(int i1;imaxx;i){ if(fxdata[i]){ return i; } } return -1; } ​ //插入 void insert(char x,char fx,int flag){ int fxifind(fx);//找到父结点的下标 if(flag0){//是左子结点 data[2*fxi]x; }else{//是右子结点 data[2*fxi1]x; } } ​ ​ int main(){ int n;//总共n个数据 char root,x,fx;//根结点读入数据读入数据的父结点 scanf(%d,n); getchar(); scanf(%c,root); initTree(root);//初始化 //插入数据 for(int i1;in;i){//还剩n-1个数据 getchar(); scanf(%c %c %d,x,fx,flag); insert(x,fx,flag); } ​ getchar(); scanf(%c,x); int xifind(x); //找父亲 if(xi/20){//根结点 printf(该结点是根节点\n); }else{ printf(该节点的父亲为%c\n,data[xi/2]); } ​ //找孩子 printf(该节点的左孩子是%c,右孩子是%c\n,data[xi*2],data[xi*21]); ​ return 0; } /* 7 A B A 0 C A 1 D B 0 E B 1 F E 0 G E 1 B ​ */结果该节点的父亲为A 该节点的左孩子是D,右孩子是E3.2 链式存储类似上一节孩子兄弟表示法3.2.1 分析我们直接用二叉链表来表示树用左子节点和右子节点来维护结点的关系与孩子兄弟表示法的长子和右兄弟不同。注孩子兄弟表示法转换成的二叉树是一种特殊的二叉树关系二者不能划等号3.2.2 实现整体结构根指针二叉链表与上一种类似由于存在左子结点和右子结点所以还需要定义一个flag来记录孩子是那一个结点结构体1个数据域char来储存数据2个指针域结构体指针指向后继结点左子结点和右子节点为了方便找父结点我们再加一个指针域指向父结点初始化1.声明根结点2.储存数据3.三个数据域均为null查询数据与孩子兄弟表示法相同1.判root是否是目标结点是的话返回该节点不是的话下一步2.在root-ch为根节点的情况下找目标节点即在原来的树的左子树找目标节点3.在root-bro为根节点的情况下找目标节点即在原来的树的右子树找目标节点当以上三步都找不到就返回null实际上这是利用递归的思想添加数据1.声明结点储存数据且节点的两个子结点指针域均为为null2.判断结点是左子结点还是右子结点将结点的地址放入父结点的对应指针域3.将父结点地址放入结点的父结点指针域效果演示#includestdio.h #includestdlib.h ​ //结点结构体 typedef struct Node{ char data;//数据域 struct Node* l;//左子结点 struct Node* r;//右子结点 struct Node* f;//父结点 ​ }Node,*BTree;//BTree是根指针见名知义 ​ int flag;//0为左子结点1为右子结点 ​ //初始化 BTree initTree(char root){ Node* s(Node*)malloc(sizeof(Node));//创建根节点 s-dataroot;//储存数据 s-ls-rs-fNULL;//两个子结点都是null return s; } ​ //查找数据 Node* find(BTree t,char x){ if(t-datax){//根节点 return t; } if(t-l!NULL){//左子树 Node* res find(t-l,x); if(res!NULL){ return res; } } if (t-r!NULL){//右子树 Node* res find(t-r,x); if(res!NULL){ return res; } } ​ return NULL;//找不到 } ​ //添加数据 BTree insert(BTree t,char x,char fx,int flag){ Node* s(Node*)malloc(sizeof(Node));//创建根节点 s-datax;//储存数据 s-ls-rNULL;//右兄弟和孩子为null ​ //将结点放入树 Node* fxifind(t,fx);//找到父结点的地址 if(flag0){//左结点 fxi-ls; }else{//右结点 fxi-rs; } s-ffxi; return t; } ​ int main(){ int n;//总共n个数据 char root,x,fx;//根结点读入数据读入数据的父结点 scanf(%d,n); getchar(); scanf(%c,root); BTree t initTree(root);//初始化 //插入数据 for(int i1;in;i){//还剩n-1个数据 getchar(); scanf(%c %c %d,x,fx,flag); tinsert(t,x,fx,flag); } ​ getchar(); scanf(%c,x); Node* pfind(t,x); //找孩子 if(p-l!NULL)printf(%c的左子结点为%c\n,x,p-l-data); if(p-r!NULL)printf(%c的右子结点为%c\n,x,p-r-data); ​ //找父亲 if(p-fNULL)printf(%c为根节点\n,x); else printf(%c的父结点为%c\n,x,p-f-data); ​ return 0; } ​ /* 7 A B A 0 C A 1 D B 0 E B 1 F E 0 G E 1 B ​ */结果B的左子结点为D B的右子结点为E B的父结点为A感谢您的阅读您的点赞是我坚持下去的动力