目录一、链式二叉树结构实现二、链式二叉树的基本方法实现2.1 创造树结点2.2 创造二叉树前序2.3 二叉树的销毁2.4 前中后序遍历2.5 层序遍历2.6 求二叉树结点个数2.7 二叉树叶子结点个数2.8 二叉树第k层节点个数2.9 二叉树查找值为x的节点2.10 判断二叉树是否是完全二叉树三、总结一、链式二叉树结构实现用链表来表示⼀棵⼆叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。typedef char BTDataType; //二叉树结构 typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; };二、链式二叉树的基本方法实现2.1 创造树结点//创造树结点 BTNode* BuyNode(BTDataType x) { BTNode* root (BTNode*)malloc(sizeof(BTNode)); if (root NULL) { perror(malloc); exit(1); } root-data x; root-left root-right NULL; return root; }2.2 创造二叉树前序以这个实例为准这里用到了递归的思想先不断递归左子树然后跳出递归条件为NULL然后再销毁函数栈并返回到递归之前那个函数进而继续进行下一个代码块。比如在这里我们递归到左子树的最后一个NULL后NULL这个创建的函数栈帧返回到D这个函数中继续执行右子树NULL然后进入NULL这个函数栈帧中跳出循环回到D这个函数中返回D这个数据此时D这个函数栈帧也就销毁了进而不断递归右子树D的兄弟结点。//构造二叉树(前序) BTNode* BinaryTreeCreate(BTDataType* a, int* pi)//a为数组pi为下标 { if (a[*pi] #)//#表示空 { (*pi);//一定要加加 return NULL; } //根左右 BTNode* root BuyNode(a[*pi]); (*pi); root-left BinaryTreeCreate(a, pi); root-right BinaryTreeCreate(a, pi); return root; }2.3 二叉树的销毁二叉树的销毁也是通过递归的方式进行实现的。这里是不能顺序删除头结点的首先要递归到左右再删头结点否则唯一一个可以寻找左右结点的头结点消失了。//二叉树的销毁 void BinaryTreeDestroy(BTNode** root) { assert(root); if (*root NULL) { return; } BinaryTreeDestroy((*root)-left); BinaryTreeDestroy((*root)-right); free(*root); (*root)-data 0; *root NULL; }指针销毁时一定要记得销毁内部数据避免释放后的数据残留导致的安全问题。2.4 前中后序遍历在写前中后序遍历过程中我们需要知道遍历的规则遍历规则按照规则⼆叉树的遍历有前序/中序/后序的递归结构遍历1前序遍历(Preorder Traversal 亦称先序遍历)访问根结点的操作发⽣在遍历其左右⼦树之前访问顺序为根结点、左⼦树、右⼦树2中序遍历(Inorder Traversal)访问根结点的操作发⽣在遍历其左右⼦树之中间访问顺序为左⼦树、根结点、右⼦树3后序遍历(Postorder Traversal)访问根结点的操作发⽣在遍历其左右⼦树之后访问顺序为左⼦树、右⼦树、根结点//前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root NULL) { printf(NULL ); return; } //根左右 printf(%c , root-data); BinaryTreePrevOrder(root-left); BinaryTreePrevOrder(root-right); } //中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root NULL) { printf(NULL ); return; } //左根右 BinaryTreeInOrder(root-left); printf(%c , root-data); BinaryTreeInOrder(root-right); } //后序遍历 void BinaryTreePostOrder(BTNode* root) { if (root NULL) { printf(NULL ); return; } //左右根 BinaryTreePostOrder(root-left); BinaryTreePostOrder(root-right); printf(%c , root-data); }2.5 层序遍历//层序遍历 void BinaryTreeLevelOrder(BTNode* root) { Queue q; QueueInit(q); //插入队列中 QueuePush(q, root); while (!QueueEmpty(q)) { //取对头保存 BTNode* top QueueFront(q); printf(%c , top-data); QueuePop(q); //将左右孩子插入 if(top-left) { QueuePush(q, top-left); } if(top-right) { QueuePush(q, top-right); } } QueueDestroy(q); }2.6 求二叉树结点个数二叉树结点个数等于根结点加左右子树的结点个数1左右子树的结点//求二叉树结点个数 int BinaryTreeSize(BTNode* root) { //结点个数1左右子树结点 if (root NULL) { return 0; } return 1 BinaryTreeSize(root-left) BinaryTreeSize(root-right); }2.7 二叉树叶子结点个数叶子结点个数左子树叶子结点个数 右子树结点个数//求二叉树叶子结点个数 int BinaryTreeLeafSize(BTNode* root) { if (root NULL) { return 0; } if (root-left NULL root-right NULL) { return 1; } return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right); }2.8 二叉树第k层节点个数第k层结点递归过程中可以用逆向思维将第一层设置为k层然后不断递归减一达到预期的层数达到我们想要的目的。第k层的结点个数左子树第k层结点个数右子树第k层结点个数。//第k层结点个数 int BinaryTreeLevekSize(BTNode* root, int k) { if (root NULL) { return 0; } if (k 1) { return 1; } return BinaryTreeLevekSize(root-left,k - 1) BinaryTreeLevekSize(root-right, k - 1); }2.9 二叉树查找值为x的节点寻找为x的结点这里假设x为F这个结点那我们寻找F这个结点时只需要找到一个即可所以我们向不断递归左子树孩子的结点与寻找值对比找到后直接返回所以return 后面接的是||这个或操作符避免重复递归。//在二叉树中寻找x值 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root NULL) { return NULL; } if (root-data x) { return root; } BTNode* left BinaryTreeFind(root-left, x); if (left) { return left; } BTNode* right BinaryTreeFind(root-right, x); if (right) { return right; } return NULL; }2.10 判断二叉树是否是完全二叉树//判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root) { Queue q; QueueInit(q); QueuePush(q, root); while (!QueueEmpty(q)) { //取对头 BTNode* top QueueFront(q); QueuePop(q); if (root NULL)//跳出循环 { break; } QueuePush(q, root-left); QueuePush(q, root-right); } while (!QueueEmpty(q)) { //判断当层第一个NULL这一层是否还有结点 BTNode* top QueueFront(q); QueuePop(q); if (top ! NULL) { QueueDestroy(q); return false; } } QueueDestroy(q); return true; }三、总结实现以上的二叉树方法离不开递归当然这里遍历可以分两种类型一种是递归型前中后序遍历另一种是非递归型层序遍历但是另一种非递归型需要利用到另外学到的数据结构队列。用这个队列可以存储需要顺序遍历的结点当然这个思想让我也知道了原来数据结构之间也是可以联系在一起的并可以一起使用并实现一个另一个数据结构的方法。这个二叉树体现出了递归的便利性但也需要我们不断画图并不断理解起函数栈帧的建立和销毁。总的来说二叉树这些代码实现让我大脑充实了很多知识学会了递归在一个就是我觉得重要的是二叉树的创造我在这里卡了很久因为总是忘记在为空的情况下让指针加加导致我调试也很难看出来而且创造二叉树是我们理解二叉树的基础我认为很有必要重点关注这个。