---

1.通过前序遍历数组"ABD##E#H##CF##G##"构建二叉树

BTNode* createNode(BTDataType n)
{BTNode* NewNode = (BTNode*)malloc(sizeof(BTNode));NewNode->data = n;NewNode->left = NULL;NewNode->right = NULL;return NewNode;
}// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = createNode(a[(*pi)++]);root->left = BinaryTreeCreate(a, pi);root->right = BinaryTreeCreate(a, pi);return root;
}

---

2.前序遍历

//前序遍历
void BinaryTreePrevOrder(BTNode* root){if (root == NULL)return;printf("%c ", root->data);BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);
}

3.中序遍历

//中序
void BinaryTreeInOrder(BTNode* root) {if (root == NULL)return;BinaryTreeInOrder(root->left);printf("%c ", root->data);BinaryTreeInOrder(root->right);
}

4.后序遍历

//后序
void BinaryTreePostOrder(BTNode* root) {if (root == NULL)return;BinaryTreePostOrder(root->left);BinaryTreePostOrder(root->right);printf("%c ", root->data);
}

5.层序遍历

这里需要用到队列来存储结点

//层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Que q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);printf("%c ", front->data);if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);QueuePop(&q);}printf("\n");QueueDestroy(&q);
}

6.二叉树结点个数及第k层结点个数

其中第k层结点个数相当于第k减一层的第一层，依次递归

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL)return 0;return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}// 二叉树第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);}

7.查找为x的结点

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;BTNode* ans = NULL;ans = BinaryTreeFind(root->left, x);if (ans)return ans;ans = BinaryTreeFind(root->right, x);if (ans)return ans;return NULL;
}

8.叶子结点个数

// 二叉树叶子节点个数
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);
}

9.销毁二叉树(二级指针)

//销毁二叉树
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL)return;BinaryTreeDestory(&(*root)->left);BinaryTreeDestory(&(*root)->right);free(*root);*root = NULL;
}

10.判断是否为完全二叉树

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Que q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

测试代码及运行结果

#include "tree.h"int main() {BTDataType a[] = { 'A','B','D','#','#','E','#','H','#','#','C','F','#','#','G','#','#' };int j = 0;int k = 2;BTDataType x = 'j';BTNode* root = BinaryTreeCreate(a, &j);printf("Preorder Traversal of the Binary Tree: ");BinaryTreePrevOrder(root);printf("\nInorder Traversal of the Binary Tree: ");BinaryTreeInOrder(root);printf("\nPostorder Traversal of the Binary Tree: ");BinaryTreePostOrder(root);int ret1 = BinaryTreeSize(root);printf("\n节点数为%d\n", ret1);int ret2 = BinaryTreeLevelKSize(root, k);printf("第k层节点数为%d\n", ret2);BTNode* ret3 = BinaryTreeFind(root, x);if (ret3 == NULL)printf("没找到\n");elseprintf("找到了\n");int ret4 = BinaryTreeLeafSize(root);printf("叶子节点数为%d\n", ret4);printf("Levelorder Traversal of the Binary Tree: ");BinaryTreeLevelOrder(root);int ret5 = BinaryTreeComplete(root);printf("\n%d", ret5);return 0;
}