数据结构——先序遍历的顺序创建二叉链表并中序遍历(C语言）

先序遍历的顺序创建二叉链表并中序遍历

1.算法步骤：

   1）扫描数字序列，读入数字n。

   2）如果n是一个 0 数字，则表明该二叉树为空树，即T=NULL;否则执行一下操作。

•  申请一个节点空间T
• 将n赋给(*T)->data
• 递归创建T的左子树
• 递归创建T的右子树

2.创建的结果图：

3.数字的输入顺序：

          1 2 3 0 0 0 4 5 0 0 6 0 0

4.C语言完整程序

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

typedef int ElemType; 
typedef struct BiNode{
	ElemType data;
	struct BiNode *leftChild,*rightChild;
}BiNode,*BiTree;

/*Function:先序遍历的顺序创建二叉链表*/
void CreateBiTree(BiTree *T){
	ElemType n;
	printf("请输入元素：\n");
	scanf("%d",&n);
	if(n==0){
		(*T)=NULL;
	}else{
		(*T)=(BiNode *)malloc(sizeof(BiNode));
		(*T)->data=n;
		CreateBiTree(&((*T)->leftChild));
		CreateBiTree(&((*T)->rightChild));
	}
}
/*Function:中序遍历二叉树的递归算法*/ 
void InOrderTraverse(BiTree T){
	if(T){
		InOrderTraverse(T->leftChild);
		printf("%d",T->data);
		InOrderTraverse(T->rightChild);
	}
} 
/*主函数*/ 
void main(){
	BiTree tree;
	printf("请输入建立二叉链表的序列：\n");
	CreateBiTree(&tree);
	printf("二叉树中序遍历为：\n");
	InOrderTraverse(tree);
}

5.程序中的指针问题：

     在程序中我们会注意到：在创建结构体时定义了结构体指针*BiTree,在CreateBiTree()方法中传入的参数是BiTree *T,没错传入的参数就是二维指针，即指向指针的指针。

     这是因为：在申请根结点空间时，地址可能会发生变化，而这种变化是无法判断的，单个指针就无法找到变化后的地址，所以 ，用指针的指针，找到变化后的地址。

6.执行结果：