算法导论10.4-5

思路：

1、不停搜索当前节点的左孩子直到最后一个左孩子,并赋给当前节点

2、当前节点有右孩子，将右孩子设为当前节点，执行1

     若当前节点没有右孩子，将当前节点标记为last，当前节点上溯到其父节点

3、执行1前，判断当前节点左右孩子是否为last，如为last跳到2

#include <stdio.h>
#include <stdlib.h>

//typedef struct NODE *tree;
typedef struct NODE *node;

struct NODE{
	node parent;
	node left;
	node right;
	int key;

};

/*非递归遍历二叉树*/
void visit(node n){
	node last = n;
	node cur = n;

	while(cur){
		while(cur->left && cur->left != last && cur->right != last){	//左下搜索
			last = cur;
			cur = cur->left;
		}

		if(cur->right && cur->right != last){	//右孩子存在且不为last
			last = cur;
			cur = cur->right;
		}else{									//上溯
			printf("%d\n",cur->key);
			last = cur;
			cur = cur->parent;
		}
	}
}

void main(){
	struct NODE one,two,three,four,five,six,seven,eight,nine,ten;
	
	one.key = 1;
	two.key = 2;
	three.key = 3;
	four.key = 4;
	five.key = 5;
	six.key = 6;
	seven.key = 7;
	eight.key = 8;
	nine.key = 9;
	ten.key = 10;
	one.parent = NULL;
	one.left = &two;
	one .right = &three;
	two.parent = &one;
	two.left = &four;
	two.right = &five;
	three.parent = &one;
	three.left = &six;
	three.right = &seven;
	four.parent = &two;
	four.left = &eight;
	four.right = &nine;
	five.parent = &two;
	five.left = &ten;
	five.right = NULL;
	six.parent = &three;
	six.left = NULL;
	six.right = NULL;
	seven.parent = &three;
	seven.left = NULL;
	seven.right = NULL;
	eight.parent = &four;
	eight.left = NULL;
	eight.right = NULL;
	nine.parent = &four;
	nine.left = NULL;
	nine.right = NULL;
	ten.parent = &five;
	ten.left = NULL;
	ten.right = NULL;
	visit(&one);

}