二叉树基本概念及遍历-洪萨配资

二叉树基本概念及遍历

1、基本概念

二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。它是非线性数据结构中最基础、最重要的一种。

2、核心特征

2.1.结构特性

每个节点最多有两个子节点（0个、1个或2个）
子节点有明确顺序：左子节点和右子节点（顺序不可互换）
第 i 层最多有2^(i-1)个节点
高度为 h 的二叉树最多有2^h - 1个节点

2.2.基本性质

设 n 为节点总数，n₀ 为叶子节点数，n₁ 为度为1的节点数，n₂ 为度为2的节点数：（度即是分支数量）

n = n₀ + n₁ + n₂
n₀ = n₂ + 1

推导：

从节点到子节点的边数 = 0*n₀ + 1*n₁ + 2*n₂ = n₁ + 2n₂ 从子节点到父节点的边数 = n - 1（因为根节点没有父节点） n₁ + 2n₂ = n - 1 得：n₀ = n₂ + 1

3、相关名词

3.1.节点相关

根节点：没有父节点的节点，树的起点
内部节点：至少有一个子节点的节点
叶子节点：没有子节点的节点（度为0）
父节点：直接上级节点
子节点：直接下级节点

3.2.遍历相关

前序遍历：根 → 左 → 右
中序遍历：左 → 根 → 右
后序遍历：左 → 右 → 根
层序遍历：按层次从上到下、从左到右

4、二叉树的基础类型

4.1.满二叉树

定义：每个节点都有0个或2个子节点
特征：没有度为1的节点
叶子节点数 = 内部节点数 + 1

1 / \ 2 3 / \ 4 5

4.2.完全二叉树

定义：除最后一层外，其他层都完全填满，最后一层从左到右填充，不能间断
特点：
- 可以用数组高效存储
- 第 i 个节点的左子节点：2i，右子节点：2i+1，父节点：⌊i/2⌋（编号一般从1开始，如果从0开始，公式相应改变）

1 / \ 2 3 / \ / 4 5 6

4.3.完美二叉树

定义：所有叶子节点都在同一层，每个内部节点都有两个子节点（属于特殊的满二叉树）

1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \/ \ / \ 8 9 10111213 14

4.4.平衡二叉树

定义：任意节点的左右子树高度差不超过1
高度的定义：从该节点到最远叶子节点的最长路径的边数

1 / \ 2 3 / \ 错误示范，“1”节点左右子数高度差超过1 4 5 \ 6

4.5.二叉搜索树

性质：对于任意节点
- 左子树所有节点值 < 当前节点值
- 右子树所有节点值 > 当前节点值
中序遍历得到有序序列

8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13

5.普通二叉树的实现（链表实现）

5.1.结构定义

