深圳专业网站制作技术,wordpress站点自动推送,培训学校加盟,蛟河市建设局网站文章目录 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. 中序遍历非递归a. 算法NIOb. 算法解读c. 典例剖析d.代码实现 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-3 先序、中序、后序遍历递归实现及相关练习
【数据结构】树与二叉树七二叉树的遍历先序、中序、后序及其C语言实现
中序遍历递归实现
void inOrderTraversal(struct Node* root) {if (root NULL) {return;}// 递归遍历左子树inOrderTraversal(root-left);// 访问根节点printf(%c , root-data);// 递归遍历右子树inOrderTraversal(root-right);
}4. 中序遍历非递归
a. 算法NIO b. 算法解读 NIO算法利用了一个辅助堆栈S来模拟递归过程中的函数调用栈。通过在循环中不断将左子节点入栈然后处理栈顶节点并将指针移动到右子节点实现了中序遍历的非递归算法。
创建一个空堆栈S并将指针p指向树的根节点t。进入循环只要p不为空执行以下步骤 a. 将p入栈S。 b. 将p指向其左子节点p Left( p )。如果堆栈S为空则结束算法。从堆栈S中弹出栈顶元素并将p指向弹出的节点。打印p节点的值。将p指向p的右子节点p Right( p )。跳转到步骤2继续循环。 该算法的时间复杂度为O(n)其中n是二叉树中节点的数量。因为每个节点都会被访问一次且入栈一次所以算法的时间复杂度与节点数量成正比。 这个非递归中序遍历算法可以应用于需要遍历二叉树并按照中序顺序访问节点的场景例如在构建二叉树的线索化结构时或者需要按照中序顺序遍历二叉搜索树等情况下。
c. 典例剖析 d.代码实现
void nonRecursiveInOrder(struct Node* root) {struct Node* stack[100]; // 辅助堆栈用于模拟递归调用栈int top -1; // 栈顶指针struct Node* current root;while (current ! NULL || top ! -1) {// 将当前结点的左子结点入栈while (current ! NULL) {stack[top] current;current current-left;}// 弹出栈顶结点并访问current stack[top--];printf(%c , current-data);// 处理右子结点current current-right;}
}
5. 代码整合
#include stdio.h
#include stdlib.h// 二叉树结点的定义
struct Node {char data;struct Node* left;struct Node* right;
};// 创建新结点
struct Node* createNode(int 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 inOrderTraversal(struct Node* root) {if (root NULL) {return;}// 递归遍历左子树inOrderTraversal(root-left);// 访问根节点printf(%c , root-data);// 递归遍历右子树inOrderTraversal(root-right);
}// 非递归中序遍历
void nonRecursiveInOrder(struct Node* root) {struct Node* stack[100]; // 辅助堆栈用于模拟递归调用栈int top -1; // 栈顶指针struct Node* current root;while (current ! NULL || top ! -1) {// 将当前结点的左子结点入栈while (current ! NULL) {stack[top] current;current current-left;}// 弹出栈顶结点并访问current stack[top--];printf(%c , current-data);// 处理右子结点current current-right;}
}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(Recursive In-order traversal: \n);inOrderTraversal(root);printf(\n);// 非递归中序遍历二叉树printf(Non-recursive In-order traversal:\n);nonRecursiveInOrder(root);printf(\n);return 0;
}
