二叉樹建構和三種周遊算法實作等【資料結構-朱戰立】

/*2018年8月19日 16:55:56*/
/*建構一個二叉樹函數*/
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef char DataType;
typedef struct tree{

	DataType data;
	struct tree *left;
	struct tree *right;
}TreeNode;


/*二叉樹初始化函數*/
void TreeInit(TreeNode **root)
{
	if ((*root=(TreeNode *)malloc(sizeof(TreeNode)))==NULL)
	{
		printf("-error-");
		getchar();
		exit(1);
	}
	(*root)->left = NULL;
	(*root)->right = NULL;
}

/*二叉樹左子節點插入*/
int *TreeLeftNode(TreeNode *pLeft, DataType x)
{
	TreeNode *pre, *temp;

	if (pLeft==NULL)
	{
		return NULL;
	}

	temp = pLeft->left;  //儲存原節點的左子樹指針
	pre = (TreeNode*)malloc(sizeof(TreeNode));//開辟pre的記憶體空間
	pre->data = x;      //将數字插入節點資料儲存中
	pre->left = temp;//将原樹的左子樹指針指派給新節點的左子樹指針
	pre->right = NULL; //将新節點右子樹設為空；

	pLeft->left = pre; //新節點成為左子樹；
	return pLeft->left;  //2018年8月19日 21:03:12  傳回左子樹指針
}


/*二叉樹右子節點插入*/
int *TreeRightNode(TreeNode *pRight, DataType x)
{
	TreeNode *pre, *temp;

	if (pRight == NULL)
	{
		return NULL;
	}

	temp = pRight->right;
	pre = (TreeNode*)malloc(sizeof(TreeNode));//開辟pre的記憶體空間
	pre->data = x;
	pre->right = temp;

	pre->left = NULL;
	pRight->right = pre;
	return pRight->right;   //2018年8月19日 21:02:49  傳回右子樹指針
}


/*二叉樹左子節點删除*/
int *TreeLeftDel(TreeNode *dLeft)
{
	if (dLeft==NULL||dLeft->left==NULL)
	{
		return NULL;
	}
	free(dLeft->left);
	dLeft->left = NULL;
	return dLeft;
}

/*二叉樹右子節點删除*/
int *TreeRightDel(TreeNode *dright)
{
	if (dright==NULL||dright->right==NULL)
	{
		return NULL;
	}
	free(dright->right);
	dright->right = NULL;
	return dright;
}


/*遞歸撤銷連結清單的函數*/
void Destroy(TreeNode **tree)
{
	if ((*tree) != NULL && (*tree)->left != NULL)
	{
		Destroy(&(*tree)->left);
	}
	if ((*tree) != NULL && (*tree)->right != NULL)
	{
		Destroy(&(*tree)->right);
	}
	free(*tree);
}

/*通過遞歸實作周遊*/
void Visit(DataType item)
{
	printf("%c->",item);
}

/*前序周遊*/
void FrontOrder(TreeNode *tree, void Visit(DataType item))
{
	if (tree!=NULL)
	{
		Visit(tree->data);
		FrontOrder(tree->left, Visit);
		FrontOrder(tree->right, Visit);
	}
}

/*中序周遊*/
void BetweenOrder(TreeNode *tree, void Visit(DataType item))
{
	if (tree!=NULL)
	{
		BetweenOrder(tree->left, Visit);
		Visit(tree->data);
		BetweenOrder(tree->right, Visit);
	}
}

/*後續周遊*/
void LastOrder(TreeNode *tree, void Visit(DataType item))
{
	if (tree != NULL)
	{
		BetweenOrder(tree->left, Visit);
		BetweenOrder(tree->right, Visit);
		Visit(tree->data);
	}
}

/*列印函數*/
void PrintBiTree(TreeNode *tree, int num) //其中num是層數
{
	int i;
	if (tree==NULL)
	{
		return;
	}
	PrintBiTree(tree->right, num + 1);
	/*通路根節點*/
	for ( i = 0; i < num-1; i++)
	{
		printf("   ");
	}
	if (num>0)
	{
		printf("----");
		printf("%c\n", tree->data);
	}
	PrintBiTree(tree->left, num + 1);
}

/*二叉樹查找函數*/
TreeNode *Serach(TreeNode *tree, DataType x)
{
	TreeNode *pre;

	if (tree==NULL)
	{
		return NULL;
	}
	if (tree->data==x)
	{
		return tree;
	}
	if (tree->left!=NULL)
	{
		pre=Serach(tree->left, x);
		if (pre!=NULL)
		{
			return pre;
		}
	}
	if (tree->right != NULL)
	{
		pre=Serach(tree->right, x);
		if (pre != NULL)
		{
			return pre;
		}
	}
	return NULL;
}

/*主函數*/

int main()
{
	TreeNode *root,*p,*pp;

	TreeInit(&root);
	p = TreeLeftNode(root, 'A');
	p = TreeLeftNode(p, 'B');
	p = TreeLeftNode(p, 'D');
	p = TreeRightNode(p, 'G');
	p = TreeRightNode(root->left, 'C');
	pp = p;
	TreeLeftNode(p, 'E');
	TreeRightNode(pp, 'F');

	PrintBiTree(root, 0);

	printf("前序周遊:\n");
	FrontOrder(root->left, Visit);
	printf("\n中序周遊:\n");
	BetweenOrder(root->left, Visit);
	printf("\n後序周遊:\n");
	LastOrder(root->left, Visit);

	Destroy(&root);  //2018年8月19日 20:40:34 注意這裡輸出型
	printf("\n");
	system("pause");
	return 0;
}