当前位置：首页 > news >正文

学习嵌入式第二十二天

news 2025/8/11 13:04:00

文章目录

二叉树
- 1.概念
- 2.树形结构
- 3.二叉树
- 4.二叉树的操作
- - 1.节点定义
  - 2.依赖的头文件
  - - 1.linkqueue.h(声明在栈和队列中)
    - 2.linkstack.h（声明在栈和队列中）
    - 3.btree.h
  - 3.创建完全二叉树
  - 4.二叉树深度优先遍历（递归实现）
  - 5.二叉树的广度优先遍历
  - 6.二叉树的销毁
  - 7.创建一个非完全二叉树
  - 8.获得树的高度、深度、层数
  - 9.二叉树的深度优先遍历（非递归实现）

二叉树

非线性结构

1.概念

线性结构：描述数据一对一的关系（表）
非线性结构：描述数据一对多（树），多对多（图）的关系

2.树形结构

节点：组成树形结构的一个小的单元
- 根节点：只有后继，没有前驱
- 分支节点：既有前驱，又有后继
- 叶子节点：只有前驱，没有后继
前驱（祖先）：被访问节点的上一个节点
后继（子孙）：节点后续访问的节点
层：根节点层数为1，后续节点，每层层数+1
树的层数：由最高节点对应层数表示
高度：由该节点到最远叶子节点的层数距离（节点高度自身为1）
深度：由该节点到根节点的距离（节点自身深度为1）
树的高度=树的深度=数的层数
度：后续节点个数

3.二叉树

树形结构中的所有节点度数最大为2
节点类型
- 叶子节点
- 只有左孩子
- 只有右孩子
- 左右孩子都有
满二叉树和完全二叉树
- 满二叉树
  1. 概念：所有叶子节点均在同一层，且每层节点个数均为最大值
  2. 特性
    - 第k层节点有 $2^k$
    - 前k层节点有 $2^k -1$
- 完全二叉树
  1. 概念：编号（如果节点编号为n，左孩子编号：2n，右孩子：2n+1）展开是连续的
  2. 遍历形式
    
    深度优先遍历（DFS）
    - 前序遍历（先序遍历）：分节点，左孩子，右孩子
    - 中序遍历：左孩子，分节点，右孩子
    - 后序遍历：左孩子，右孩子，分节点
    广度优先遍历（BFS）
    - 层序遍历：逐层从左到右依次遍历

4.二叉树的操作

1.节点定义

代码实现：

typedef struct tree{int num;struct tree *pleftchild;struct tree *prightchild;}treenode;

2.依赖的头文件

1.linkqueue.h(声明在栈和队列中)

#include"btree.h"extern linknode *create_empty_linkqueue(void);
extern int is_empty_linkqueue(linknode *phead);
extern int enter_linkqueue(linknode *phead, datatype tmpdata);
extern datatype quit_linkqueue(linknode *phead);
extern int destroy_linkqueue(linknode **pphead);

2.linkstack.h（声明在栈和队列中）

#include"btree.h"extern linknode *create_empty_linkstack(void);
extern int is_empty_linkstack(linknode *phead);
extern int push_linkstack(linknode *phead, datatype tmpdata);
extern datatype pop_linkstack(linknode *phead);
extern int destroy_linkstack(linknode **pphead);

3.btree.h

