如何在网站上做qq群链接,wordpress博客页修改,wordpress关闭发表评论,seo挖关键词文章目录 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. 先序遍历理论练习代码实现 2. 中序遍历理论练习代码实现 3. 后序遍历理论练习代码实现 4. 代码整合5. 答案 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. 先序遍历
理论 先序遍历Preorder Traversal根节点的访问顺序在左右子树之前。
先访问根节点然后递归地对左子树进行先序遍历最后递归地对右子树进行先序遍历。a b d e f g c
练习 答案见文末~
代码实现
void preOrderTraversal(struct Node* root) {if (root NULL) {return;}// 访问根节点printf(%c , root-data);// 递归遍历左子树preOrderTraversal(root-left);// 递归遍历右子树preOrderTraversal(root-right);
}2. 中序遍历
理论 中序遍历Inorder Traversal根节点的访问顺序在左右子树之间。
先递归地对左子树进行中序遍历然后访问根节点最后递归地对右子树进行中序遍历。d b f e g a c
练习 答案见文末~
代码实现
void inOrderTraversal(struct Node* root) {if (root NULL) {return;}// 递归遍历左子树inOrderTraversal(root-left);// 访问根节点printf(%c , root-data);// 递归遍历右子树inOrderTraversal(root-right);
}3. 后序遍历
理论 后序遍历Postorder Traversal根节点的访问顺序在左右子树之后。
先递归地对左子树进行后序遍历然后递归地对右子树进行后序遍历最后访问根节点。d f g e b c a
练习 答案见文末~
代码实现
void postOrderTraversal(struct Node* root) {if (root NULL) {return;}// 递归遍历左子树postOrderTraversal(root-left);// 递归遍历右子树postOrderTraversal(root-right);// 访问根节点printf(%c , root-data);
}4. 代码整合
#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;
}
// 先序遍历
void preOrderTraversal(struct Node* root) {if (root NULL) {return;}// 访问根节点printf(%c , root-data);// 递归遍历左子树preOrderTraversal(root-left);// 递归遍历右子树preOrderTraversal(root-right);
}// 中序遍历
void inOrderTraversal(struct Node* root) {if (root NULL) {return;}// 递归遍历左子树inOrderTraversal(root-left);// 访问根节点printf(%c , root-data);// 递归遍历右子树inOrderTraversal(root-right);
}// 后序遍历
void postOrderTraversal(struct Node* root) {if (root NULL) {return;}// 递归遍历左子树postOrderTraversal(root-left);// 递归遍历右子树postOrderTraversal(root-right);// 访问根节点printf(%c , root-data);
}
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(Rre-order traversal: \n);preOrderTraversal(root);printf(\n);// 递归中序遍历二叉树printf(In-order traversal: \n);inOrderTraversal(root);printf(\n);// 递归后序遍历二叉树printf(Post-order traversal: \n);postOrderTraversal(root);printf(\n);return 0;
}5. 答案 先序遍历 t1: a b d e f g ct2: a b d c e f g 中序遍历 t1: d b f e g a ct2: d b c a f e g 后序遍历 t1: d f g e b c at2: d c b f g e a