typedefstructTreeNode{intdata;// 节点数据structTreeNode*left;// 左子树指针structTreeNode*right;// 右子树指针}TreeNode;typedefstructBinaryTree{TreeNode*root;// 根节点指针intsize;// 节点总数}BinaryTree;

5.2.基本操作

创建树的节点，树的结构

TreeNode*createNode(intdata){//节点TreeNode*newNode=(TreeNode*)malloc(sizeof(TreeNode));if(newNode==NULL){printf("内存分配失败");exit(1);}newNode->data=data;newNode->left=NULL;newNode->right=NULL;returnnewNode;}BinaryTree*createBinaryTree(){BinaryTree*tree=(BinaryTree*)malloc(sizeof(BinaryTree));if(tree==NULL){printf("内存分配失败");exit(1);}tree->root=NULL;tree->size=0;returntree;}

插入与删除节点

对于普通二叉树，一般只是先提前构建好二叉树，之后进行只读操作。大多不进行删除插入。

但如果要插入删除的话，和链表也差不多，根据相应的编号或位置，遍历，然后进行相关的链表操作。

//先遍历找到对应节点n1,n2，遍历后面说TreeNode*new=creatNode(0);//在n1与n2间插入节点P（0）n1->left=new;new->left=n2;//删除节点Pn1->left=n2;free(P);

遍历

1.递归（深度优先）

1 / \ 2 3 / \ / \ 4 5 6 7

二叉树的前序中序后序遍历：

前序：根 -> 左 -> 右，即1，2，4，5，3，6，7.

中序：左 -> 根 -> 右，即4，2，5，1，6，3，7.

后序：左 -> 右 -> 根，即4，5，2，6，7，3，1.

voidpreorderTraversal(TreeNode*root){// 前序遍历：根 -> 左 -> 右if(root==NULL){return;}printf("%d ",root->data);// 访问根节点preorderTraversal(root->left);// 遍历左子树preorderTraversal(root->right);// 遍历右子树}voidinorderTraversal(TreeNode*root){// 中序遍历：左 -> 根 -> 右if(root==NULL){return;}inorderTraversal(root->left);printf("%d ",root->data);inorderTraversal(root->right);}voidpostorderTraversal(TreeNode*root){// 后序遍历：左 -> 右 -> 根if(root==NULL){return;}postorderTraversal(root->left);postorderTraversal(root->right);printf("%d ",root->data);}

例题：力扣144. 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的前序遍历。
示例：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]

思路：
先计算总节点，方便之后分配数组，再通过前序遍历将节点按固定顺序放入数组中。
代码：

intgetNodeCount(structTreeNode*root){if(root==NULL)return0;return1+getNodeCount(root->left)+getNodeCount(root->right);}voidpreorder(structTreeNode*root,int*result,int*index){if(root==NULL)return;result[(*index)++]=root->val;preorder(root->left,result,index);preorder(root->right,result,index);}int*preorderTraversal(structTreeNode*root,int*returnSize){*returnSize=getNodeCount(root);int*result=(int*)malloc(sizeof(int)*(*returnSize));if(result==NULL){*returnSize=0;returnNULL;}intindex=0;preorder(root,result,&index);returnresult;}

2.使用队列（广度优先）

1 / \ 2 3 / \ / \ 4 5 6 7

遍历得到：1，2，3，4，5，6，7.

思路：

第1步：根节点1入队

队列：[1]

第2步：队首1出队，访问1，把1的子节点2和3入队

访问：1 队列：[2, 3]

第3步：队首2出队，访问2，把2的子节点4和5入队

访问：1 2 队列：[3, 4, 5]

第4步：队首3出队，访问3，把3的子节点6和7入队

访问：1 2 3 队列：[4, 5, 6, 7]

第5步：队首4出队，访问4，4没有子节点

访问：1 2 3 4 队列：[5, 6, 7]

第6步：队首5出队，访问5，5没有子节点

访问：1 2 3 4 5 队列：[6, 7]

第7步：队首6出队，访问6，6没有子节点

访问：1 2 3 4 5 6 队列：[7]

第8步：队首7出队，访问7，7没有子节点

访问：1 2 3 4 5 6 7 队列：[空]

队列相关实现：

typedefstructQueue{// 定义队列结构TreeNode**array;intfront;intrear;intcapacity;}Queue;Queue*createQueue(intcapacity){//创建队列Queue*queue=(Queue*)malloc(sizeof(Queue));queue->array=(TreeNode**)malloc(sizeof(TreeNode*)*capacity);queue->front=0;queue->rear=0;queue->capacity=capacity;returnqueue;}voidenqueue(Queue*queue,TreeNode*node){//将二叉树节点放入队列if((queue->rear+1)%queue->capacity==queue->front){return;}queue->array[queue->rear]=node;queue->rear=(queue->rear+1)%queue->capacity;}TreeNode*dequeue(Queue*queue){//出队列if(queue->front==queue->rear){returnNULL;}TreeNode*node=queue->array[queue->front];queue->front=(queue->front+1)%queue->capacity;returnnode;}intisQueueEmpty(Queue*queue){//判断为空returnqueue->front==queue->rear;}

开始遍历：

voidlevelOrderTraversal(TreeNode*root){if(root==NULL){return;}Queue*queue=createQueue(100);enqueue(queue,root);while(!isQueueEmpty(queue)){TreeNode*node=dequeue(queue);printf("%d ",node->data);if(node->left)enqueue(queue,node->left);if(node->right)enqueue(queue,node->right);}printf("\n");free(queue->array);free(queue);}