根据遍历序列确定二叉树如果二叉树中的节点各不相同,则二叉树结点的先序序列、中序序列、后序序列都是唯一的 由二叉树的先序序列和中序序列、后序序列和中序序列都能过确定唯一一颗二叉树,但是只有先序序列和后续序列不能确定二叉树。 已知先序序列和中序序列确定二叉树,分析方法:由先序序列确定根节点,由中序序列确定左右子树。 已知中序序列和后序序列确定二叉树,分析方法:由后序序列确定根节点,由中序序列确定左右子树。
哈夫曼树的构造构造哈夫曼树的口诀 构造森林全是根 选用两小造新树 删除两小添新根 重复2、3剩单根 顺序存储 哈夫曼树 存储结构 typedef struct HTNode { int weight; // 权值 int parent; // 双亲结点 int lchild; // 左子树 int rchild; // 右子树}HTNode, *HuffmanTree; 初始状态所有的结点都是独立的一棵树(根节点),parent, lchild, rchild 都是 0
二叉树的存储结构顺序存储按满二叉树的结点层次编号,依次存放二叉树中的数据元素。双亲和孩子的关系存储在编号上 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 个结点的二叉链表中,有 ___ 个指针域 三
树的遍历遍历算法分析遍历和创建树的过程都是递归的(算法思想都是递归的,就算是非递归算法仍然是按照递归思想实现的),只是按照某种遍历方式遍历子树时和访问树的方式一样。 注意子树和结点的区别 每个节点在递归调用的时候都会经过3次,不同的遍历顺序只是访问的时机不一样。 图片来自青岛大学王卓老师的PPT **先序遍历:**先访问根节点,先序遍历左子树,先序遍历右子树先序遍历左子树的时候同样是先访问根节点,再先序遍历左子树的左子树,等到第一颗左子树的所有子孙被访问完之后再先序遍历右子树。 递归算法实现Status preOrderTraverse(BiTree T) { if (T =
二叉树二叉树的定义二叉树的每个结点最多只有两个分支,结点数只可能是 0, 1, 2。 二叉树是由一个根结点和两颗互不相交的分别称作这个根的左子树和右子树的二叉树定义(递归定义),子树有顺序之分不能调换顺序。 二叉树有以下 5 种基本形态: ∅ ⚪ ⚪ ⚪ ⚪ / \ / \ ⚪ ⚪ ⚪ ⚪空二叉树 根和空的二叉树 根和左子树 根和右子树 根和左右子树 **二叉树不是树的特殊情况,它们是两个概念。**因为如果二叉树某个结点只有一个孩子结点时仍然需要区分这个结点是左孩子还是右孩子;而树的某个结点只有一个孩子结点时就
树与二叉树的转换将树转换为二叉树给定一棵树,能够得到唯一的二叉树,因为树的二叉链表表示只有一种情况。 转换方法(兄弟相连留长子) 在兄弟结点之间加一根线 对每个结点,除了其左孩子外,去除该结点与其余孩子之间的关系 然后得到的数据结构就是二叉树。 将二叉树转换为树 双亲结点和所有的左孩子的右孩子,右孩子的右孩子 … 相连接 去掉所有节点和右孩子的连线 这样就从二叉树转换为树了 是不是很简单呢 (bushi)
树树的基本术语: 节点的度:一个节点含有的子树的个数称为该节点的度; 树的度:一棵树中,最大的节点度称为树的度; 叶节点或终端节点:度为零的节点; 非终端节点或分支节点:度不为零的节点; 父亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 兄弟节点:具有相同父节点的节点互称为兄弟节点; 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推; 深度:对于任意节点n,n的深度为从根到n的唯一路径长,根的深度为0; 高度:对于任意节点n,n的高度为从n到一片树叶的最长路径长,所有树叶的高度为0;
Makefile执行过程 读取阶段 读取Makefile文件的所有内容 根据Makefile的内容再程序中建立起变量 在程序中构建起显示规则和隐式规则 建立目标和依赖之间的依赖图 目标更新阶段 用第一阶段构建起来的数据确定哪个目标需要更新然后执行对应的更新方法 变量和函数的展开如果发生再第一阶段就称作立即展开,否则称为延迟展开 Makefile 的规则target: prerequisites recipe target target 可以是一个 object file (目标文件,eg: main.o),也可以是一个可执行文件(executable file, eg: hello