二叉樹基本操作C語言 c語言 定義二叉樹的結(jié)點(diǎn)結(jié)構(gòu)\n實(shí)現(xiàn)先序序列構(gòu)造二叉樹的算法\n實(shí)
二叉樹基本操作C語言
c語言
定義二叉樹的結(jié)點(diǎn)結(jié)構(gòu)\n實(shí)現(xiàn)先序序列構(gòu)造二叉樹的算法\n實(shí)現(xiàn)先序遍歷這棵二叉樹，輸出每個(gè)結(jié)點(diǎn)的值的算法\n利用先序遍歷，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)\n利用后序遍歷，求二叉樹的深度
#include <stdio.h>
#include <stdlib.h>
// 定義二叉樹節(jié)點(diǎn)結(jié)構(gòu)
typedef struct TreeNode {
? ? int val;
? ? struct TreeNode* left;
? ? struct TreeNode* right;
} TreeNode;
// 創(chuàng)建新的二叉樹節(jié)點(diǎn)
TreeNode* createNode(int val) {
? ? TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
? ? newNode->val = val;
? ? newNode->left = NULL;
? ? newNode->right = NULL;
? ? return newNode;
}
// 先序序列構(gòu)造二叉樹
TreeNode* constructBinaryTree(int* preOrder, int start, int end) {
? ? static int preIndex = 0;
? ? if (start > end) {
? ? ? ? return NULL;
? ? }
? ? TreeNode* root = createNode(preOrder[preIndex++]);
? ? if (start == end) {
? ? ? ? return root;
? ? }
? ? int i;
? ? for (i = start; i <= end; i++) {
? ? ? ? if (preOrder[i] > root->val) {
? ? ? ? ? ? break;
? ? ? ? }
? ? }
? ? root->left = constructBinaryTree(preOrder, preIndex, i - 1);
? ? root->right = constructBinaryTree(preOrder, i, end);
? ? return root;
}
// 先序遍歷二叉樹
void preOrderTraversal(TreeNode* root) {
? ? if (root == NULL) {
? ? ? ? return;
? ? }
? ? printf("%d ", root->val);
? ? preOrderTraversal(root->left);
? ? preOrderTraversal(root->right);
}
// 統(tǒng)計(jì)葉子節(jié)點(diǎn)個(gè)數(shù)
int countLeaves(TreeNode* root) {
? ? if (root == NULL) {
? ? ? ? return 0;
? ? }
? ? if (root->left == NULL && root->right == NULL) {
? ? ? ? return 1;
? ? }
? ? return countLeaves(root->left) + countLeaves(root->right);
}
// 后序遍歷二叉樹
int maxDepth(TreeNode* root) {
? ? if (root == NULL) {
? ? ? ? return 0;
? ? }
? ? int leftDepth = maxDepth(root->left);
? ? int rightDepth = maxDepth(root->right);
? ? return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
int main() {
? ? int preOrder[] = { 4, 2, 1, 3, 6, 5, 7 };
? ? int size = sizeof(preOrder) / sizeof(preOrder[0]);
? ? TreeNode* root = constructBinaryTree(preOrder, 0, size - 1);
? ? printf("先序遍歷結(jié)果：");
? ? preOrderTraversal(root);
? ? printf("\n");
? ? int leafCount = countLeaves(root);
? ? printf("葉子節(jié)點(diǎn)個(gè)數(shù)：%d\n", leafCount);
? ? int depth = maxDepth(root);
? ? printf("二叉樹深度：%d\n", depth);
? ? return 0;
}