typedef struct tree{int num;    //编号struct tree *pleftchild;    //右子树根节点地址struct tree *prightchild;   //左子树根节点地址char data;  //数据int flag;}treenode;
/* 存放数据的类型 */
typedef treenode *datatype;/* 链表节点类型 */
typedef struct node 
{datatype data;struct node *pnext;
}linknode;extern treenode *create_complete_btree(int startnum, int endnum);
extern int preorder_btree(treenode *proot);
extern int inorder_btree(treenode *proot);
extern int postorder_btree(treenode *proot);
extern int destroy_btree(treenode *proot);
extern int levelorder_btree(treenode *proot);
extern treenode *create_btree(void);
extern int get_btree_height(treenode *proot);
extern int preorder_btree_nonrec(treenode *proot);
extern int inorder_btree_nonrec(treenode *proot);
extern int postorder_btree_nonrec(treenode *proot);

3.创建完全二叉树

通过函数递归完成完全二叉树的创建
- 申请节点空间
- 存放数据空间
- 如果存在左子树递归创建左子树
- 如果存在右子树递归创建右子树

代码实现：

treenode *create_complete_btree(int startnum,int endnum){treenode *proot = NULL;proot = malloc(sizeof(treenode));if(NULL == proot){perror("fail to malloc");return NULL;}proot->num = startnum;proot->pleftchild = NULL;proot->prightchild = NULL;if(2 * startnum <= endnum){proot->pleftchild = create_complete_btree(2 * startnum,endnum);}if(2 * startnum + 1 <= endnum){proot->prightchild = create_complete_btree(2 * startnum + 1,endnum);}return proot;}

4.二叉树深度优先遍历（递归实现）

前序遍历

代码实现：

int preorder_btree(treenode *proot){printf("%c ",proot->data);if(proot->pleftchild != NULL){preorder_btree(proot->pleftchild);   }if(proot->prightchild != NULL){preorder_btree(proot->prightchild);}return 0;
}

中序遍历

代码实现：

int inorder_btree(treenode *proot){if(proot->pleftchild != NULL){inorder_btree(proot->pleftchild);}printf("%c ",proot->data);if(proot->prightchild != NULL){inorder_btree(proot->prightchild);   }return 0;
}

后序遍历

代码实现：

int postorder_btree(treenode *proot){if(proot->pleftchild != NULL){postorder_btree(proot->pleftchild);}if(proot->prightchild != NULL){postorder_btree(proot->prightchild);}printf("%c ",proot->data);return 0;
}

5.二叉树的广度优先遍历

层序遍历

利用队列实现

根节点入队
根节点出队，左孩子入队，右孩子入队
左孩子出队，左孩子的左孩子入队，左孩子的右孩子入队
右孩子出队，右孩子的左孩子入队，右孩子的右孩子入队
…

代码实现：

int levelorder_btree(treenode *proot){linknode *ptmpnode = NULL;ptmpnode = create_empty_linkqueue();treenode *tmpdata = NULL;enter_linkqueue(ptmpnode,proot);while(!is_empty_linkqueue(ptmpnode)){tmpdata = quit_linkqueue(ptmpnode);printf("%c ",tmpdata->data);if(tmpdata->pleftchild != NULL){enter_linkqueue(ptmpnode,tmpdata->pleftchild);}if(tmpdata->prightchild != NULL){enter_linkqueue(ptmpnode,tmpdata->prightchild);}}destroy_linkqueue(&ptmpnode);return 0;
}

6.二叉树的销毁

代码实现：

int destroy_btree(treenode *proot){if(proot->pleftchild != NULL){destroy_btree(proot->pleftchild);}if(proot->prightchild != NULL){destroy_btree(proot->prightchild);}free(proot);return 0;
}

7.创建一个非完全二叉树

代码实现：

treenode *create_btree(void){char ch = 0;treenode *ptmpnode =NULL;scanf(" %c",&ch);if(ch == '#'){return NULL;}ptmpnode = malloc(sizeof(treenode));if(NULL == ptmpnode){perror("fail to malloc");return NULL;}ptmpnode->data = ch;ptmpnode->pleftchild = create_btree();ptmpnode->prightchild = create_btree();return ptmpnode;
}

8.获得树的高度、深度、层数

代码实现：

int get_btree_height(treenode *proot){int leftheight = 0;int rightheight = 0;if(NULL == proot){return 0;}leftheight = get_btree_height(proot->pleftchild);rightheight = get_btree_height(proot->prightchild);return (leftheight > rightheight ? leftheight : rightheight) + 1;
}

9.二叉树的深度优先遍历（非递归实现）

从根节点出发到叶子节点，所有左孩子入栈
出栈一个节点元素

将该节点的右孩子按照一二步循环操作，直到栈空为止

前序遍历

在入栈前打印节点数据

代码实现：

int preorder_btree_nonrec(treenode *proot){linknode *ptmpstack = NULL;treenode *ptmpnode = NULL;ptmpstack = create_empty_linkstack();ptmpnode = proot;while(1){while(ptmpnode != NULL){printf("%c ",ptmpnode->data);push_linkstack(ptmpstack,ptmpnode);ptmpnode = ptmpnode->pleftchild;}if(is_empty_linkstack(ptmpstack)){break;}ptmpnode = pop_linkstack(ptmpstack);ptmpnode = ptmpnode->prightchild;} destroy_linkstack(&ptmpstack);return 0;
}

中序遍历

在出栈时打印节点数据

代码实现：

int inorder_btree_nonrec(treenode *proot){linknode *ptmpstack = NULL;treenode *ptmpnode = NULL;ptmpstack = create_empty_linkstack();ptmpnode = proot;while(1){while(ptmpnode != NULL){push_linkstack(ptmpstack,ptmpnode);ptmpnode = ptmpnode->pleftchild;}if(is_empty_linkstack(ptmpstack)){break;}ptmpnode = pop_linkstack(ptmpstack);printf("%c ",ptmpnode->data);ptmpnode = ptmpnode->prightchild;}destroy_linkstack(&ptmpstack);return 0;
}

后序遍历

因为最后打印根节点，所以节点都需要两次入栈
第一次入栈，为了出栈时找到该节点的右孩子，找到后，将该节点和右孩子一起入栈
第二次入栈，打印该节点

代码实现：

int postorder_btree_nonrec(treenode *proot){linknode *ptmpstack = NULL;treenode *ptmpnode = NULL;ptmpstack = create_empty_linkstack();ptmpnode = proot;while(1){while(ptmpnode != NULL){ptmpnode->flag = 1;push_linkstack(ptmpstack,ptmpnode);ptmpnode = ptmpnode->pleftchild;}if(is_empty_linkstack(ptmpstack)){break;}ptmpnode = pop_linkstack(ptmpstack);if(1 == ptmpnode->flag){ptmpnode->flag = 0;push_linkstack(ptmpstack,ptmpnode);ptmpnode = ptmpnode->prightchild;}else if(0 == ptmpnode->flag){printf("%c ",ptmpnode->data);ptmpnode = NULL; // 置空，防止重复输出}}destroy_linkstack(&ptmpstack);return 0;
}