二叉树的重建 二叉树的重建方法: 一、根据前序加中序遍历重建二叉树 构造该二叉树的过程如下: 1. 根据前序序列的第一个元素建立根结点; 2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列; 3. 在前序序列中确定左右子树的前序序列; 4. 由左子树的前序序列和中序序列建立左子树; 5. 由右子树的前序序列和中序序列建立右子树。 二、根据中序加后序遍历重建二叉树 构造该二叉树的过程如下: 1. 根据后序序列的最后一个元素建立根结点; 2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列; 3. 在…

2017年10月14日 0条评论 6点热度 阅读全文

二叉树的重建 二叉树的重建方法: 一、根据前序加中序遍历重建二叉树 构造该二叉树的过程如下: 1. 根据前序序列的第一个元素建立根结点; 2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列; 3. 在前序序列中确定左右子树的前序序列; 4. 由左子树的前序序列和中序序列建立左子树; 5. 由右子树的前序序列和中序序列建立右子树。 二、根据中序加后序遍历重建二叉树 构造该二叉树的过程如下: 1. 根据后序序列的最后一个元素建立根结点; 2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列; 3. 在…

2017年10月14日 0条评论 34点热度 阅读全文

二叉排序树的插入、查找、删除 二叉排序树的定义 二叉排序树右称二叉查找树。或者为空树,或者是具有以下性质: (1)若它的左子树不为空,则左子树所有节点的值小于根结点, (2)若它的右子树不为空,则根结点的值小于所有右子树结点的值 (3)它的左右子树叶分别为二叉排序树   总结起来就是根据结点的值有:左子树<根结点<右子树 如下图就是一棵二叉排序树     它的中序遍历:12、19、23、28、34、36、38、42、53、65、90,刚好是排好序的。   二叉排序…

2017年7月17日 0条评论 18点热度 阅读全文

二叉排序树的插入、查找、删除 二叉排序树的定义 二叉排序树右称二叉查找树。或者为空树,或者是具有以下性质: (1)若它的左子树不为空,则左子树所有节点的值小于根结点, (2)若它的右子树不为空,则根结点的值小于所有右子树结点的值 (3)它的左右子树叶分别为二叉排序树   总结起来就是根据结点的值有:左子树<根结点<右子树 如下图就是一棵二叉排序树     它的中序遍历:12、19、23、28、34、36、38、42、53、65、90,刚好是排好序的。   二叉排序…

2017年7月17日 0条评论 5点热度 阅读全文

完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 比如下面这棵树就是一棵完全二叉树 通过图片我们可以了解到它的创建过程是从上到下,从左至右的,也就是说,它是一层一层建立的。 完全二叉树有以下基本性质: 对于一棵有n个结点的完全二叉树,其任意结点 i (1<=i<=n),如果 i = 1, 则结点 i 是二叉树的根,无双亲; 如果 i>1,则其双亲parent(i)是结点 i/2. 如果 …

2016年11月5日 0条评论 15点热度 阅读全文

完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 比如下面这棵树就是一棵完全二叉树 通过图片我们可以了解到它的创建过程是从上到下,从左至右的,也就是说,它是一层一层建立的。 完全二叉树有以下基本性质: 对于一棵有n个结点的完全二叉树,其任意结点 i (1<=i<=n),如果 i = 1, 则结点 i 是二叉树的根,无双亲; 如果 i>1,则其双亲parent(i)是结点 i/2. 如果 …

2016年11月5日 0条评论 20点热度 阅读全文

  名词解释    树这个数据结构用到了递归的概念:树的子树还是树; 度:节点的子树个数; 树的度:树中任意节点的度的最大值; 兄弟:两节点的parent相同; 层:根在第一层,以此类推; 高度:叶子节点的高度为1,根节点高度最高; 有序树:树中各个节点是有次序的; 森林:多个树组成;   树的表示法   1.双亲表示法:每个节点存储:数据、parent在数组中的下标; 2.孩子表示法:全部节点组成一个数组,每个数组指向一个单链表,存放其孩子;如下图: 3.双亲孩子…

2012年2月26日 0条评论 19点热度 阅读全文

  名词解释    树这个数据结构用到了递归的概念:树的子树还是树; 度:节点的子树个数; 树的度:树中任意节点的度的最大值; 兄弟:两节点的parent相同; 层:根在第一层,以此类推; 高度:叶子节点的高度为1,根节点高度最高; 有序树:树中各个节点是有次序的; 森林:多个树组成;   树的表示法   1.双亲表示法:每个节点存储:数据、parent在数组中的下标; 2.孩子表示法:全部节点组成一个数组,每个数组指向一个单链表,存放其孩子;如下图: 3.双亲孩子…

2012年2月26日 0条评论 7点热度 阅读全文