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

青旅半醒 2023-01-16 06:22 115阅读 0赞

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

--------------------

**1.算法步骤：**

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

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

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

**2.创建的结果图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjM2NDcxMA_size_16_color_FFFFFF_t_70][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjM2NDcxMA_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjM2NDcxMA_size_16_color_FFFFFF_t_70]: /images/20221022/34e0f03feaad455ea2353eaf217f3e5f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjM2NDcxMA_size_16_color_FFFFFF_t_70 1]: /images/20221022/9b83e854b7b344c6aa0af4aeb5373905.png