一、树的概念

xxx班的学生信息表如图1.1所示，其中学生分别分到了不同的学习小组，第一组组长是李华，组员有王丽、张阳、赵斌；第二组组长是孙琪，组员有马丹；第三组组长是刘畅，组员有周天、黄凯。

这些信息构成了一颗树，如图1.2所示。这就是一种典型的数据结构–树。要实现学生组员的插入、删除、查找等操作，就要用到树的相关知识。

1.1 树的概念

树是零个或多个结点的有限集合。结点树为0的数称为空树，结点树大于0的数称为非空树。在一颗树中：
1）有且仅有一个特定的称为跟的结点。
2）当结点数大于1时，除根结点外，其他结点被分成n(n > 0)个互不相交的子集：T₁,T₂,T₃，…，T_n，其中每个子集本身又是一颗树（称为子树），每一棵子树的根x_i (1 ≤ i ≤ n)都是根结点root的后续，树T₁，T₂，… ，T_n称为根的子树。

1.2 树的基本语术

结点的度：指结点拥有的子树的数目。
叶子或终端结点：指度为0的结点。
非终端结点或分支结点：指度不为0的结点。
树的度：指树内各结点度的最大值。
孩子和双亲：某个结点的子树的根称为该结点的孩子，相应的，该结点称为孩子的双亲。
兄弟：同一个双亲的孩子结点互为兄弟。
结点的层次：规定根所在的层次为第一层，根的孩子在第二层以此类推。
树的深度或高度：树中结点最大的层数。
有序数：指数中结点的各子树从左到右是有次序的，否则称为无序树。
深林：指n（n ≥ 0）棵互不相交的树的集合。
根据树的概念可知：树中任一个结点都可以有零个或多个后续结点（孩子），但是最多只能有一个前趋结点（双亲）；根结点无双亲，叶子结点无孩子；祖先与子孙的关系是父子关系的拓展；有序树中兄弟结点之间从左至右有次序之分。

二 、树的逻辑表示方法

树的常用表示方法有以下四种：树形图法、嵌套集合法、广义表表示法和凹入表示法。

2.1 树形图法

图2.1给出了图形表示树的直观表示法，其中用圆圈表示接点，连线表示结点间的关系，并把树根画在上面。树形图法主要用于直观描述树的逻辑结构。

2.2 嵌套集合表示法

嵌套集合法采用集合的包含关系表示树，如图2.2所示。

2.3 广义表表示法

广义表表示法以广义表的形式表示树，利用广义表的嵌套区间表示树的结构。如A(B, C(E, F), D(G))。

2.4 凹入表示法

凹入表示法采用逐层缩进的方式表示树，有横向凹入表示和竖向凹入表示。如图2.4所示为横向凹入表示。

三、 树的存储结构

存储树时，即要存储结点的数据元素，又要存储结点之间的逻辑关系。结点之间的逻辑关系有：双亲-孩子关系、兄弟关系。因此，采用树的存储结构主要有双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法。

3.1 双亲表示法

使用指针表示每个结点的双亲结点，即双亲表示法。每个结点包含两个域：数据域和指针域。双亲表示法存储如图3.1所示。

在常规指针表示法中，每一个节点是一个结构，包含两个域：数据域和指针域。指针域指向该节点的双亲节点，没有双亲节点的指针域是空指针域。在仿真指针表示法中，每个节点是数组的一个元素，每个元素也包含数据域和指针域，但是指针域存放的是双亲节点所在的数组下标地址（即仿真指针），没有双亲节点的指针域为-1。
双亲表示法多查找一个节点的双亲节点及祖先节点的操作十分便利，但是查找其孩子结点并不方便。

3.2 孩子表示法

使用指针表示出每个结点的孩子结点，即孩子表示法。由于每个结点的孩子结点个数不同，为了简便起见，孩子表示法中的每个结点的指针域个数是树的度。图3.2是孩子表示法采用常规指针表示的存储结构。

孩子表示法与双亲表示法的特点相反。孩子表示法可方便地找到一个结点的孩子及其后裔，并能方便地实现树的遍历。

3.3 双亲孩子表示法

采用双亲表示法和孩子表示法的优势，使用指针即表示出每个结点的双亲结点，又表示出每个结点的孩子结点，就是双亲孩子表示法。指针域即包括指向孩子的指针，也包括指向双亲结点的指针。图3.3是双亲孩子表示法采用常规指针表示的存储结构，其中蓝线表示孩子指针，红线表示双亲指针。

3.4 孩子兄弟表示法

使用指针即指向每个结点的孩子结点，又指向每个结点的兄弟结点，就是孩子兄弟表示法。指针域包含两个指针，指向孩子结点的指针和指向最邻近兄弟结点的指针。
图3.4是常规指针表示的存储结构，其中蓝线表示孩子指针，红线表示兄弟指针。

