C语言编程实现：二叉树采用二叉链表存储，要求建立一颗二叉树，并输出要求的二叉树树状形式与结点编号。

缺乏、安全感 2023-07-24 13:27 90阅读 0赞

## **一、题目** ##

编程实现：二叉树采用二叉链表存储，要求建立一颗二叉树，并输出要求的二叉树树状形式与结点编号。结点如图1.1所示。

![20200412111457336.png][]

图 1.1

其中，二叉树的num编号域为整数类型，data数据域为字符类型，要求生成二叉树中编号，从1开始进行连续编号，每个结点的编号大于其左右子树中孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，请给出对二叉树中结点的实现如上要求编号并按如下图1.2所示的二叉树树状形式打印出相应点编号的程序。

测试数据：AB凵D凵凵CE凵F凵凵凵 (其中符号“凵”代表空格)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70][]

图1.2

## ** 二、题目解析** ##

**  1、题目分析**

本题的要求就是输入一颗二叉树序列，然后输出这个二叉树的横向显示形状，并且按照编号要求输出二叉树横向显示形 状所对应的结点编号。

** 2、解题思路**

（1）根据题目要求可知本题考查了二叉树创建算法、二叉树横向树状打印算法、二叉树遍历算法。

（2）根据输入的数据和对应的二叉树可知，本题用二叉树的前序遍历创建一颗二叉树。

（3）比较二叉树和对应的二叉树树状，可看出对应的树状是二叉树的横向显示图。

分析：①二叉树的横向显示应是竖向显示的90°旋转。由下图2.1可知，这种树形打印格式要求先打印右子树，再打印根，最后打印左子树，按由上而下顺序看，其输出的结点序列为CFEADB，这刚好是逆中序遍历序列。所以解决二叉树横向显示问题采用“逆中序”遍历方法，因此横向显示算法先右子树、再根结点、再左子树的RDL结构。

②在这种输出格式中，结点的左、右位置与结点的层深(即结点所在高度)有关，所以在实现此算法(即实现函数)中设置一个表示当前结点层深的参数，以控制输出结点的左右位置，每当递归进层时层深参数加1。这些操作应在访问根结点时实现。

**                                          **![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70 1][]

图 2.1

（4）根据二叉树树状所对应的序列编号可知，每个结点对应的编号是二叉树后序遍历的顺序编号。即二叉树后序遍历             序列为DBFECA，所对应编号为123456。所以对二叉树编号的算法（即实现函数）就是用二叉树的后序遍历完成。

## ** 三、代码实现** ##

typedef struct BiTNode{
    	char data;
    	int num;
    	struct BiTNode *Lchild, *Rchild;
    }BiTNode,*BiTree;
    void createBiTree(BiTree &T){   //前序遍历创建二叉树
    	char ch;
    	ch=getchar();
    	if (ch != ' '){
    		T = (BiTree)malloc(sizeof(BiTNode));
    		T->Lchild = T->Rchild = NULL;
    		T->data = ch;
    		createBiTree(T->Lchild);
    		createBiTree(T->Rchild);
    	}
    }
    
    int count = 1;
    void putNum(BiTree &T){    //由题可知，对二叉树按后序遍历进行编号
    	if (T != NULL){
    		putNum(T->Lchild);
    		putNum(T->Rchild);
    		T->num = count;
    		count++;
    	}
    }
    
    void printTree(BiTree T,int nLayer){    //输出要求的树状
    	if (T == NULL) return;
    	printTree(T->Rchild,nLayer+1);
    	for (int i = 0; i < nLayer; i++)
    		printf(" ");
    	printf("%c\n", T->data);     //按逆中序输出结点，用层深决定的左、右位置
    	printTree(T->Lchild,nLayer+1);
    }
    
    void printTreeNum(BiTree T, int nLayer){    //输出要求的树状编号
    	if (T == NULL) return;
    	printTreeNum(T->Rchild, nLayer + 1);
    	for (int i = 0; i < nLayer; i++)
    		printf(" ");
    	printf("%d\n", T->num);     //按逆中序输出结点，用层深决定的左、右位置
    	printTreeNum(T->Lchild, nLayer + 1);
    }

## ** 四、输出结果** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70 2][]

[20200412111457336.png]: /images/20230528/e0cfdd4ee8ff4854b306c5b2794141f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70]: /images/20230528/cd1b189fa9c8432286accba007ff6b91.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70 1]: /images/20230528/300cfdb1e34d4315bf07e134ca3cdf81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70 2]: /images/20230528/d227e302cd3c41408b225cd3993589b4.png