不使用递归的二叉树遍历

2017-9-5 Plan C C语言

blog.kurukurumi.com原创,转载请注明出处。

E-mail:hubenchang0515@outlook.com


        使用递归可以非常轻松的实现二叉树遍历,但是递归层数非常多时会导致栈溢出,因此写了不使用递归的二叉树遍历,因为只是随手所写,质量较差,可能有错误,权当笔记,待以后修改。

/*
 *   不使用递归的二叉树遍历
 *   hubenchang0515@outlook.com
 *   blog.kurukurumi.com
 *
            (-)
          /     \
        /        \
       /          \
      /            \
     (+)          (/) 
     / \          /  \
   (a) (*)      (e) (f)
       /  \
      (b) (-)
          /  \
         (c) (d)
 */

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

typedef struct BinaryTreeNode Node;

struct BinaryTreeNode
{
	char value;

	Node* parent;
	Node* left;
	Node* right;
};


/* 创建Node */
Node* CreateNode(char value)
{
	Node* node = malloc(sizeof(Node));
	if(node != NULL)
	{
		node->parent = NULL;
		node->left = NULL;
		node->right = NULL;
		node->value = value;
	}
	
	return node;
}


/* 插入左子树 */
void InsertLeft(Node* parent, Node* left)
{
	parent->left = left;
	left->parent = parent;
}


/* 插入右子树 */
void InsertRight(Node* parent, Node* right)
{
	parent->right = right;
	right->parent = parent;
}


/* 生成一颗二叉树 */
Node* init()
{
	Node* root = CreateNode('-');
	Node* node = root;
	InsertLeft(node,CreateNode('+'));
	InsertRight(node,CreateNode('/'));
	
	node = root->left;
	InsertLeft(node, CreateNode('a'));
	InsertRight(node, CreateNode('*'));
	
	node = root->left->right;
	InsertLeft(node, CreateNode('b'));
	InsertRight(node, CreateNode('-'));
	
	node = root->left->right->right;
	InsertLeft(node, CreateNode('c'));
	InsertRight(node, CreateNode('d'));
	
	node = root->right;
	InsertLeft(node, CreateNode('e'));
	InsertRight(node, CreateNode('f'));
	
	return root;
}


/* 回调函数 */
typedef void (*Callback)(Node* node);

/* 先根遍历 */
void PreOrderTraverse(Node* root, Callback callback)
{
	Node* node = root;
	while(1)
	{
		callback(node); // 先根

		if(node->left != NULL)  // 左
		{
			node = node->left;
			continue;
		}
		
		if(node->right != NULL) // 右
		{
			node = node->right;
			continue;
		}
		
		Node* pre;
		do // 回溯
		{
			pre = node;
			node = node->parent;
			if(node == NULL)
			{
				printf("\n");
				return;
			}
		}while(node->right == pre);
		node = node->right;
	}

}


/* 中根遍历 */
void MidOrderTraverse(Node* root, Callback callback)
{
	Node* node = root;
	while(1)
	{
		while(node->left != NULL) // 左
		{
			node = node->left;
		}
		callback(node);
	
		if(node == node->parent->left)	// 中根
		{
			node = node->parent; 
			callback(node);
		}
		
		if(node->right != NULL) // 右
		{
			node = node->right;
			continue;
		}
		
		Node* pre;
		do // 回溯
		{
			pre = node;
			node = node->parent;
			if(node == NULL)
			{
				printf("\n");
				return;
			}
		}while(node->right == pre);
		callback(node);
		node = node->right;
	}
}


/* 后根遍历 */
void BakOrderTraverse(Node* root, Callback callback)
{
	Node* node = root;
	for(size_t i = 0; i < 6; i++)
	{
		while(node->left != NULL) // 左
		{
			node = node->left;
		}
		callback(node);
	
		if(node == node->parent->left)	// 右
		{
			node = node->parent;
			if(node->right != NULL)
			{
				node = node->right;
				continue;
			} 
		}

		Node* pre;
		//node = node->parent;
		do // 回溯
		{
			pre = node;
			node = node->parent;
			if(node == NULL)
			{
				printf("\n");
				return;
			}
			else if(node->right == pre)
			{
				callback(node);
			}
		}while(node->right == pre);
		node = node->right;
	}
}

/* 回调函数,打印节点的值 */
void printNode(Node* node)
{
	printf("%c",node->value);
}

int main()
{
	Node* root = init();
	PreOrderTraverse(root, printNode);
	MidOrderTraverse(root, printNode);
	BakOrderTraverse(root, printNode);
}


发表评论:

Powered by emlog
鄂ICP备16003833号