Question

二叉树遍历问题

一个二叉树，节点由左child 与右child 和 parent 组成，如何在线性时间内，只使用固定空间（注意是固定，不能和节点数有关），不能修改树（哪怕是暂时的）对各个节点进行遍历。求高手解答，只要一个思想就行了，编码我自己来。

Answer 1

对于二叉链式存储的二叉树，各种遍历方式都至少得用到栈（包括递归）或者队列结构吧……
于是乎O(1)的空间有可能吗？求原题详细描述并坐等高手……

追问

详见 《算法导论（第二版）》 10.4-4

追答

那题好像没写要求固定空间……而且题目说的是多叉树的二叉存储……
该怎么遍历二叉树还怎么遍历吧。基本上怎么做都可以达到O(n)的时间复杂度。

追问

题中确实写了要求O(1)的空间复杂度，不知道是不是书的失误，算法这玩意儿，难……

追答

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.
以上原文。我不知道中文版怎么翻的。

追问

额，不好意思，说错了，是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 proce-
dure.

追答

既然是算法导论上的习题，那还是有兴趣想一想……作者肯定知道这个要怎么做
目前估计得用若干个辅助指针以及计数变量……

E.Horowitz等编著的《数据结构基础》第5章练习11可以提供一些思路，不妨找来看一下。

Answer 2

blic class BinaryTreeTest{

public static void main(String args[]){

BinaryTreeTest b=new BinaryTreeTest();

int data[]={12,11,34,45,67,89,56,43,22,98};

BinaryTree root =new BinaryTree(data[0]);

System.out.print("二叉树的中的数据： ");

for(int i=1;i data.length 1;i )

{

root.insertTree(root,data[i-1]);

System.out.print(data[i-1] ";");

}

System.out.println(data[data.length-1]);

int key=Integer.parseInt(args[0]);

if(b.searchkey(root,key))

{

System.out.println("找到了:" key);

}

else

{

System.out.println("没有找到：" key);

}

}

public boolean searchkey(BinaryTree root, int key)

{

boolean bl = false;

if (root == null)

{

bl = false;

return bl;

}

else if (root.data == key)

{

bl = true;

return bl;

}

else if (key

Answer 3

*
**由前序，和中序创建二叉树，
**由已知的二叉树，得到他的后序
**/
#includestdio.h