盐城高端网站制作公司,品牌设计官网,数据库和网站开发,天津百度代运营文章目录 5.2.1 二叉树二叉树性质引理5.1#xff1a;二叉树中层数为i的结点至多有 2 i 2^i 2i个#xff0c;其中 i ≥ 0 i \geq 0 i≥0。引理5.2#xff1a;高度为k的二叉树中至多有 2 k 1 − 1 2^{k1}-1 2k1−1个结点#xff0c;其中 k ≥ 0 k \geq 0 k≥0。引理5.3… 文章目录 5.2.1 二叉树二叉树性质引理5.1二叉树中层数为i的结点至多有 2 i 2^i 2i个其中 i ≥ 0 i \geq 0 i≥0。引理5.2高度为k的二叉树中至多有 2 k 1 − 1 2^{k1}-1 2k1−1个结点其中 k ≥ 0 k \geq 0 k≥0。引理5.3设T是由n个结点构成的二叉树其中叶结点个数为 n 0 n_0 n0度数为2的结点个数为 n 2 n_2 n2则有 n 0 n 2 1 n_0 n_2 1 n0n21。 满二叉树、完全二叉树定义、特点及相关证明 5.2.2 二叉树顺序存储5.2.3 二叉树链接存储5.2.4 二叉树的遍历1-3 先序、中序、后序遍历递归实现及相关练习4. 中序遍历非递归5. 后序遍历非递归6. 先序遍历非递归7. 层次遍历a. 算法LevelOrderb. 算法解读c. 时间复杂度d.代码实现levelOrdercreateenqueuedequeue 8. 代码整合 5.2.1 二叉树 二叉树是一种常见的树状数据结构它由结点的有限集合组成。一个二叉树要么是空集被称为空二叉树要么由一个根结点和两棵不相交的子树组成分别称为左子树和右子树。每个结点最多有两个子结点分别称为左子结点和右子结点。
二叉树性质
引理5.1二叉树中层数为i的结点至多有 2 i 2^i 2i个其中 i ≥ 0 i \geq 0 i≥0。
引理5.2高度为k的二叉树中至多有 2 k 1 − 1 2^{k1}-1 2k1−1个结点其中 k ≥ 0 k \geq 0 k≥0。
引理5.3设T是由n个结点构成的二叉树其中叶结点个数为 n 0 n_0 n0度数为2的结点个数为 n 2 n_2 n2则有 n 0 n 2 1 n_0 n_2 1 n0n21。
详细证明过程见前文【数据结构】树与二叉树三二叉树的定义、特点、性质及相关证明
满二叉树、完全二叉树定义、特点及相关证明
详细证明过程见前文【数据结构】树与二叉树四满二叉树、完全二叉树及其性质
5.2.2 二叉树顺序存储 二叉树的顺序存储是指将二叉树中所有结点按层次顺序存放在一块地址连续的存储空间中详见 【数据结构】树与二叉树五二叉树的顺序存储初始化插入结点获取父节点、左右子节点等
5.2.3 二叉树链接存储 二叉树的链接存储系指二叉树诸结点被随机存放在内存空间中结点之间的关系用指针说明。在链式存储中每个二叉树结点都包含三个域数据域Data、左指针域Left和右指针域Right用于存储结点的信息和指向子结点的指针详见 【数据结构】树与二叉树六二叉树的链式存储
5.2.4 二叉树的遍历
遍历Traversal是对二叉树中所有节点按照一定顺序进行访问的过程。通过遍历可以访问树中的每个节点并按照特定的顺序对它们进行处理。对二叉树的一次完整遍历可给出树中结点的一种线性排序。 在二叉树中常用的遍历方式有三种先序遍历、中序遍历和后序遍历。这三种遍历方式都可以递归地进行它们的区别在于节点的访问顺序。 在实现遍历算法时需要考虑递归终止条件和递归调用的顺序。 还可以使用迭代的方式来实现遍历算法使用栈或队列等数据结构来辅助实现。 遍历是二叉树中基础而重要的操作它为其他许多操作提供了基础如搜索、插入、删除等。
1-3 先序、中序、后序遍历递归实现及相关练习
【数据结构】树与二叉树七二叉树的遍历先序、中序、后序及其C语言实现
4. 中序遍历非递归
【数据结构】树与二叉树八二叉树的中序遍历非递归算法NIO
5. 后序遍历非递归
【数据结构】树与二叉树九二叉树的后序遍历非递归算法NPO
6. 先序遍历非递归
【数据结构】树与二叉树十二叉树的先序遍历非递归算法NPO
7. 层次遍历 层次遍历按层数由小到大即从第0层开始逐层向下同层中由左到右的次序访问二叉树的所有结点。
a. 算法LevelOrder b. 算法解读
创建一个队列Q。将指针p指向二叉树T的根节点。如果p不为空则将p入队列Q。当队列Q非空时执行以下操作 将队首元素p出队列。打印p的数据。如果p的左子节点不为空则将左子节点入队列Q。如果p的右子节点不为空则将右子节点入队列Q。 使用队列来保存待访问的节点保证按层次遍历的顺序进行访问。首先将根节点入队列然后通过循环每次从队列中取出一个节点访问该节点的数据并将其左右子节点如果存在依次入队列。这样就可以按照层次遍历的顺序逐层访问二叉树的节点。
c. 时间复杂度 这个算法的时间复杂度是O(n)其中n是二叉树中节点的数量。因为每个节点都会入队列一次出队列一次所以总的入队和出队操作次数为2n所以时间复杂度为O(n)。
d.代码实现
levelOrder
void levelOrder(struct Node* root) {if (root NULL) {return;}struct Queue* front, * rear;create(front, rear);enqueue(front, rear, root);while (front ! NULL) {struct Node* current front-node;printf(%c , current-data);if (current-left ! NULL) {enqueue(front, rear, current-left);}if (current-right ! NULL) {enqueue(front, rear, current-right);}dequeue(front);}
}
其中队列操作详解【数据结构】线性表九队列链式队列及其基本操作初始化、判空、入队、出队、存取队首元素
create
// 初始化队列
void create(struct Queue** front, struct Queue** rear) {*front *rear NULL;
}enqueue
// 入队列
void enqueue(struct Queue** front, struct Queue** rear, struct Node* node) {struct Queue* temp (struct Queue*)malloc(sizeof(struct Queue));if (temp NULL) {printf(Memory allocation failed!\n);exit(1);}temp-node node;temp-next NULL;if (*rear NULL) {*front *rear temp;return;}(*rear)-next temp;*rear temp;
}dequeue
// 出队列
void dequeue(struct Queue** front) {if (*front NULL) {return;}struct Queue* temp *front;*front (*front)-next;free(temp);
}
8. 代码整合
#include stdio.h
#include stdlib.h// 二叉树结点的定义
struct Node {char data;struct Node* left;struct Node* right;
};// 创建新结点
struct Node* createNode(char data) {struct Node* newNode (struct Node*)malloc(sizeof(struct Node));if (newNode NULL) {printf(Memory allocation failed!\n);exit(1);}newNode-data data;newNode-left NULL;newNode-right NULL;return newNode;
}// 创建队列
struct Queue {struct Node* node;struct Queue* next;
};// 初始化队列
void create(struct Queue** front, struct Queue** rear) {*front *rear NULL;
}// 入队列
void enqueue(struct Queue** front, struct Queue** rear, struct Node* node) {struct Queue* temp (struct Queue*)malloc(sizeof(struct Queue));if (temp NULL) {printf(Memory allocation failed!\n);exit(1);}temp-node node;temp-next NULL;if (*rear NULL) {*front *rear temp;return;}(*rear)-next temp;*rear temp;
}// 出队列
void dequeue(struct Queue** front) {if (*front NULL) {return;}struct Queue* temp *front;*front (*front)-next;free(temp);
}// 层次遍历二叉树
void levelOrder(struct Node* root) {if (root NULL) {return;}struct Queue* front, * rear;create(front, rear);enqueue(front, rear, root);while (front ! NULL) {struct Node* current front-node;printf(%c , current-data);if (current-left ! NULL) {enqueue(front, rear, current-left);}if (current-right ! NULL) {enqueue(front, rear, current-right);}dequeue(front);}
}int main() {// 创建一棵二叉树struct Node* root createNode(a);root-left createNode(b);root-right createNode(c);root-left-left createNode(d);root-left-right createNode(e);root-left-right-left createNode(f);root-left-right-right createNode(g);// 层次遍历二叉树printf(层次遍历二叉树: \n);levelOrder(root);printf(\n);return 0;
}
