课堂笔记
数组,链表它们有一个共同的特点——线性表
线性表由若干元素按照线性结构(一对一的关系)组成的有限序列,是一对一的关系。
那么一对多是由什么实现的呢?树!
树是一个由n个节点组成的有限集合,子树是该集合的子集。
度:节点所拥有的子树个数。二叉树:度小于等于2,大于等于0。度为0的节点叫做叶子节点。
深度:树的最大层次
二叉树是有序树,完全二叉树的节点从上到下,从左到右的节点顺序不能中断。
满二叉树,完全二叉树,非完全二叉树
二叉树遍历方式:先序,中序,后序
C语言实现
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 创建新节点
struct TreeNode* createNode(int val) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
// 插入节点
struct TreeNode* insert(struct TreeNode* root, int val) {
if (root == NULL) {
return createNode(val);
}
if (val < root->val) {
root->left = insert(root->left, val);
} else if (val > root->val) {
root->right = insert(root->right, val);
}
return root;
}
// 中序遍历二叉树
void inorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
int main() {
int a[] = {5, 3, 7, 1, 9, 4};
int len = sizeof(a) / sizeof(a[0]);
struct TreeNode* root = NULL;
root = insert(root, a[0]);
for (int i = 1; i < len; i++) {
insert(root, a[i]);
}
inorderTraversal(root); // 输出:1 3 4 5 7 9
}
三种遍历方式
© 版权声明
文章版权归作者所有,请勿转载至任何平台。
THE END
暂无评论内容