用手机域名做网站,网站建设培训 店,上海进博会2022,厦门网站制作阳哥目录
二叉树的数据结构
前序遍历
中序遍历
后序遍历
二叉树的创建
二叉树的销毁
二叉树的节点个数
二叉树叶子节点个数
二叉树第K层节点个数
二叉树的查找
层序遍历
判断二叉树是否为完全二叉树
完整代码 二叉树的数据结构
typedef char BTDataType;
typedef str…目录
二叉树的数据结构
前序遍历
中序遍历
后序遍历
二叉树的创建
二叉树的销毁
二叉树的节点个数
二叉树叶子节点个数
二叉树第K层节点个数
二叉树的查找
层序遍历
判断二叉树是否为完全二叉树
完整代码 二叉树的数据结构
typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;
这里二叉树是使用了链式存储
data负责存储数据left指针负责存储左孩子节点right负责存储右孩子节点
前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-_data);BinaryTreePrevOrder(root-_left);BinaryTreePrevOrder(root-_right);
} 前序遍历的规则是先访问根节点然后访问左子树最后访问右子树 根据规则我们在遍历前先打印当前根节点的值若是遇到NULL则打印N代替空节点然后再往下递归左子树、右子树即可
中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root NULL){printf(N );return;}BinaryTreeInOrder(root-_left);printf(%d , root-_data);BinaryTreeInOrder(root-_right);
} 中序遍历的规则是先访问左子树然后访问根节点最后访问右子树 所以这里先递归到左子树最左边然后打印当前节点的值然后再访问右子树右子树的左子树打印值循环往复
后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root NULL){printf(N );return;}BinaryTreePostOrder(root-_left);BinaryTreePostOrder(root-_right);printf(%d , root-_data);
} 后序遍历的规则是先访问左子树然后访问右子树最后访问根节点 跟前面的前序遍历和中序遍历基本一致都只是顺序不一样
二叉树的创建
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{if (*pi n){(*pi);return NULL;}BTNode* root (BTNode*)malloc(sizeof(BTNode));root-_data a[(*pi)];root-_left BinaryTreeCreate(a, n, pi);root-_right BinaryTreeCreate(a, n, pi);return root;
}使用该函数需要传一个数组并根据数组里的元素当作前序遍历构建起二叉树
并需要传一个数组的大小和一个标记pi在外面传参的时候从数组开始的下标开始传 这里为了让函数在递归过程中能够始终有一个变量能够指向数组的某个元素来迭代遍历数组不受递归变化而变化所以需要一个指针变量在下一次递归的时候只需要传地址就能获得*pi的值而不是通过传参 在每次递归过程中需要先创建一个根节点root并开辟一块空间并为该节点data赋值为当前走到的*pi的位置
接下来就要开始递归先从根的左子树开始到右子树并分别赋值给root的左和右 这里的递归会一直递归我们需要让他递归到空为止所以需要设定if语句限定递归次数 if语句限定了当*pi超过了数组的长度或等于数组长度时则不能继续递归获取空间
所以这里是从最后一个节点开始往回返先return最后一个节点给上一个递归的左或者右节点依次往复即可
二叉树的销毁
void BinaryTreeDestory(BTNode* root)
{if (root NULL)return;BinaryTreeDestory(root);BinaryTreeDestory(root);free(root);
}
销毁我们需要用后序遍历因为前序和中序会先将根节点给销毁了这样就不好往下找了故此要使用后序遍历来一个个free掉每一个节点
二叉树的节点个数
int BinaryTreeSize(BTNode* root)
{if (root NULL)return 0;return BinaryTreeSize(root-_left) BinaryTreeSize(root-_right) 1;
}
控制好递归的次数
只需要在遍历每一层节点时1即可
二叉树叶子节点个数
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);
}
还是先控制递归的层数当root等于空时往回返
若root的左和右都为空则说明当前节点为叶子节点返回1
最后返回左子树叶子节点和右子树叶子节点个数相加即可
二叉树第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);
}和前面的递归思路都差不多
这里返回1的条件是k 1因为只需要递归k-1次即可当递归次数达到说明也到了第k层则返回1即可
最后返回给外层的时候把左右子树的结果返回起来相加即可
二叉树的查找
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-_data x)return root;BTNode* ret1 BinaryTreeFind(root-_left, x);if (ret1)return ret1;BTNode* ret2 BinaryTreeFind(root-_right, x);if (ret2)return ret2;return NULL;
} 第一个if语句控制层数
第二个判断查找结果若找到则返回根节点root
找到的结果返回给下面的ret1指针或者ret2指针通过这两个指针返回给最外层
层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%d , front-_data);if (front-_left)QueuePush(q, front-_left);if (front-_right)QueuePush(q, front-_right);}QueueDestroy(q);
} 层序遍历是一层一层从左到右遍历那么我们就需要借助队列来完成先进先出 例如该图层序遍历后就是124356
首先我们需要将根节点入队列 然后进入循环我们循环的条件是队列为空则停止循环
所以我们还需要不断入栈
这里第一层已经入栈了这时候就可以拿到这个节点我把它叫做front
后面我们就可以打印这个front节点的data
然后就可以删除掉这个节点了但是删除的同时需要把它的左右孩子带进来但是左右孩子有可能为空所以先判断若不为空则push入队列这样第二层就入队列了 接下来继续pop2和4pop的同时打印然后push2和4的左右孩子 最后不要忘记将队列销毁防止造成内存泄漏
判断二叉树是否为完全二叉树
int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front NULL)break;QueuePush(q, front-_left);QueuePush(q, front-_right);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front NULL){QueueDestroy(q);return 0;}}QueueDestroy(q);return 1;
}
和前面层序遍历差不多我们也需要借用一个队列来完成该函数
先入第一个根节点进队列然后循环的将二叉树的全部节点按照层序遍历都push进去 push到最后队列的头节点front总会碰到空节点所以我们碰到空节点就break出去循环这是第一个循环的主要作用 例如该二叉树我们push2的时候就会把左节点3和右节点NULL给入队列那么我们的front肯定会接收到NULL从而跳出循环 如上并不是一个完全二叉树所以我们判断它不是完全二叉树的理由就是根据层序遍历它的空节点后面还有一个节点6 所以我们第二个循环的任务就是pop掉队列剩下的所有值若pop的时候发现里面还有非空节点则不为完全二叉树return 0 例如我们在把NULL节点接收给front时我们肯定会经过4这个节点然后4这个节点就会把它的左NULL和右6两个节点入队列 所以我们最后在把队列全部出掉的时候肯定会碰到这个6既然碰到了这个6就说明这不是一个完全二叉树 完整代码
#includeBinaryTree.h
#includeQueue.hBTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{if (*pi n){(*pi);return NULL;}BTNode* root (BTNode*)malloc(sizeof(BTNode));root-_data a[(*pi)];root-_left BinaryTreeCreate(a, n, pi);root-_right BinaryTreeCreate(a, n, pi);return root;
}void BinaryTreeDestory(BTNode* root)
{if (root NULL)return;BinaryTreeDestory(root);BinaryTreeDestory(root);free(root);
}int BinaryTreeSize(BTNode* root)
{if (root NULL)return 0;return BinaryTreeSize(root-_left) BinaryTreeSize(root-_right) 1;
}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 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);
}BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-_data x)return root;BTNode* ret1 BinaryTreeFind(root-_left, x);if (ret1)return ret1;BTNode* ret2 BinaryTreeFind(root-_right, x);if (ret2)return ret2;return NULL;
}void BinaryTreePrevOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-_data);BinaryTreePrevOrder(root-_left);BinaryTreePrevOrder(root-_right);
}void BinaryTreeInOrder(BTNode* root)
{if (root NULL){printf(N );return;}BinaryTreeInOrder(root-_left);printf(%d , root-_data);BinaryTreeInOrder(root-_right);
}void BinaryTreePostOrder(BTNode* root)
{if (root NULL){printf(N );return;}BinaryTreePostOrder(root-_left);BinaryTreePostOrder(root-_right);printf(%d , root-_data);
}void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%d , front-_data);if (front-_left)QueuePush(q, front-_left);if (front-_right)QueuePush(q, front-_right);}QueueDestroy(q);
}int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front NULL)break;QueuePush(q, front-_left);QueuePush(q, front-_right);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front NULL){QueueDestroy(q);return 0;}}QueueDestroy(q);return 1;
} 完
