目录链式二叉树的模拟实现二叉树的数据结构基本功能实现树初始化和销毁遍历方式遍历方式的概念解释遍历方式的代码模拟实现层序遍历计算树的节点个数二叉树叶子结点个数二叉树k层结点个数二叉数的最大深度查找元素判断是否为完全二叉树链式二叉树的模拟实现二叉树的数据结构typedef int TreeDateType; typedef struct TreeNODE { TreeDateType data; struct TreeNODE* left; struct TreeNODE* right; }TreeNODE; typedef struct Tree { TreeNODE* phead; int size; }Tree;基本功能实现树初始化和销毁void TreeInit(Tree* head)//初始化 { head-size 0; head-phead NULL; return; } void Treedestory(TreeNODE* ptr)//销毁一 { if (ptr NULL) { return; } Treedestory(ptr-left);//后序遍历 Treedestory(ptr-right); free(ptr); ptr NULL; return; } void TreeDestory(Tree* head)//销毁二 { Treedestory(head-phead); head-size 0; return; }遍历方式遍历方式的概念解释树是一个非线性的数据结构我们就不能以普通的顺序遍历方式来遍历二叉树的遍历方式多了三种前序遍历、中序遍历和后序遍历。如何理解这三种遍历方式呢我们知道二叉树是由一个根节点和两个向下分支出来的两个节点构成三种遍历方式就是以三个围绕张开的遍历方式。为了方便理解我们把三个节点分为根、左、右来理解。前序遍历根-左-右中序遍历左-根-右后序遍历左-右-根记住一定是无论根在哪个位置都是左优先在右。以上图的二叉树为例前序遍历的输出打印方式就是1 2 4 5 3 6 7以为以1 2 3 为一个节点来说那么就是优先打印1然后走到2而 2 4 5又是一个节点那么就优先打印 2 然后在走到 4 4也是一个节点但是没有其他两节点了所以只 打印出 4 就返回到 2 4 5的节点中再走到 5 同理就打印出 5 2 4 5 这整个节点打印结束就回到 1 2 3 的节点中同样的方式打印出剩下的节点所以打印出来的是1 2 4 5 3 6 7。中序遍历打印方式4 2 5 1 6 3 7.功能介绍与前序遍历方法类似后序遍历打印方式4 5 2 6 7 3 1 功能介绍与前序遍历方法类似遍历方式的代码模拟实现我们其实在观察概念的时候其实也不难看出二叉树的章节的代码实现其实已经很明显的看出都要以函数递归来实现代码的的确无论实现前中后序遍历都是需要到函数递归来实现。void preorder(TreeNODE* ptr)//前序打印 { if (ptr NULL) { return; } printf(%d , ptr-data); preorder(ptr-left); preorder(ptr-right); return; } void inorder(TreeNODE* ptr)//中序打印 { if (ptr NULL) { return; } inorder(ptr-left); printf(%d , ptr-data); inorder(ptr-right); return; } void postorder(TreeNODE* ptr)//后序打印 { if (ptr NULL) { return; } postorder(ptr-left); postorder(ptr-right); printf(%d , ptr-data); return; } void Tree_print (Tree* head,void* Print(TreeNODE*))//输出打印 { Print(head-phead); printf(\n); return; }我的这套代码是通过函数回调函数来实现函数的打印输出通过Tree_print 函数 传参结构体和相关的遍历打印输出函数来实现。void Treetest() { Tree head; TreeInit(head); Treepush(head, 1); Treepush(head, 2); Treepush(head, 3); Treepush(head, 4); Treepush(head, 5); Treepush(head, 6); Treepush(head, 7); Tree_print(head, preorder); Tree_print(head, inorder); Tree_print(head, postorder); TreeDestory(head); return; } int main() { Treetest(); return 0; }输出结果层序遍历除了三种遍历方式之外还有一种的就是层序遍历功能描述就是以按顺序的每一层的数值依次打印出来以图上的二叉树为例打印出来就是1 2 3 4 5 6 7。那么我们要实现改代码就要用到之前的数据结构的知识队必要操作沿用以前的写过的队的数据结构或者先写也可以基本功能的保证初始化销毁入队和出队的功能输出可不用将原本typedef int QUEDatatype 的 int 类型或者其他改成TreeNODE* 的树节点结构体类型。queue.c 和queue.h 的文件拷贝一份到对应的现在写的Tree.c 文件当前位置并且Tree.c 文件内要有#include queue.h的库的调用。queue.h#include stdio.h #include stdlib.h #include assert.h #include stdbool.h typedef struct TreeNODE* QUEDatatype; typedef struct queuenode { QUEDatatype data; struct queuenode* next; }QN; typedef struct queue { QN* phead;//头 QN* ptail;//尾 int size; }Q; //队头队尾 void queue_init(Q* queue);//初始化 void queue_destory(Q* queue);//销毁队 void queue_push(Q* queue, QUEDatatype a);//入队 void queue_pop(Q* queue);//出队函数 void queue_print(Q* queue);//输出queue.c#include queue.h void queue_init(Q* queue)//初始化 { queue-phead queue-ptail NULL; queue-size 0; return; } void queue_destory(Q* queue)//销毁队 { QN* dest; while (queue-phead) { dest queue-phead; queue-phead queue-phead-next; free(dest); queue-size--; } queue-ptail NULL; return; } void queue_push(Q* queue, QUEDatatype a)//入队 { QN* node (QN*)malloc(sizeof(QN)); if (node NULL) { perror(malloc); exit(1); } node-data a; node-next NULL; if (queue-phead NULL) { queue-phead node; queue-ptail node; queue-size; } else { queue-ptail-next node; queue-ptail node; queue-size; } return; } void queue_pop(Q* queue)//出队函数 { if (queue-size) { QN* pop queue-phead; queue-phead queue-phead-next; free(pop); queue-size--; if (queue-phead NULL) queue-ptail NULL; } return; } void queue_print(Q* queue)//输出 { QN* p queue-phead; while (p ! NULL) { printf(%p -, (void*)p-data); p p-next; } printf(\n); return; }Tree.c#include Tree.h #include queue.h实现思路要实现该代码的原理也不困难肯定必不可少的就是循环的利用或者递归当然如果在一开始的时候我们没办法想象到如何运用递归的知识还是保险起见还是先用循环来实现。我们要实现循环可先分为三个部分头、过程和尾的部分头的功能就是延续循环的根本、过程就是功能的实现尾就是能使循环逐渐停止的功能。头queue_push 入队 判断队的节点的树左右节点是否有内容需不需要入队过程printf(%d , queue.phead-data-data); 打印输出队尾尾queue_pop(queue); 出队头。代码展示void level_order(TreeNODE* ptr)//顺序打印 { Q queue; queue_init(queue); queue_push(queue, ptr); while (queue.phead) { if (queue.phead-data-left) { queue_push(queue, queue.phead-data-left); } if (queue.phead-data-right) { queue_push(queue, queue.phead-data-right); } printf(%d , queue.phead-data-data); queue_pop(queue); } queue_destory(queue); return; } void Tree_print (Tree* head,void* Print(TreeNODE*))//输出打印 { Print(head-phead); printf(\n); return; }void Treetest() { Tree head; Tree_init(head); Tree_push(head, 1); Tree_push(head, 2); Tree_push(head, 3); Tree_push(head, 4); Tree_push(head, 5); Tree_push(head, 6); Tree_push(head, 7); Tree_print(head, level_order); Tree_destory(head); return; }类似的就是层序的写入功能也是一样的。TreeNODE* Tree_malloc(TreeDateType a) { TreeNODE* node (TreeNODE*)malloc(sizeof(TreeNODE)); if (node NULL) { perror(malloc); return NULL; } node-data a; node-left NULL; node-right NULL; return node; } void Tree_push(Tree* head,TreeDateType a)//层序写入 { if (head-phead NULL) { head-phead Tree_malloc(a); return; } Q queue; queue_init(queue); queue_push(queue, head-phead); while (1) { if (queue.phead-data-left NULL) { queue.phead-data-left Tree_malloc(a); break; } if (queue.phead-data-right NULL) { queue.phead-data-right Tree_malloc(a); break; } queue_push(queue, queue.phead-data-left); queue_push(queue, queue.phead-data-right); queue_pop(queue); } head-size; queue_destory(queue); return; }通过层序直到遇到对应位NULL的位置就通过malloc 创建空间退出循环销毁 queue。实现树的层序遍历的创建。计算树的节点个数//计算树的节点个数 1 int Tree_size_1(Tree* ptr) { return ptr-size; } //计算树的节点个树 2 int Tree_size_2(TreeNODE* ptr) { if (ptr NULL) { return 0; } return 1 Tree_size_2(ptr-left) Tree_size_2(ptr-right); }两种方式就是在的设置树的节点的时候已经有预留一个空间来存取size 的大小另一种就是没有预留空间来存取那么就直接计算无论是什么遍历方式都可以我这里用的就是前序遍历的方式来实现数值的递归放回的进行计算。二叉树叶子结点个数要求计算末端节点的个数int Tree_leaf_size(TreeNODE* ptr) { if (ptr NULL) { return 0; } if (ptr-left NULL ptr-right NULL) { return 1; } return Tree_leaf_size(ptr-left) Tree_leaf_size(ptr-right); }二叉树k层结点个数要求计算出k 层的节点个数int Tree_levelK_size(TreeNODE* ptr, int k) { if (k 1 ptr ! NULL)//是否符合条件 { return 1; } else if (ptr NULL)//判断为空指针 { return 0; } return Tree_levelK_size(ptr-left, k - 1) Tree_levelK_size(ptr-right, k - 1);//递归 }二叉数的最大深度要求计算出的二叉树的最大深度int Tree_depth(TreeNODE* ptr) { if (ptr NULL)//判断为空指针 { return 0; } if (Tree_depth(ptr-left) Tree_depth(ptr-right))//比较长短 { return 1 Tree_depth(ptr-left); } else { return 1 Tree_depth(ptr-right); } }查找元素要求查找 a 元素所在位置并且返回地址如果没有就直接访问 NULL空指针TreeNODE* Tree_find(TreeNODE* ptr,TreeDateType a) { if (ptr NULL)//判断为空 { return NULL; } if (ptr-data a)//识别是否为所需元素 { return ptr; } TreeNODE* find Tree_find(ptr-right, a);//递归 if (find ! NULL) { return find; } return Tree_find(ptr-left, a);//递归 } /* 因为指针和return 的条件不能直接使用两个return */判断是否为完全二叉树bool Tree_complete(Tree* ptr) { Q queue; int input 0;//0 就是未遇到NULL 1 遇到NULL进行 queue_init(queue); queue_push(queue, ptr-phead); while (queue.phead !input) { if (queue.phead-data-left NULL !input) { input 1; } else { queue_push(queue, queue.phead-data-left); } if (queue.phead-data-right NULL !input) { input 1; } else { queue_push(queue, queue.phead-data-right); } if(!input) queue_pop(queue); } while (input) { if (queue.phead-data ! NULL) { if (queue.phead-data-left ! NULL input) { input 0; } if (queue.phead-data-right ! NULL input) { input 0; } queue_pop(queue); } else { break; } } queue_destory(queue); return input; }void Treetest() { Tree head; Tree_init(head); Tree_push(head, 1); Tree_push(head, 2); Tree_push(head, 3); Tree_push(head, 4); Tree_push(head, 5); Tree_push(head, 6); Tree_push(head, 7); Tree_push(head, 8); Tree_push(head, 9); head.phead-right-right-rightTree_malloc(10); //Tree_print(head, pre_order); //Tree_print(head, in_order); //Tree_print(head, post_order); Tree_print(head, level_order); printf(%d\n, Tree_size_2(head.phead)); printf(%d\n, Tree_leaf_size(head.phead)); printf(%d\n, Tree_levelK_size(head.phead,3)); printf(%d\n, Tree_depth(head.phead)); printf(%p\n, Tree_find(head.phead, 10)); printf(%d\n, Tree_complete(head)); Tree_destory(head); return; }感谢观看悠仁さん