“Threaded binary tree”的意思、由来-开放百科全书

词条

Threaded binary tree

释义

Definition
Motivation
Relation to Parent pointers
Types of threaded binary trees
The array of Inorder traversal
Example
Null link
Non recursive Inorder traversal for a Threaded Binary Tree
Algorithm
References
External links

In computing, a threaded binary tree is a binary tree variant that facilitates traversal in a particular order (often the same order already defined for the tree).

An entire binary sort tree can be easily traversed in order of the main key, but given only a pointer to a node, finding the node which comes next may be slow or impossible. For example, leaf nodes by definition have no descendants, so no other node can be reached given only a pointer to a leaf node -- of course that includes the desired "next" node. A threaded tree adds extra information in some or all nodes, so the "next" node can be found quickly. It can also be traversed without recursion and the extra storage (proportional to the tree's depth) that requires.

Definition

A threaded binary tree defined as follows:

"A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node."^[1]

This definition assumes the traversal order is the same as in-order traversal of the tree. However, pointers can instead (or in addition) be added to tree nodes, rather than replacing existing nulls. The linked lists thus defined are also commonly called "threads", and can be used to enable traversal in any order(s) desired. For example, a tree whose nodes represent information about people might be sorted by name, but have extra threads allowing quick traversal in order of birth date, weight, or any other known characteristic.

Motivation

Trees, including (but not limited to) binary search trees, can be used to store items in a particular order, such as the value of some property stored in each node, often called a key. One useful operation on such a tree is traversal: visiting all the items in order of the key.

A simple recursive traversal algorithm that visits each node of a BST is the following. Assume {{mvar|t}} is a pointer to a node, or {{math|nil}}. "Visiting" {{mvar|t}} can mean performing any action on the node {{mvar|t}} or its contents.

Algorithm traverse({{mvar|t}}):

Input: a pointer {{mvar|t}} to a node (or {{math|nil}})
If {{math|t {{=}} nil}}, return.
Else:
- traverse(left-child({{mvar|t}}))
- Visit {{mvar|t}}
- traverse(right-child({{mvar|t}}))

One problem with this algorithm is that, because of its recursion, it uses stack space proportional to the height of a tree. If the tree is fairly balanced, this amounts to {{math|O(log n)}} space for a tree containing {{mvar|n}} elements. In the worst case, when the tree takes the form of a chain, the height of the tree is {{mvar|n}} so the algorithm takes {{math|O(n)}} space. A second problem is that all traversals must begin at the root when nodes have pointers only to their children. It is common to have a pointer to a particular node, but that is not sufficient to get back to the rest of the tree unless extra information is added, such as thread pointers.

In this approach, it may not be possible to tell whether the left and/or right pointers in a given node actually point to children, or are a consequence of threading. If the distinction is necessary, adding a single bit to each node is enough to record it.

In 1968, Donald Knuth asked whether a non-recursive algorithm for in-order traversal exists, that uses no stack and leaves the tree unmodified. One of the solutions to this problem is tree threading, presented by J. H. Morris in 1979.^[2]^[3]

Relation to Parent pointers

Another way to achieve similar goals is to include a pointer in every node, to that node's parent node. Given that, the "next" node can always be reached. "right" pointers are still null whenever there are no right children. To find the "next" node from a node whose right pointer is null, walk up through "parent" pointers until reaching a node whose right pointer is not null, and is not the child you just came up from. That node is the "next" node, and after it come its descendants on the right.

It is also possible to discover the parent of a node from a threaded binary tree, without explicit use of parent pointers or a stack, although it is slower. To see this, consider a node k with right child r. Then the left pointer of r must be either a child or a thread back to k. In the case that r has a left child, that left child must in turn have either a left child of its own or a thread back to k, and so on for all successive left children. So by following the chain of left pointers from r, we will eventually find a thread pointing back to k. The situation is symmetrically similar when q is the left child of p—we can follow q's right children to a thread pointing ahead to p.

Types of threaded binary trees

Single Threaded: each node is threaded towards either the in-order predecessor or successor (left or right).
Double threaded: each node is threaded towards both the in-order predecessor and successor (left and right).

In Python:

def parent(node):

    if node is node.tree.root:        return None    else:        x = node        y = node        while True:            if is_thread(y):                p = y.right                if p is None or p.left is not node:                    p = x                    while not is_thread(p.left):                        p = p.left                    p = p.left                return p            elif is_thread(x):                p = x.left                if p is None or p.right is not node:                    p = y                    while not is_thread(p.right):                        p = p.right                    p = p.right                return p            x = x.left            y = y.right

The array of Inorder traversal

Threads are reference to the predecessors and successors of the node according to an inorder traversal.

Inorder of the threaded tree is ABCDEFGHI, the predecessor of E is D, the successor of E is F.

Example

Let's make the Threaded Binary tree out of a normal binary tree

The INORDER traversal for the above tree is—D B A E C. So, the respective Threaded Binary tree will be --

Null link

In an m-way threaded binary tree with n nodes, there are n*m - (n-1) void links.

Non recursive Inorder traversal for a Threaded Binary Tree

As this is a non-recursive method for traversal, it has to be an iterative procedure; meaning, all the steps for the traversal of a node have to be under a loop so that the same can be applied to all the nodes in the tree.

We will consider the INORDER traversal again. Here, for every node, we'll visit the left sub-tree (if it exists) first (if and only if we haven't visited it earlier); then we visit (i.e. print its value, in our case) the node itself and then the right sub-tree (if it exists). If the right sub-tree is not there, we check for the threaded link and make the threaded node the current node in consideration. Please, follow the example given below.

