UC知道二叉树的线索化是否合理？
来源：百度知道 编辑：UC知道 时间：2024/06/16 21:33:58
二叉树的线索化需要在结点里多添加2个标志指针状态的域
就算是用bool 那么一个结点也就要用2字节 还是常驻内存
线索二叉树遍历不需要栈 但是栈的最大储存量是树的深度 而储存一个指针需要4个字节
这样的话 来算算
最极端的情况 二叉树的每个结点的度都为1 有n个结点 线索化二叉树需要多发费2n个字节 使用栈需要4n个字节
但是如果是一个满二叉树 如果树的深度为k 线索化需要多发费2(2^k - 1)个字节 使用栈则需要4k个字节
线索化二叉树还需要先对二叉树进行一次遍历
貌似很不合算啊
汗 我不是讨论树是否合理 而是二叉树的线索化是否合理
二叉树的线索化吧为空的指针指向该结点的前驱或后继 使二叉树的遍历不需要使用栈
而使用栈似乎比线索化更节省空间 而且线索二叉树的里边需要O(n) 而使用栈遍历也是O(n) 似乎没有时间上的优势啊
就算是用bool 那么一个结点也就要用2字节 还是常驻内存
线索二叉树遍历不需要栈 但是栈的最大储存量是树的深度 而储存一个指针需要4个字节
这样的话 来算算
最极端的情况 二叉树的每个结点的度都为1 有n个结点 线索化二叉树需要多发费2n个字节 使用栈需要4n个字节
但是如果是一个满二叉树 如果树的深度为k 线索化需要多发费2(2^k - 1)个字节 使用栈则需要4k个字节
线索化二叉树还需要先对二叉树进行一次遍历
貌似很不合算啊
汗 我不是讨论树是否合理 而是二叉树的线索化是否合理
二叉树的线索化吧为空的指针指向该结点的前驱或后继 使二叉树的遍历不需要使用栈
而使用栈似乎比线索化更节省空间 而且线索二叉树的里边需要O(n) 而使用栈遍历也是O(n) 似乎没有时间上的优势啊
虽然说存储二叉树会花很大的空间,而且从根到某一结点的遍历也是很麻烦的,但是也有一个好处,那就是这颗树非常准确形象的,在逻辑上可以很简单的实现一些功能.其实二叉树存在内存中不也是一个空间内存单元么,就算是用一个线性表不也可以表示一颗树么,学习一下数据结构,然后再学习一下堆排序,你就会更深刻的感觉到这一点.所以不用太在意储存上的问题,主要是怎么样在已有的储存上通过怎么样的操作来完成一定的功能.