计算二叉树的深度
2024-11-26 93 字 1 分钟

计算二叉树的深度

计算二叉树的深度 如果是空树，那么深度为 0 否则，递归计算左子树的深度 m，递归计算右子树的深度记为 n，整棵树的深度是 max(m, n) + 1 int calculateDepth(BiTree tree) { if (tree == NULL) { return 0; } else { m = calculateDepth(tree->lchild); n = calculateDepth(tree->rchild); if (m > n) return
计算二叉树节点个数
2024-11-26 74 字 1 分钟

计算二叉树节点个数

计算二叉树的结点个数 如果是空树，那么结点个数为 0 否则，整棵树结点个数 = 左子树结点个数 + 右子树结点个数 + 1 int calculateNode(BiTree tree) { if (tree == NULL) { return 0; } else { return calculateNode(tree->lchild) + calculateNode(tree->rchild) + 1; }}
复制二叉树
2024-11-26 90 字 1 分钟

复制二叉树

复制二叉树复制二叉树需要复制所有结点的值 递归实现 void copy(BiTree source, BiTree copy) { if (source == NULL) { copy = NULL; return; } else { // 分配新结点 copy = (BiTree)malloc(sizeof(BiTreeNode)); // 复制根结点的值 copy->data = source->data; // 复制左子树
建立二叉树
2024-11-26 158 字 1 分钟

建立二叉树

建立二叉树按照先序遍历序列建立二叉树的二叉链表 在这个例子中，已知一个序列不能唯一确定一棵二叉树 typedef struct BiTreeNode { int data; struct BiTreeNode *lchild; struct BiTreeNode *rchild;} *BiTree;// 一般空结点会用特殊字符表示，自己特判就行// ABC##DE#G##F###// 分别是C E G F A 的空结点BiTree preOrderCreatTree(BiTree tree) { char ch; scanf(
树的层次遍历
2024-11-26 158 字 1 分钟

树的层次遍历

树的层次遍历把树看成从上到下的 n 层，一层一层访问，每一层从左到右访问每一个节点，每一个节点只访问一次 算法设计思路：使用一个队列 将根节点入队 在队列不为空的情况下访问每一个节点，如果他有左右孩子那么都入队 typedef struct BiTreeNode { int data; struct BiTreeNode *lchild; struct BiTreeNode *rchild;} *BiTree;// 也就是所谓的 DFS 算法void levelVisit(Queue q, BiTree tree) { q.push(
根据遍历序列确定二叉树
2024-11-23 185 字 1 分钟

根据遍历序列确定二叉树

根据遍历序列确定二叉树如果二叉树中的节点各不相同，则二叉树结点的先序序列、中序序列、后序序列都是唯一的 由二叉树的先序序列和中序序列、后序序列和中序序列都能过确定唯一一颗二叉树，但是只有先序序列和后续序列不能确定二叉树。 已知先序序列和中序序列确定二叉树，分析方法：由先序序列确定根节点，由中序序列确定左右子树。 已知中序序列和后序序列确定二叉树，分析方法：由后序序列确定根节点，由中序序列确定左右子树。
哈夫曼树
2024-11-20 109 字 1 分钟

哈夫曼树

哈夫曼树的构造构造哈夫曼树的口诀 构造森林全是根 选用两小造新树 删除两小添新根 重复2、3剩单根 顺序存储 哈夫曼树 存储结构 typedef struct HTNode { int weight; // 权值 int parent; // 双亲结点 int lchild; // 左子树 int rchild; // 右子树}HTNode, *HuffmanTree; 初始状态所有的结点都是独立的一棵树（根节点），parent, lchild, rchild 都是 0
二叉树的存储结构
2024-11-20 158 字 1 分钟

二叉树的存储结构

二叉树的存储结构顺序存储按满二叉树的结点层次编号，依次存放二叉树中的数据元素。双亲和孩子的关系存储在编号上 typedef TElemType SqBiTree[100];SqBiTree bt; 缺点：深度为 k 的且只有 k 个节点的单支树需要 2^k^ - 1 的一维数组 链式存储typedef struct BiNode { TElemType data; struct BiNode *lchild; struct BiNode *rchild;} BiNode, *BiTree; quiz：在 n 个结点的二叉链表中，有 ___ 个指针域 三
树的遍历
2024-11-20 670 字 2 分钟

树的遍历

树的遍历遍历算法分析遍历和创建树的过程都是递归的（算法思想都是递归的，就算是非递归算法仍然是按照递归思想实现的），只是按照某种遍历方式遍历子树时和访问树的方式一样。 注意子树和结点的区别 每个节点在递归调用的时候都会经过3次，不同的遍历顺序只是访问的时机不一样。 图片来自青岛大学王卓老师的PPT **先序遍历：**先访问根节点，先序遍历左子树，先序遍历右子树先序遍历左子树的时候同样是先访问根节点，再先序遍历左子树的左子树，等到第一颗左子树的所有子孙被访问完之后再先序遍历右子树。 递归算法实现Status preOrderTraverse(BiTree T) { if (T =
树与二叉树的转换
2024-11-18 176 字 1 分钟

树与二叉树的转换

树与二叉树的转换将树转换为二叉树给定一棵树，能够得到唯一的二叉树，因为树的二叉链表表示只有一种情况。 转换方法（兄弟相连留长子） 在兄弟结点之间加一根线 对每个结点，除了其左孩子外，去除该结点与其余孩子之间的关系 然后得到的数据结构就是二叉树。 将二叉树转换为树 双亲结点和所有的左孩子的右孩子，右孩子的右孩子 … 相连接 去掉所有节点和右孩子的连线 这样就从二叉树转换为树了 是不是很简单呢 (bushi)
backtop