手机网站注意哪些问题吗,做个网站设计多少钱,企业网站模板优化,网站制作公司成都文章目录 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. 层次遍历 5.2.5 二叉树的创建先序创建a. 算法CBTb. 代码实现 代码整合 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. 层次遍历
【数据结构】树与二叉树十一二叉树的层次遍历算法LevelOrder
5.2.5 二叉树的创建
先序遍历 a b d e f g c 中序遍历 d b f e g a c 后序遍历 d f g e b c a 层次遍历 a b c d e f g
先序创建 由二叉树的遍历很容易想到用遍历方法去创建二叉树。我们考虑从先根遍历思想出发来构造二叉树。 方法输入当前被创建结点的数据域的值如果不空申请空间用指针指向然后对数据域进行赋值再递归对该结点的左右指针域进行赋值这就是先根创建过程。当输入为空则算法返回一个空指针即空树。递归出口。
a. 算法CBT b. 代码实现
struct Node* CBT(char data[], int* index, char tostop) {char ch data[(*index)];if (ch tostop) {return NULL;} else {struct Node* t createNode(ch); t-left CBT(data, index, tostop);t-right CBT(data, index, tostop);return t;}
}代码整合
#include stdio.h
#include stdlib.hstruct 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 Node* CBT(char data[], int* index, char tostop) {char ch data[(*index)];if (ch tostop) {return NULL;} else {struct Node* t createNode(ch); t-left CBT(data, index, tostop);t-right CBT(data, index, tostop);return t;}
}
void inorderTraversal(struct Node* root) {if (root ! NULL) {inorderTraversal(root-left);printf(%c , root-data);inorderTraversal(root-right);}
}// 创建队列
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() {char tostop #;char input_data[] {a, b, d, #, #, e, f, #, #, g, #, #, c, #, #};int index 0;struct Node* root CBT(input_data, index, tostop);// 层次遍历二叉树printf(层次遍历二叉树: );levelOrder(root);printf(\n);printf(中序遍历二叉树: );inorderTraversal(root);printf(\n);return 0;
}
