[数据结构与算法]??二叉树的创建（递归）和遍历??

二叉树的创建

二叉树的创建，是我们数据结构当中比较重要的部分，接下来我们学习一下二叉树的创建。

第一步：创建结点（节点）

? ? ? ? 结点的创建，我们一般是选择用结构体存放结点，以及结点的数据。

typedef struct treeNode
{
	char data;
	struct treeNode* lchild;//创建左结点
	struct treeNode* rchild;//创建右结点
}NODE, * LPNODE,*LPTREE;//结构体的别名

????????结构体创建结点的好处是便于我们利用指针或者链表进行数据的存放。

第二步：把数据变成结点

? ? ? ? 结点的创建是为了存放数据

LPNODE createNode(char data)
{
	LPNODE newNode = (LPNODE)malloc(sizeof(NODE));分配一个NODE类型大小的内存空间, 并把它赋给LPNODE型的变量:newNode，也是创建根结点
	newNode->data = data;
	newNode->lchild = NULL;//左结点的起始为空
	newNode->rchild = NULL;//右结点的起始为空
	return newNode;//返回根节点
}

第三步：创建树（递归创建）

//递归创建树
void createtree(LPTREE* root)
{
	char key;
	scanf("%c",&key);
	if(key=='#')
	{
		*root==NULL;
	}
	else
	{
		*root=(LPTREE)malloc(sizeof(NODE));//与上面的解释雷同
		(*root)->data=key;
		createtree(&(*root)->lchild);//递归为左子树结点赋值
		createtree(&(*root)->rchild);//递归为右子树结点赋值
	}
} 

第四步：遍历,遍历也分递归和非递归

????????递归遍历是有套路的，其实递归遍历的算法是一样的，但是就是输出语句的位置不同罢了，当然函数的名字也不能相同。

? ? ? ? （1）先序遍历

void preOrder(LPNODE root)
{
	if (root != NULL)
	{
		cout << root->data << " ";
		preOrder(root->lchild);
		preOrder(root->rchild);
	}
}

? ? ? ? ?（2）中序遍历

void midOrder(LPNODE root)
{
	if (root != NULL)
	{
		midOrder(root->lchild);
		cout << root->data << " ";
		midOrder(root->rchild);
	}
}

? ? ? ? （3）后序遍历

void lastOrder(LPNODE root)
{
	if (root != NULL)
	{
		lastOrder(root->lchild);
		lastOrder(root->rchild);
		cout << root->data << " ";
	}
}

第五步：主函数main编写

? ? ? ? 这里主要不输入数据了，用我们现成的数据。

int main()
{
	LPNODE A = createNode('A');
	LPNODE B = createNode('B');
	LPNODE C = createNode('C');
	LPNODE D = createNode('D');
	LPNODE E = createNode('E');
	LPNODE F = createNode('F');
	insertNode(A, B, C);//根左右均不为空
	insertNode(B, D, NULL);//根左不为空，右为空
	insertNode(C, E, NULL);//根左不为空，右为空
	insertNode(E, NULL, F);//根右不为空，左为空
	cout << "preOrder:\n";
	preOrder(A);

	cout << "\nmidOrder:\n";
	midOrder(A);

	cout << "\nlaseOrder:\n";
	lastOrder(A);

}

运行结果：

?