- typedef int DadaType;
- struct Node{
- struct Node* firstChild;
- struct Node* pnextBrother
- DataType data;
- };//树的表示
二叉树是一种树形数据结构,每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树具有以下特点:
1. 根节点:二叉树的顶端节点称为根节点,它没有父节点。
2. 子节点:每个节点最多有两个子节点,分别称为左子节点和右子节点。
3. 叶节点:没有子节点的节点称为叶节点。
4. 深度:从根节点到某个节点的唯一路径上的节点数称为该节点的深度。
5. 高度:从某个节点到叶节点的最长路径上的节点数称为该节点的高度。
6. 完全二叉树:除了最底层之外,每一层的节点都是满的,并且最底层的节点都靠左排列。
7. 满二叉树:每个节点要么没有子节点,要么有两个子节点。
二叉树可以用来表示表达式、文件系统、数据库索引等各种数据结构和算法问题。常见的二叉树遍历方式有前序遍历、中序遍历和后序遍历。
以下是一个示例普通二叉树的图示:
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
在这个例子中,这是一个普通二叉树,每个节点最多有两个子节点,节点的插入和删除可以随意进行,没有特定的规则限制。普通二叉树常用于表示一般的树形结构,如文件系统、家谱等。
以下是一个示例完全二叉树的图示:
```
1
/ \
2 3
/ \ /
4 5 6
```
在这个例子中,这是一个完全二叉树,因为每一层的节点都是满的,除了最底层的节点6之外,其他节点都是靠左排列的。完全二叉树常用于堆数据结构的实现,具有较好的性能特性。
以下是一个示例满二叉树的图示:
1
/ \
2 3
/ \ / \
4 5 6 7
在这个例子中,这是一个满二叉树,每个节点要么没有子节点,要么有两个子节点,所有非叶节点的度都是2。满二叉树在计算机科学中常用于堆数据结构的实现,具有一些特殊的性质和应用。
在前序遍历中,对于任意节点,先访问该根节点,然后递归地对其左子树进行前序遍历,最后递归地对其右子树进行前序遍历。
以下是一个示例二叉树的前序遍历顺序(节点值用数字表示):
1 / \ 2 3 / \ / \ 4 5 6 7
前序遍历的结果为:1, 2, 4, 5, 3, 6, 7。
在这个例子中,前序遍历先访问根节点1,然后递归地对左子树进行前序遍历(2, 4, 5),最后递归地对右子树进行前序遍历(3, 6, 7)。
在中序遍历中,对于任意节点,先递归地对其左子树进行中序遍历,然后访问该节点,最后递归地对其右子树进行中序遍历。
以下是一个示例二叉树的中序遍历顺序(节点值用数字表示):
1
/ \
2 3
/ \ / \
4 5 6 7
中序遍历的结果为:4, 2, 5, 1, 6, 3, 7。
在这个例子中,中序遍历先递归地对左子树进行中序遍历(4, 2, 5),然后访问根节点1,最后递归地对右子树进行中序遍历(6, 3, 7)。
它的遍历顺序是先递归地对左子树进行后序遍历,然后递归地对右子树进行后序遍历,最后访问根节点。(左,右,根)
在后序遍历中,对于任意节点,先递归地对其左子树进行后序遍历,然后递归地对其右子树进行后序遍历,最后访问该根节点。
以下是一个示例二叉树的后序遍历顺序(节点值用数字表示):
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
后序遍历的结果为:4, 5, 2, 6, 7, 3, 1。
在这个例子中,后序遍历先递归地对左子树进行后序遍历(4, 5, 2),然后递归地对右子树进行后序遍历(6, 7, 3),最后访问根节点1。
- #include
- using namespace std;
- typedef int DadaType;
- struct Node{
- struct Node* firstChild;
- struct Node* pnextBrother
- DataType 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;
- }