1.二叉树的前序遍历
2.二叉树的中序遍历
3.二叉树的后序遍历
4.二叉树的层序遍历
5.二叉树的节点个位
6.二叉树的叶子节点个位数
7.二叉树的的k层节点数
8.查找值为x的节点
9.二叉树的销毁
10.判断二叉树是否为完全二叉树
11.求二叉树的高度h
12.通过前序遍历构建二叉树
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h>typedef int BTDataType; typedef struct BinaryTreeNode {BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right; }BTNode;BTNode* BuyNode(BTDataType x); BTNode* CreatBinaryTree(); void BTreeDestory(BTNode* root); int BinaryTreeSize(BTNode* root); int BinaryTreeLeafSize(BTNode* root); int BinaryTreeLevelKSize(BTNode* root, int k); //查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); //前、中、后序遍历 void PrevOrder(BTNode* root); void InOrder(BTNode* root); void PostOrder(BTNode* root); //层序遍历 void LevelOrder(BTNode* root); bool BinaryTreeComplete(BTNode* root); //通过前序遍历构建二叉树 BTNode* PrevOrderCreate(char* a, int* pi);
1.通过前序遍历构建二叉树
BTNode* BuyNode(BTDataType x) {BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node; } //（int* pi）是数组的下标用来遍历数组，因为如果不传地址，形参改变不会影响实参 BTNode* PrevOrderCreate(char* a, int* pi) {if (a[*pi] == '#'){++(*pi);return NULL;}BTNode* root = BuyNode(a[*pi]);++(*pi);//递归root->left = PrevOrderCreate(a, pi);root->right = PrevOrderCreate(a, pi);return root; }
2. 二叉树的销毁
void BTreeDestory(BTNode* root) {if (root == NULL)return;BTreeDestory(root->left);BTreeDestory(root->right);free(root); }
3.二叉树的遍历
//前序遍历 void PrevOrder(BTNode* root) {if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right); } //中序遍历 void InOrder(BTNode* root) {if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right); } //后序遍历 void PostOrder(BTNode* root) {if (root == NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data); } //层序遍历 void LevelOrder(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);}printf("\n");QueueDestroy(&q); }层序遍历需要用到队列：队列的实现_元清加油的博客-CSDN博客
4. 二叉树的节点个位和二叉树的叶子节点个位数
二叉树的节点个位 int BinaryTreeSize(BTNode* root) {return root == NULL ? 0 :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); }
5. 二叉树的的k层节点数和查找值为x的节点
二叉树的的k层节点数 int BinaryTreeLevelKSize(BTNode* root, int k) {assert(k > 0);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* ret1 = BinaryTreeFind(root->left, x);if (ret1)return ret1;BTNode* ret2 = BinaryTreeFind(root->right, x);if (ret2)return ret2;return NULL; }
6. 判断二叉树是否为完全二叉树和求二叉树的高度h
// 判断二叉树是否是完全二叉树 bool 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){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true; } //求二叉树的高度h int BinaryTreeHeight(BTNode* root) {if (root == NULL){return 0;}int LeftHeight = BinaryTreeHeight(root->left);int RightHeight = BinaryTreeHeight(root->right);return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1; }判断是否为完全二叉树需要用到队列：队列的实现_元清加油的博客-CSDN博客
