为什么二叉树的节点仅具有父级到子级的链接? [英] Why nodes of a binary tree have links only from parent to children?

问题描述

为什么二叉树的节点仅具有父级到子级的链接?我知道那里有线程二叉树，但是很难实现.具有两个链接的二叉树将允许迭代遍历两个方向，而无需堆栈或队列.

Why nodes of a binary tree have links only from parent to children? I know tha there is threaded binary tree but those are harder to implement. A binary tree with two links will allow traversal in both directions iteratively without a stack or queue.

我不知道任何这样的设计.如果有的话，请告诉我.

I do not know of any such design. If there is one please let me know.

Edit1:让我想到一个问题.我想遍历而无需递归并且不使用堆栈或队列形式的额外内存.

Let me conjure a problem for this. I want to do traversal without recursion and without using extra memory in form of stack or queue.

PS:恐怕我会因为这个愚蠢的问题而感到沮丧和沮丧.

PS: I am afraid that I am going to get flake and downvotes for this stupid question.

推荐答案

有些二叉树确实要求孩子跟上他们的父母，甚至是他们的祖父母，例如八角树.但是，这仅是为了平衡或扩展树.我们只从父级到子级遍历一棵树的原因是，我们通常在搜索特定的节点，并且只要执行二叉树使得所有左子级小于父级，而所有右级子大于与父节点相反(反之亦然)，我们只需要一个方向的链接即可找到该节点.我们从根开始搜索，然后向下迭代，如果该节点在树中，则可以保证找到它.如果我们从叶子开始，则无法保证我们可以通过返回到根来找到想要的节点.我们之所以没有从孩子到父母的链接，是因为搜索是不必要的.希望这会有所帮助.

Some binary trees do require children to keep up with their parent, or even their grandparent, e.g. Splay Trees. However this is only to balance or splay the tree. The reason we only traverse a tree from the parent to the children is because we are usually searching for a specific node, and as long as the binary tree is implemented such that all left children are less than the parent, and all right children are greater than the parent (or vice-versa), we only need links in one direction to find that node. We start the search at the root and then iterate down, and if the node is in the tree, we are guaranteed to find it. If we started at a leaf, there is no guarantee we would find the node we want by going back to the root. The reason we don't have links from the child to the parent is because it is unnecessary for searches. Hope this helps.

这篇关于为什么二叉树的节点仅具有父级到子级的链接?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！