数据结构基础分析-二叉树的原理与实现

树是一种数据结构，是由n（n> = 1）个有限节点组成的一组层次关系. 每棵树都有一个根节点，该根节点下有几个子节点，每个非根节点只有一个父节点（根节点没有父节点）. 除了根节点之外，每个子节点都可以分为多个不相交的子树.

树木的相关术语是:

树节点（节点）: 包含一个数据元素和几个指向子树的分支；

子节点: 节点子树的根称为节点的子节点；

父节点: 节点B是节点A的子节点，那么节点A是节点B的父节点；

兄弟节点: 同一父节点的子节点；

库辛节点: 处于同一级别的节点；

祖先节点: 从根到节点的分支后代的所有节点: 子树中以某个节点为根的任何节点都称为节点的后代p>

节点层: 根节点的层定义为1；根的子级是第二层的节点，依此类推；

树的深度: 树中最大的节点层

节点的度数: 节点子树的数量

树的度数: 树中节点的最大度数.

叶节点: 也称为终端节点，它是度为0的节点；

分支节点: 度数不为0的节点；

有序树: 子树的有序树，例如家谱；

无序树: 不考虑子树的顺序；

二叉树是一种特殊的树. 每个节点的树结构最多包含两个子树. 即使一个节点只有一个子树，也必须区分左子树和右子树. 的. 它具有五种基本形式: 空的二叉树，根和左右子树，根和左子树，根和右子树，根和左右子树.

二叉树的属性如下:

（1）深度为k的二叉树最多具有2k-1个节点（k> = 1）

（2）二叉树的第i层上的最大节点数为2i-1（i> = 1）

（3）包含n个节点的二叉树的高度至少为（log2n）+1

（4）在任何二叉树中，如果终端节点的数量为n0，度数为2的节点的数量为n2，则n0 = n2 +1. 推论过程如下:

因为二叉树中所有节点的度数不大于2，所以n0是度数为0的节点数，n1是度数为1的节点数，n2是度数为2的节点数. 这三种类型的节点加起来汇总了点数，因此您可以获得: n = n0 + n1 + n2（1）

第二个等式可以从度之间的关系获得: n = n00 + n11 + n2 * 2 +1，即n = n1 + 2n2 +1（2）

将（1）和（2）组合在一起得到n0 = n2 +1

让我们首先看一下特殊的二叉树-全二叉树. 完整的二叉树: 除了叶子节点的最后一层（没有子节点的节点），每层上的所有节点都有两个子节点. 换句话说，如果二叉树的层数为K，并且节点总数为（2 ^ k）-1，例如，图中的层数为4，则节点数为15 ，叶节点为8、9〜15. 在相同深度的二叉树中，完整二叉树中的节点数最大，叶树最大.

完整的二进制树是从完整的二进制树派生的高效数据结构. 具有n个节点的二叉树按层次结构编号. 如果编号为i的节点和深度相同的完整二进制树在二进制树中的相同位置编号，则它是完整的二进制树. 根据顺序对关键点编号，然后进行相应搜索. 完整的二叉树必须是完整的二叉树，反之则不一定成立.

完整二叉树的特征:

1. 对于节点数相同的二叉树，完整二叉树的高度最小.

2. 完整的二叉树的叶节点仅出现在底部的两层上，而底层的叶节点必须出现在左侧，倒数第二层的叶节点必须出现在右侧.

3. 完整二叉树中度数为1的节点只有左子节点.

为什么要研究二叉树遍历？由于计算机仅处理线性序列，因此我们研究遍历，即将树中的节点转换为具有一定意义的线性序列，这为程序的实现带来了好处.

二叉树遍历是指从树的根节点开始并以一定顺序访问二叉树中的所有节点，因此每个节点仅被访问一次. 从二叉树的递归定义中，我们可以看到一个非空的二叉树由三个基本部分组成: 根节点以及左右子树. 因此，在任何给定节点上，都可以按一定顺序执行三个操作: 访问节点本身（N）；遍历节点的左子树（L）；遍历节点的右子树（R）.

以上三个操作有六个执行顺序: NLR，LNR，LRN，NRL，RNL，RLN. 前三个顺序与后三个顺序对称，此处讨论前三个顺序.

1. NLR是预习遍历（也称为预习遍历）. 访问根节点的操作在遍历其左右子树之前进行. 首先访问根节点，然后先遍历左侧子树，最后遍历右侧子树，即root-left-right.

2. LNR是有序遍历. 访问根节点的操作在遍历其左右子树（之间）时发生. 首先以中间顺序遍历左侧子树，然后访问根节点，最后以中间顺序遍历右侧子树，即left-root-right.

3. LRN是后置遍历. 遍历其左子树和右子树后数据结构 二叉树，将执行访问根节点的操作. 依次遍历左子树，然后依次遍历右子树，然后从左到右访问根节点.

因为被访问的节点必须是子树的根，所以N（节点），L（左子树）和R（右子树）可以解释为根，根的左子树和根树的右子树. NLR数据结构 二叉树，LNR和LRN也分别称为根前遍历，中根遍历和根后遍历.

下面附有源代码程序，编译命令为gcc -o hello tree_exam.c. 请注意，当您在键盘上输入一个节点时，您需要对应两个子节点. 如果为空，则用#表示.

#include<stdio.h>
#include<stdlib.h>
//二叉树的存储结构，一个数据域，2个指针域
typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void PreOrderTraverse(BiTree T)//二叉树的先序遍历
{
    if(T==NULL)
        return ;
    printf("%c ",T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}
void InOrderTraverse(BiTree T)//二叉树的中序遍历
{
   if(T==NULL)
       return ;
   InOrderTraverse(T->lchild);
   printf("%c ",T->data);
   InOrderTraverse(T->rchild);
}
void PostOrderTraverse(BiTree T)//后序遍历
{
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c ",T->data);
}
void CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c",&ch);//1C#S##D##A#1## 一个结点对应两个子结点，为空则用#表示
    if(ch=='#')
        *T=NULL;
    else
    {
        *T=(BiTree)malloc(sizeof(BiTNode));
        if(!*T)
            exit(-1);
        (*T)->data=ch;//给节点的数据域赋值
		printf("输入%c的左子树\n", ch);
        CreateBiTree(&(*T)->lchild);//递归创建左子树
		printf("输入%c的右子树\n", ch);
        CreateBiTree(&(*T)->rchild);//递归创建右子树
    }
}
void DestroyBiTree(BiTree T)
{
    if(T)//如果T存在                                        
    {
        DestroyBiTree(T->lchild);
        DestroyBiTree(T->rchild);
        free(T);
    }
}
int main()
{
    BiTree T;
	printf("请输入二叉树的数据，并以#为空节点
");
    CreateBiTree(&T);
	printf("该树的先序遍历结果为：");
    PreOrderTraverse (T);
	printf("\n");
    printf("该树的中序遍历结果为：");
    InOrderTraverse(T);
	printf("\n");
    printf("该树的后序遍历结果为：");
    PostOrderTraverse(T);
	printf("\n");	
	DestroyBiTree(T);
    return 0;
}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-222722-1.html