Skip to content

Latest commit

 

History

History
158 lines (128 loc) · 5.18 KB

10.4.md

File metadata and controls

158 lines (128 loc) · 5.18 KB
Raw

Exercises 10.4-1

Draw the binary tree rooted at index 6 that is represented by the following fields.

index key left right
1 12 7 3
2 15 8 NIL
3 4 10 NIL
4 10 5 9
5 2 NIL NIL
6 18 1 4
7 7 NIL NIL
8 14 6 2
9 21 NIL NIL
10 5 NIL NIL

Answer

Exercises 10.4-2

Write an O(n)-time recursive procedure that, given an n-node binary tree, prints out the key of each node in the tree.

Answer

前序，中序和后序遍历.

Exercises 10.4-3

Write an O(n)-time nonrecursive procedure that, given an n-node binary tree, prints out the key of each node in the tree. Use a stack as an auxiliary data structure.

Answer

这些题目都出现在leetcode上.

pre-order solution

in-order solution

post-order solution

Exercises 10.4-4

Write an O(n)-time procedure that prints all the keys of an arbitrary rooted tree with n nodes, where the tree is stored using the left-child, right-sibling representation.

Answer

PROCEDURE(root):
	if root != NULL
		PRINT root->key
	if(root->child)
		PROCEDURE(root->child)
	if(root->sibling)
		PROCEDURE(root->sibling)

Exercises 10.4-5

Write an O(n)-time nonrecursive procedure that, given an n-node binary tree, prints out the key of each node. Use no more than constant extra space outside of the tree itself and do not modify the tree, even temporarily, during the procedure.

Answer

if we don't use stack, then we must keep new attribute parent in node. The function of parent attribute is similar as the stack which help us to find the prev node.

如果不用stack,那么每个node必须要有parent属性.stack的作用其实是依路径保存parent节点.

PROCEDURE(root):
	prev = NULL;

	while root != NULL:
    	if prev == root->parent:
        	print root->key
        	root = root->left  ? root->left :
               	   root->right ? root->right : root->parent;
    	else if prev == root->left && root->right != NULL:
        	prev = root;
        	root = root -> right;
    	else:
        	prev = root;
        	root = root -> parent;

see my implementation

Exercises 10.4-6

The left-child, right-sibling representation of an arbitrary rooted tree uses three pointers in each node: left-child, right-sibling, and parent. From any node, its parent can be reached and identified in constant time and all its children can be reached and identified in time linear in the number of children. Show how to use only two pointers and one boolean value in each node so that the parent of a node or all of its children can be reached and identified in time linear in the number of children.

Answer

很简单,去掉parent指针,新增一个表示是否是最后一个儿子的bool值，如果是最后一个,那么next指向parent,否则next指向下一个兄弟节点.

Follow @louis1992 on github to help finish this task.