二叉树输出(凹入表示法)

1598: 二叉树输出

时间限制:1 Sec  内存限制: 128 MB
提交:8  解决: 8
[提交][状态][讨论版]

题目描述

树的凹入表示法主要用于树的屏幕或打印输出，其表示的基本思想是兄弟间等长，一个结点要不小于其子结点的长度。二叉树也可以这样表示，假设叶结点的长度为1,一个非叶结点 的长并等于它的左右子树的长度之和。
一棵二叉树的一个结点用一个字母表示(无重复)，输出时从根结点开始: 
每行输出若干个结点字符(相同字符的个数等于该结点长度)，
如果该结点有左子树就递归输出左子树; 
如果该结点有右子树就递归输出右子树。
假定一棵二叉树一个结点用一个字符描述，现在给出先序和中序遍历的字符串，用树的凹入表示法输出该二叉树。

输入

输入共两行，每行是由字母组成的字符串(一行的每个字符都是唯一的)， 分别表示二叉树的先序遍历和中序遍历的序列。

输出

输出的行数等于该树的结点数，每行的字母相同。

样例输入

ABCDEFG 

CBDAFEG 

样例输出

AAAA

BB

C

D

EE

F

G

提示

来源

信息学奥赛一本通

[提交][状态][讨论版]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include<cstdio> #include<cstring> #include<cmath> using namespace std; char chuan1[1010],chuan2[1010] int n; struct node{  char ch;  int data;  int xian,rightchild,t; }node[101]; void creat(int xianxushou,int xianxumo,int zhongxushou,int zhongxumo,int x){     int temp,k=0,i,temp2,temp3;     for(i=1;i<=n;i++) if(chuan2[i]==chuan1[xianxushou]) temp=i;     node[xianxushou].ch=chuan1[xianxushou];     node[xianxushou].xian=x;     if(temp==zhongxumo&&temp==zhongxushou) node[xianxushou].t=1;     else node[xianxushou].t=0; if(temp>zhongxushou) creat(xianxushou+1,xianxushou+temp-zhongxushou,zhongxushou,temp-1,xianxushou); if(temp<zhongxumo)  creat(xianxushou+temp-zhongxushou+1,xianxumo,temp+1,zhongxumo,xianxushou); }//看下面题解 int main(){     int i;     scanf("%s",chuan1+1);     scanf("%s",chuan2+1);     n=strlen(chuan1+1);     creat(1,n,1,n,0);     for(i=n;i>=1;i--) if(node[i].xian>=0) node[node[i].xian].t+=node[i].t;     for(i=1;i<=n;i++) {         for(int j=1;j<=node[i].t;j++) printf("%c",node[i].ch);         printf("\n");     } }

 

 

 

A

B

C

D

E

F

G

先序

C

B

D

A

F

E

C

中序                                   temp

Creat（先序首，先序末，中序首，中序末）

首先，易得A为树根，那么在中序中查询可知temp=4；

因为中序的性质，所以A的左子树有三个，右子树有四个

那么我们返回先序序列，有先序的性质易得 先序【2-4】为左子树 先序【5-7】为右子树

每个子树的第一个一定是该子树的根，然后又返回中序队列查询

最后可抽象出creat函数

creat(int xianxushou,int xianxumo,int zhongxushou,int zhongxumo,int x)

 

在先序队列xianxushou-xianxumo和中序队列zhongxushou-zhongxumo中进行查找

数据结构的学习中最最基本的实验之——打印二叉树结构

代码生成效果如下：

 

 

（一）需求分析

1.打印二叉树的程序中，输入数据的类型限定为字符型，并且以“回车符”为结束标志。用户默认以中序序列输入字符串，由程序转化为二叉树结构，并以凹入表示法来打印出二叉树。

2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入本程序中规定的运算命令；相应的输入数据和运算结果显示在其后。

3.该程序执行的命令包括：

定义二叉链表的类型、定义二叉链表的结点结构、建立二叉树、遍历二叉树、计算二叉树的深度、打印二叉树以及主函数部分

4.测试数据：

输入：AB D CE  F

输出：  C

                F

            E

A

            D

        B

二叉树抽象数据类型定义

