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

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

1.算法步骤:

   1)扫描数字序列,读入数字n。

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

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

2.创建的结果图:

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

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.执行结果:

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

    原文作者:@cth123
    原文地址: https://blog.csdn.net/weixin_46364710/article/details/116085853
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