2.20数据结构与算法学习日记（二叉树第一部分）
1.树的表示
typedef int DadaType;
struct Node{struct Node* firstChild;struct Node* pnextBrotherDataType data;
};//树的表示2.二叉树的简介
二叉树是一种树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树具有以下特点：
1. 根节点：二叉树的顶端节点称为根节点，它没有父节点。
2. 子节点：每个节点最多有两个子节点，分别称为左子节点和右子节点。
3. 叶节点：没有子节点的节点称为叶节点。
4. 深度：从根节点到某个节点的唯一路径上的节点数称为该节点的深度。
5. 高度：从某个节点到叶节点的最长路径上的节点数称为该节点的高度。
6. 完全二叉树：除了最底层之外，每一层的节点都是满的，并且最底层的节点都靠左排列。
7. 满二叉树：每个节点要么没有子节点，要么有两个子节点。
二叉树可以用来表示表达式、文件系统、数据库索引等各种数据结构和算法问题。常见的二叉树遍历方式有前序遍历、中序遍历和后序遍历。
3.二叉树图例（部分）
1.普通二叉树
普通二叉树是一种最基本的二叉树，每个节点最多有两个子节点，分别称为左子节点和右子节点。普通二叉树没有特定的规则或性质，节点的插入和删除可以任意进行，因此它的形态和结构比较灵活。
以下是一个示例普通二叉树的图示：
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
在这个例子中，这是一个普通二叉树，每个节点最多有两个子节点，节点的插入和删除可以随意进行，没有特定的规则限制。普通二叉树常用于表示一般的树形结构，如文件系统、家谱等。
2.完全二叉树
完全二叉树是一种特殊的二叉树，除了最底层之外，每一层的节点都是满的，并且最底层的节点都靠左排列。在完全二叉树中，如果某个节点的索引为i（从1开始），则它的左子节点的索引为2i，右子节点的索引为2i+1。
以下是一个示例完全二叉树的图示：
```
1
/ \
2 3
/ \ /
4 5 6
```
在这个例子中，这是一个完全二叉树，因为每一层的节点都是满的，除了最底层的节点6之外，其他节点都是靠左排列的。完全二叉树常用于堆数据结构的实现，具有较好的性能特性。
3.满二叉树
满二叉树是一种特殊的二叉树，每个节点要么没有子节点，要么有两个子节点。除了叶节点外，每个节点都有两个子节点。满二叉树的叶节点都在同一层，且所有非叶节点的度都是2。
以下是一个示例满二叉树的图示：
1
/ \
2 3
/ \ / \
4 5 6 7
在这个例子中，这是一个满二叉树，每个节点要么没有子节点，要么有两个子节点，所有非叶节点的度都是2。满二叉树在计算机科学中常用于堆数据结构的实现，具有一些特殊的性质和应用。
4.二叉树遍历
1.前序遍历
在前序遍历中，对于任意节点，先访问该根节点，然后递归地对其左子树进行前序遍历，最后递归地对其右子树进行前序遍历。
以下是一个示例二叉树的前序遍历顺序（节点值用数字表示）：
1/ \2 3/ \ / \4 5 6 7
前序遍历的结果为：1, 2, 4, 5, 3, 6, 7。
在这个例子中，前序遍历先访问根节点1，然后递归地对左子树进行前序遍历（2, 4, 5），最后递归地对右子树进行前序遍历（3, 6, 7）。
2.中序遍历
在中序遍历中，对于任意节点，先递归地对其左子树进行中序遍历，然后访问该节点，最后递归地对其右子树进行中序遍历。
以下是一个示例二叉树的中序遍历顺序（节点值用数字表示）：
1
/ \
2 3
/ \ / \
4 5 6 7
中序遍历的结果为：4, 2, 5, 1, 6, 3, 7。
在这个例子中，中序遍历先递归地对左子树进行中序遍历（4, 2, 5），然后访问根节点1，最后递归地对右子树进行中序遍历（6, 3, 7）。
3.后序遍历
它的遍历顺序是先递归地对左子树进行后序遍历，然后递归地对右子树进行后序遍历，最后访问根节点。（左，右，根）
在后序遍历中，对于任意节点，先递归地对其左子树进行后序遍历，然后递归地对其右子树进行后序遍历，最后访问该根节点。
以下是一个示例二叉树的后序遍历顺序（节点值用数字表示）：
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
后序遍历的结果为：4, 5, 2, 6, 7, 3, 1。
在这个例子中，后序遍历先递归地对左子树进行后序遍历（4, 5, 2），然后递归地对右子树进行后序遍历（6, 7, 3），最后访问根节点1。
代码示例（单纯只是定义了函数）
#include<bits/stdc++.h>
using namespace std;
typedef int DadaType;
struct Node{struct Node* firstChild;struct Node* pnextBrotherDataType data;
};//树的表示
//二叉链
struct binaryTreeNode{struct binaryTreeNode* pleft;struct binaryTreeNode* pright;
}BTnode;
void PreOrder(BTnode *root){//前序遍历(根，左，右)if(root==NULL){printf("NULL");return;}printf("%d",root->data);PreOrder(root->pleft);PreOrder(root->pright);
}
void Inorder(BTnode *root){//中序遍历（左，根，右）if(root==NULL){printf("NULL");return;}Inorder(root->pleft);printf("%d",root->data);Inorder(root->pright);
}
void PostOrder(Btnode *root){//后序遍历（左，右，根）if(root==NULL){printf("NULL");}PostOrder(root->pleft);printf("%d",root->data);PostOrder(root->pright);
}
void destroyOrder(BTnode *root){if(root==NULL){return;}destroyOrder(root->pleft);destroyOrder(root->pright);free(root);root=NULL;
}