ADT BinaryTree{

数据对象：一个集合D，该集合中的所有元素具有相同的特性

数据关系：

若D为空集则称BinaryTree为空二叉树；若D中仅含有一个数据元素，则R为空集，R={H},H是如下的二元关系：

1.若在D中存在的唯一存在的称为根的数据元素root，它在关系H下没有前驱。

2.除root以外，D中每个节点在关系H下都且仅有一个前驱。

基本操作：

1.Initiate（BiTree）：

操作结果：将bt初始化为空二叉树

2.Create（BiTree）：

操作结果：创建一棵非空二叉树bt

3.Destory（BiTree）：

操作结果：销毁二叉树bt

4.Empty（BiTree）：

操作结果：若bt为空则返回true，否则返回false

5.Root（BiTree）：

操作结果：求二叉树bt的根节点。若为空二叉树则返回null

6.Parent（BiTree，x）：

操作结果：求双亲函数，求二叉树bt中结点x的双亲结点。若结点x是二叉树的根节点或无根节点，则返回null

7.Leftchild（BiTree，x）：

操作结果：求左孩子

8.Rughtchild（BiTree，x）：

操作结果：求右孩子

9.Traverse（BiTree）：

操作结果：遍历操作

10.Clear（bt）：

操作结果：清除操作

Createbitree（&T，defination）构造二叉树

Preordertraverse（T）先序遍历

Inordertraverse（T）中序遍历

Postordertraverse（T）后序遍历 

本程序主要分为六个模块

1）主程序模块

2) 定义二叉链表存储结构模块

3）建立二叉树模块

4）遍历二叉树模块

5）计算二叉树深度模块

6）打印二叉树模块

其中，模块之间的调用关系如下图：

主程序模块

定义二叉链表存储结构模块
 
建立二叉树模块
 

遍历二叉树模块
 
计算二叉树深度模块
 
打印二叉树模块

 ①定义二叉链表的存储结构

typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
} BiTNode, *BiTree;

②先序建立二叉树

void CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c",&ch);
    if (ch==' ')
    *T=NULL;
    else
      { *T=(BiTree)malloc(s izeof(BiTNode));
       (*T)->data=ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
        }
}

③RDL遍历二叉树

void RDLTraverse(BiTree T)
{
    if (T)
      {
          RDLTraverse(T->rchild);
          printf("%2c",T->data);
          RDLTraverse(T->lchild);
        }
}

④计算二叉树的深度

int BiTreeDepth(BiTree T)
{
    int h1,h2,h;
    if (T==NULL)
     return 0;
    else
      {
        h1=BiTreeDepth(T->lchild);
        h2=BiTreeDepth(T->rchild);
        if (h1>h2)
        h=h1+1;
        else
        h=h2+1;
        }
     return h;
}

⑤打印二叉树

void print(BiTree T,int n)
{
    int i;
    if(T)
      {
        print(T->rchild,n+1);
        for(i=0;i<n;i++)
        {
         printf("\t");
         }
         printf("%2c\n",T->data);
         print(T->lchild,n+1);
       }
}

⑥主函数

void main()
{
    BiTree T;
    printf("请按先序输入一棵二叉树(如:AB#D##CE#F###)：\n"); CreateBiTree(&T);
    printf("\nRDL遍历：");   RDLTraverse(T);
    printf("\nDepth=%d",BiTreeDepth(T));
    printf("\n");
    printf("以RDL输出打印结果：\n");print(T,0);
    printf("\n");
}

完整代码+注释（可自取，但未经同意请勿转载）

#include <stdio.h>
#include <stdlib.h>
/*定义二叉链表*/
typedef char TElemType;
/*定义二叉链表的存储结构*/
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
} BiTNode, *BiTree;
/*先序建立二叉树*/
void CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c",&ch);
    if (ch==' ')
    *T=NULL;
    else
      { *T=(BiTree)malloc(sizeof(BiTNode));
       (*T)->data=ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
        }
}
/*RDL遍历二叉树*/
void RDLTraverse(BiTree T)
{
    if (T)
      {
          RDLTraverse(T->rchild);
          printf("%2c",T->data);
          RDLTraverse(T->lchild);
        }
}
/*计算二叉树的深度*/
int BiTreeDepth(BiTree T)
{
    int h1,h2,h;
    if (T==NULL)
     return 0;
    else
      {
        h1=BiTreeDepth(T->lchild);
        h2=BiTreeDepth(T->rchild);
        if (h1>h2)
        h=h1+1;
        else
        h=h2+1;
        }
     return h;
}
/*打印二叉树*/
void print(BiTree T,int n)
{
    int i;
    if(T)
      {
        print(T->rchild,n+1);
        for(i=0;i<n;i++)
        {
         printf("\t");
         }
         printf("%2c\n",T->data);
         print(T->lchild,n+1);
       }
}
void main()
{
    BiTree T;
printf("请按先序输入一棵二叉树(如:AB#D##CE#F###)：\n");
CreateBiTree(&T);
    printf("\nRDL遍历：");   RDLTraverse(T);
    printf("\nDepth=%d",BiTreeDepth(T));
    printf("\n");
    printf("以RDL输出打印结果：\n");print(T,0);
    printf("\n");
}

程序编译运行后，根据提示输入各结点信息（一定要按先序输入！）

注意叶子结点都要有，如果没有，须添加一些虚结点，用#代替

打印二叉树到这里就结束啦~如果对你有帮助，记得点赞赞噢~