【数据结构】C语言实现链式二叉树

目录一.链式二叉树新节点的创建二.链式二叉树的判空三.链式二叉树的先序遍历四.链式二叉树的中序遍历五.链式二叉树的后序遍历六.链式二叉树的层序遍历七.链式二叉树叶子节点的计算八.链式二叉树左孩子节点数计算九.链式二叉树右孩子节点数计算十.链式二叉树节点数计算十一.链式二叉树高度计算十二.链式二叉树查询某层节点个数十三.链式二叉树查找节点十四.判断是否为完全二叉树十五.实现翻转链式二叉树十六.链式二叉树的销毁一.链式二叉树新节点的创建创建链式二叉树结点的结构体应该包括存储数据的数据域data以及存储左孩子结点地址的指针域left存储右孩子结点地址的指针域right。创建链式二叉树新结点和单链表中创建新结点的处理方法相同。代码如下BTNode* buyNode(char x) { BTNode* node (BTNode*)malloc(sizeof(BTNode)); node-data x; node-left node-right NULL; return node; }二.链式二叉树的判空链式二叉树的判空只需要返回根节点。代码如下//判空 bool BTEmpty(BTNode* root) { return (!root); }三.链式二叉树的先序遍历链式二叉树先序遍历的思路是先访问根节点后递归访问左子树递归访问右子树。代码如下//前序遍历——根左右 void preOrder(BTNode* root) { if (root NULL) { printf(NULL ); return; } printf(%c , root-data); preOrder(root-left); preOrder(root-right); }四.链式二叉树的中序遍历链式二叉树先序遍历的思路是先递归访问左子树再访问根节点最后递归访问右子树。代码如下//中序遍历--左根右 void inOrder(BTNode* root) { if (root NULL) { printf(NULL ); return; } inOrder(root-left); printf(%c , root-data); inOrder(root-right); }五.链式二叉树的后序遍历链式二叉树先序遍历的思路是先递归访问左子树再递归访问右子树最后访问根节点。代码如下//后序遍历--左右根 void postOrder(BTNode* root) { if (root NULL) { printf(NULL ); return; } postOrder(root-left); postOrder(root-right); printf(%c , root-data); }六.链式二叉树的层序遍历链式二叉树的层序遍历需要借助数据结构队列来实现。思路先把根节点入队列再队列不为空情况下去队头出对头将队头的非空的左右孩子入队列。这是层序遍历的效果图代码如下//层序遍历 void leverOrder(BTNode* root) { Queue q; QueueInit(q); QueuePush(q, root); while (!QueueEmpty(q)) { //取队头出队头 BTNode* top QueueFront(q); QueuePop(q); printf(%c , top-data); //将队头非空左右孩子入队列 if (top-left) QueuePush(q, top-left); if (top-right) QueuePush(q, top-right); } QueueDestroy(q); }七.链式二叉树叶子节点的计算叶子节点数 左子树的叶子节点数 右子树的叶子节点数。叶子结点的判断条件是根存在且左右子树都为空。代码如下// ⼆叉树叶⼦结点个数 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); }八.链式二叉树左孩子节点数计算根结点的左孩子节点数 左子树的左孩子节点数 右子树的左孩子节点数。左孩子结点的判断条件是根存在且左子树不为空。代码如下//左孩子节点数 int BinaryTreeLLeafSize(BTNode* root) { if (root NULL) return 0; if (root-left ! NULL) return BinaryTreeLLeafSize(root-left) BinaryTreeLLeafSize(root-right)1; else return BinaryTreeLLeafSize(root-left) BinaryTreeLLeafSize(root-right); }九.链式二叉树右孩子节点数计算根结点的右孩子节点数 左子树的右孩子节点数 右子树的右孩子节点数。左孩子结点的判断条件是根存在且左子树不为空。代码如下//右孩子节点数 int BinaryTreeRLeafSize(BTNode* root) { if (root NULL) return 0; if (root-right ! NULL) return BinaryTreeRLeafSize(root-left) BinaryTreeRLeafSize(root-right)1; else return BinaryTreeRLeafSize(root-left) BinaryTreeRLeafSize(root-right); }十.链式二叉树节点数计算节点数 根节点 左孩子节点数 右孩子节点数。根节点要存在。代码如下int BinaryTreeSize(BTNode* root) { if (root NULL) { return 0; } return 1 BinaryTreeSize(root-left) BinaryTreeSize(root-right); }十一.链式二叉树高度计算二叉树的高度为左右子树中的较高子树用三目操作符即可再加上根结点自己的高度即二叉树的高度 左子树的高度 右子树的高度 ? 左子树高度 1 : 右子树高度 1代码如下//⼆叉树的深度/⾼度 int BinaryTreeDepth(BTNode* root) { if (root NULL) { return 0; } int leftDep BinaryTreeDepth(root-left); int rightDep BinaryTreeDepth(root-right); return 1 (leftDep rightDep ? leftDep : rightDep); }十二.链式二叉树查询某层节点个数根结点的K层节点数 左子树的K层节点数 右子树的K层节点数。判断条件是在K层且结点存在。代码如下// ⼆叉树第k层结点个数 int BinaryTreeLevelKSize(BTNode* root, int k) { if (root NULL) { return 0; } if (k 1) { return 1; } return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1); }十三.链式二叉树查找节点查找的思路很简单就是递归二叉树来看是否存在值为需要查找的元素的节点。需要注意的是如果左孩子存在该节点的话右孩子就无需再递归下去了直接返回该节点即可。所以要创造两个变量分别保存左子树和右子树的返回的值。即左右子树存在一个该节点则节点就存在。代码如下// ⼆叉树查找值为x的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root NULL) { return NULL; } if (root-data x) { return root; } BTNode* leftFind BinaryTreeFind(root-left, x); if (leftFind) { return leftFind; } BTNode* rightFind BinaryTreeFind(root-right, x); if (rightFind) { return rightFind; } return NULL; }十四.判断是否为完全二叉树判断二叉树是否为完全二叉树的代码与层序遍历相似都需要借助数据结构队列思路是利用完全二叉树的性质若完全二叉树不为满二叉树,则空节点必定连续出现在最后一层的靠右部分。因此利用层序遍历的思路将所有结点的空孩子也入队当完全二叉树遍历到第一个空结点时后面一定全为空结点如果后面还有非空结点那么这树就不是完全二叉树。代码如下//判断树是否是完全二叉树 bool TreeComplete(BTNode* root) { //完全二叉树按层序走,非空结点一定是连续的(出过的结点的空子树也被无形中带入队了,不用担心结点在后面没有入队) Queue q; QueueInit(q); if (root) QueuePush(q, root); while (!QueueEmpty(q)) { BTNode* front QueueFront(q); QueuePop(q); if (frontNULL) { break; } else { QueuePush(q, front-left); QueuePush(q, front-right); } } //判断是不是完全二叉树(即出队过程中剩余元素有没有非空的结点) while (!QueueEmpty(q)) { BTNode* front QueueFront(q); QueuePop(q); //front不为空,就为真,就返回假 if (front) { QueueDestroy(q); return false; } } QueueDestroy(q); return true; }十五.实现翻转链式二叉树翻转二叉树 翻转左子树 翻转右子树。和销毁二叉树的思路一致采用后序遍历的思想最后翻转根节点的左右子树。//翻转二叉树 BTNode* InvertTree(BTNode* root) { if (root NULL) return NULL; BTNode* tmp InvertTree(root-right); root-right InvertTree(root-left); root-left tmp; return root; }十六.链式二叉树的销毁二叉树的销毁采用后序遍历的思想即先销毁左右子树再销毁根节点代码如下// ⼆叉树销毁--左右根 void BinaryTreeDestory(BTNode** root) { if (*root NULL) { return; } BinaryTreeDestory(((*root)-left)); BinaryTreeDestory(((*root)-right)); free(*root); *root NULL; }