Algorithm

Step-1: For the current node check whether it has a left child which is not there in the visited list. If it has then go to step-2 or else step-3.

Step-2: Put that left child in the list of visited nodes and make it your current node in consideration. Go to step-6

Step-3: Print the node and If the node has the right child then go to step 4 else go to step 5

Step-4: Make the right child as the current node.

Step-5: if there is a thread node then make it the current node.

Step-6: if all nodes have been printed then END else go to step 1

Li
step-1	'A' has a left child i.e. B, which has not been visited. So, we put B in our "list of visited nodes" and B becomes our current node in consideration.	B
step-2	'B' also has a left child, 'D', which is not there in our list of visited nodes. So, we put 'D' in that list and make it our current node in consideration.	B D
step-3	'D' has no left child, so we print 'D'. Then we check for its right child. 'D' has no right child and thus we check for its thread-link. It has a thread going till node 'B'. So, we make 'B' as our current node in consideration.	B D	D
step-4	'B' certainly has a left child but its already in our list of visited nodes. So, we print 'B'. Then we check for its right child but it doesn't exist. So, we make its threaded node (i.e. 'A') as our current node in consideration.	B D	D B
step-5	'A' has a left child, 'B', but it is already there in the list of visited nodes. So, we print 'A'. Then we check for its right child. 'A' has a right child, 'C' and it's not there in our list of visited nodes. So, we add it to that list and we make it our current node in consideration.	B D C	D B A
step-6	'C' has 'E' as the left child and it's not there in our list of visited nodes even. So, we add it to that list and make it our current node in consideration.	B D C E	D B A
step-7	and finally.....	D B A E C

References

1. ^Van Wyk, Christopher J. Data Structures and C Programs, Addison-Wesley, 1988, p. 175. {{ISBN|978-0-201-16116-8}}.
2. ^{{Cite journal | doi = 10.1016/0020-0190(79)90068-1| title = Traversing binary trees simply and cheaply| journal = Information Processing Letters| volume = 9| issue = 5| year = 1979| last1 = Morris | first1 = Joseph H.}}
3. ^{{cite journal |title=Morris' tree traversal algorithm reconsidered |first1=Prabhaker |last1=Mateti and |first2=Ravi |last2=Manghirmalani |year=1988 |journal=Science of Computer Programming |volume=11 |pages=29–43 |doi=10.1016/0167-6423(88)90063-9}}

External links

Tutorial on threaded binary trees
GNU libavl 2.0.2, Section on threaded binary search trees

3 : Articles with example Python code|Binary trees|Search trees

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。