二叉树上的预排序遍历与深度优先搜索相同吗?
在我看来，前序遍历和 DFS 与我们以深度方式遍历到叶节点的两种情况相同.如果我错了，有人可以纠正我吗? 提前致谢！ 解决方案 预购是 DFS 的一种. 深度优先遍历有前序、中序和后序三种. 查看此处了解更多信息.
..
binary-tree相关内容
将二叉树转换为链表，广度优先，常量存储/破坏性
这不是作业，我不需要回答它，但现在我已经迷上了:) 问题是: 设计一种算法，以广度优先的方式将二叉树破坏性地展平为链表.好吧，很简单.只需建立一个队列，然后做您必须做的事情. 这就是热身.现在，用常量存储来实现它(递归，如果你能用它找出答案，就是对数存储，而不是常量). 大约一年前我在网上找到了解决这个问题的方法，但现在我忘记了，我想知道:) 据我所知，这个技巧涉及使用树
..
只有一个节点的树的高度
根据维基百科， 树的高度是从根到树的路径的长度树中最深的节点.一棵只有一个节点的(有根的)树(root) 的高度为零(或一). 我不明白 - 它是零还是一(或两者)? 解决方案 这只是您对二叉树高度的递归描述所做的假设.您可以考虑仅由高度为 0 或高度为 1 的节点组成的树. 如果你真的想以某种方式考虑它，你可以这样想 如果您将高度视为边数，则为 0(因此单个节点没
..
Haskell:二叉树深度的尾递归版本
首先，我有两种不同的实现，我认为它们是正确的，并且对它们进行了分析并认为它们具有相同的性能: depth::Tree a ->整数深度 空 = 0深度(分支 b l r)= 1 + 最大(深度 l)(深度 r)depthTailRec::Tree a ->整数depthTailRec = depthTR 0 其中depthTR d 空 = ddepthTR d (Branch b l r) =
..
打印二叉树中的所有根到叶路径
我正在尝试使用 java 打印二叉树中的所有根到叶路径. public void printAllRootToLeafPaths(Node node,ArrayList path){如果(节点==空){返回;}路径.添加(节点.数据)；if(node.left==null && node.right==null){System.out.println(路径);返回;}别的{printAllRoo
..
将排序后的数组插入二叉搜索树
我想实现一种算法，将排序的数组插入到二叉搜索树中，但我不希望以只向一侧生长的树结束. 你有什么想法吗? 谢谢. 解决方案 这应该会给你一个平衡的树(在 O(n) 中): 为数组中的中间元素构造一个节点并返回它 (这将是基本情况下的根). 从数组左半部分的 1. 开始重复，将返回值分配给根的左子节点. 在数组的右半部分从 1. 开始重复，将返回值分配给根的右孩子.
..
使用预序和中序字符串确定一棵二叉树是否是另一棵二叉树的子树
我想找出二叉树T2是否是二叉树T1的子树.我读到可以使用前序和中序遍历为 T2 和 T1 构建字符串表示，如果 T2 字符串是 T1 字符串的子字符串，则 T2 是 T1 的子树. 我对这种方法有点困惑，不确定它的正确性. 来自维基:“树 T 的子树是由 T 中的一个节点及其在 T 中的所有后代组成的树." 在下面的例子中: T2:1/\2 3T1:1/\2 3\4 如果我们
..
代表树的对象
在 C#(或 .net)中是否有任何对象表示二叉树(或出于好奇)和 n 叉树? 我不是在谈论表示树控件，而是作为模型对象. 如果没有，有没有好的外部实现? 解决方案 NGenerics 项目是一个很棒的数据结构和算法集合，包括二叉树. 公共类 BinaryTree:IVisitableCollection，ITree{//方法public void Add(Bin
..
使用“N"个节点，可能有多少种不同的二叉和二叉搜索树?
对于二叉树:无需考虑树节点值，我只对具有“N"个节点的不同树拓扑感兴趣. 对于二叉搜索树:我们必须考虑树节点值. 解决方案 我推荐这篇文章 由我的同事尼克·帕兰特 (Nick Parlante) 撰写(从他还在斯坦福大学的时候开始).结构不同的二叉树的计数(问题 12)有一个简单的递归解决方案(封闭形式最终是@codeka 的答案已经提到的加泰罗尼亚公式). 我不确定结构不同的
..
在 Ocaml 中查找树深度的尾递归函数
我有一个类型 tree 定义如下 type 'a tree = 'a 的叶子 |'a * 'a tree * 'a tree的节点;; 我有一个函数来查找树的深度，如下所示 let rec depth = function|叶 x ->0|节点(_，左，右)->1 +(最大(左侧深度)(右侧深度));; 这个函数不是尾递归的.有没有办法以尾递归的方式编写这个函数? 解决方案 您可以
..
将二叉树转换为链表
我正在尝试从二叉树创建一个链表. 问题是，是否可以使用简单链表而不是双向链表? 我试过了: typedef struct arvbin* ABin;typedef struct arvbin{整数值；AB 对;ABin 离开了；} arvb;typedef 结构体列表{整数值；结构 slist* 下一个；} *SList;void preorder(ABin 树，SList *l){
..
C链表在末尾插入节点
我在 C 中插入链表的方法遇到了一些问题.它似乎只在列表的开头添加.我所做的任何其他插入都失败了.这个 CodeBlocks 调试器太难理解了，我还是不明白.它从来没有给我价值，只是内存中的地址.无论如何，这是我的职责.你看到它失败的任何原因了吗? /* 在链表末尾添加新节点的函数 */int addNodeBottom(int val, 节点 *head){//创建新节点节点 *newNode
..
二叉树 vs. 链表 vs. 哈希表
我正在为我正在处理的项目构建一个符号表.我想知道人们对可用于存储和创建符号表的各种方法的优缺点有何看法. 我进行了大量搜索，最常推荐的是二叉树、链表或哈希表.以上所有的优点和/或缺点是什么?(在 C++ 中工作) 解决方案 您的用例大概是“插入数据一次(例如，应用程序启动)，然后执行大量读取，但很少(如果有的话)额外插入". 因此，您需要使用一种快速查找所需信息的算法.
..
用 O(1) 辅助空间迭代二叉树
是否可以在 O(1) 辅助空间(不使用堆栈、队列等)中迭代二叉树，或者这是否已被证明是不可能的?如果可以，怎么做? 编辑:如果有指向父节点的指针很有趣，我得到的关于这可能的回答很有趣，我不知道这可以完成，但取决于你如何看待它，这可能是 O(n) 辅助空间.此外，在我的实际用例中，没有指向父节点的指针.从现在开始，请在回答时假设这一点. 解决方案 天哪，我必须从 Knuth 那里实际输
..
如何创建一个二叉树
我不是说二叉搜索树. 例如，如果我将值 1,2,3,4,5 插入到二叉搜索树中，中序遍历将给出1,2,3,4,5 作为输出. 但是如果我将相同的值插入到二叉树中，中序遍历应该给出4,2,5,1,3 作为输出. 可以使用动态数组创建二叉树，其中对于索引 n 中的每个元素，2n+1 和 2n+2 分别代表它的左孩子和右孩子. 因此表示和层序遍历在这里非常容易. 但我认为，
..
计算二叉搜索树高度的最佳方法?(平衡 AVL 树)
我正在寻找在 AVL-tree 中计算节点余额的最佳方法.我以为我可以正常工作，但是在进行了大量插入/更新之后，我可以看到它无法正常工作(根本无法正常工作). 这是一个两部分的问题，第一部分是如何计算子树的高度，我知道定义“节点的高度是最长向下路径的长度到那个节点的叶子." 我理解它，但我未能实现它.更让我困惑的是，这句话可以在维基百科的树高上找到“通常，值 -1 对应于没有节点的子树，而零
..
何时使用前序、后序和中序二叉搜索树遍历策略
我最近意识到，虽然在我的生活中使用了大量的 BST，但我什至从未考虑过使用中序遍历以外的任何东西(虽然我知道并知道调整程序以使用 pre/post-order遍历). 意识到这一点后，我拿出了一些旧的数据结构教科书，并寻找前序和后序遍历的有用性背后的推理 - 不过他们并没有说太多. 什么时候实际使用前序/后序的例子有哪些?什么时候比按顺序更有意义? 解决方案 何时使用 Pre-
..
垂直打印一棵树
要了解什么是相同的垂直线，我们需要先定义水平距离.如果两个节点具有相同的水平距离 (HD)，则它们在同一条垂直线上.高清的想法很简单.根的HD为0，右边缘(连接到右子树的边缘)被认为是+1水平距离，左边缘被认为是-1水平距离.例如，在下面的树中，节点 4 的 HD 为 -2，节点 2 的 HD 为 -1，5 和 6 的 HD 为 0，节点 7 的 HD 为 +2. 示例: 1/\2 3/
..
查找二叉堆的最后一个元素
引用维基百科: 完全可以接受使用传统二叉树数据结构实现一个二叉堆.有寻找相邻的问题最后一层的元素添加元素时的二元堆可以解决算法上... 关于这种算法如何工作的任何想法? 我无法找到有关此问题的任何信息，因为大多数二进制堆都是使用数组实现的. 感谢任何帮助. 最近，我注册了一个 OpenID 帐户，但无法编辑我的初始帖子或评论答案.这就是我通过这个答案做出回应的原因.对
..
如果有三元搜索，为什么要使用二分搜索?
我最近听说过三元搜索，我们将数组分成 3 部分并进行比较.这里会有两个比较，但它将数组减少到 n/3.为什么人们不使用这么多? 解决方案 实际上，人们确实将 k-ary 树用于任意 k. 然而，这是一种权衡. 要在 k-ary 树中查找元素，您需要进行 k*ln(N)/ln(k) 运算(记住基数变化公式).您的 k 越大，您需要的整体操作就越多. 您所说的逻辑扩展是“为什
..