二叉树的基本操作

时间：2021-11-22 17:32:45

一、树：

二叉树的基本操作

树 ：一种非线性数据结构

树的应用：

  • 操作系统中：用树表示文件目录组织结构

  • 编译系统中: 用树表示源程序语法结构

相关概念常见表示方法：

  • 树有且仅有一个根节点

  • 树的结构定义是一个递归的定义

  • 树可以看做一个集合，每个集合下面又有很多子集合，所以单节点与子树之间可以表示为 T={跟结点，左孩子，右孩子}

    -实例：T1 ={A,B,C}

  • 当然，树还可以用括号表示，这样更加容易看

    • 上图可表示为：(A (B(D,E(G) ), C( F(H,J) ) )

  • 还可以通过图形来表示：

二叉树的基本操作

基本树语：

  1. 结点的度：拥有的子树（也就是说有几个分支）
  2. 树的度：树中结点度的最大值
  3. 叶子结点（终端结点）：度为0的结点（没有分支）
  4. 双亲和孩子：如下图：A是B、C的双亲，B、C是A的孩子。
  5. 堂兄弟：如下图：双亲在同一层（如E和F）
  6. 高度（深度）：书中结点最大几层（比如下图为深度：3）
    二叉树的基本操作

二、二叉树：

二叉树：树的度为2的二叉树（结点最大度为2）。

性质：

  • 第i层最多 2^(i-1)个结点
  • 深度为k，最多2^k - 1 个结点
  • 叶子结点树为n,度为2的节点数为n2，那么n=n2+1
  • n个结点的二叉树深度：log2n + 1 (log2n不小于log2n的整数)

满二叉树与完全二叉树：

1、满二叉树：
深度为k且含有2^k-1个结点。看图很容易理解。
二叉树的基本操作

2、完全二叉树：
每个结点都与所对应的完全二叉树一 一对应，叶子几点只可能出现在最后两层。
二叉树的基本操作

二叉树的三种遍历算法：

二叉树的基本操作

1、前序遍历：ABDGHCEIF（规则是先是根结点，再前序遍历左子树，再前序遍历右子树）

2、中序遍历：GDHBAEICF（规则是先中序遍历左子树，再是根结点，再是中序遍历右子树）

3、后序遍历：GHDBIEFCA（规则是先后序遍历左子树，再是后序遍历右子树，再是根结点）

三、C语言实现基本操作（三种遍历算法）;

1、定义树的结构体：

typedef struct BTree
{
char data;              
struct BTree *lChild;  //左孩子
struct BTree *rChild;  //右孩子
}BinTree;

2、创建树：

输入顺序是先遍历根结点，再遍历左右结点，也就是先序遍历，然后重复把左右孩子当做根节点，重复上诉过程，这就是一个递归过程。这里用“#”表示孩子为空，所以下图中B就表示叶子结点，而C没有左孩子。

二叉树的基本操作

这里要求要通过先序遍历输入各结点，如果要创建这个树应该输入：AB##C#D##

BinTree *CreateTree(BinTree *p)
{
    char ch;
    scanf("%c",&ch);
if (ch == '#')  
    {
return NULL;   
    }

    p=(BinTree *)malloc(sizeof(BinTree));
    p->data = ch;
    p->lChild = CreateTree(p->lChild);  //递归左孩子
    p->rChild = CreateTree(p->rChild);  //递归又孩子

return p;
}

3、前序遍历：

根结点->左孩子->右孩子

void PreOrder(BinTree *T)
{
if(T)
    {
        printf("%c",T->data);  //先打印数据，也就是遍历根节点
        PreOrder(T->lChild);
        PreOrder(T->rChild);
    }
}

4、中序遍历

左孩子->根结点->右孩子

void MidOrder(BinTree *T)
{
if (T)
    {
MidOrder(T->lChild);
        printf("%c",T->data);
MidOrder(T->rChild);
    }
}

4、后序遍历：

左孩子->右孩子->根结点

void LastOrder(BinTree *T)
{
if(T)
    {
LastOrder(T->lChild);
LastOrder(T->rChild);
        printf("%c",T->data);
    }
}

5、复制二叉树;

void Copy(BinTree *T,BinTree **newTree)  //二级指针存放指针的地址
{
if(T == NULL)
    {
*newTree = NULL;
return ;
    }

else
    {
*newTree = (BinTree *)malloc(sizeof(BinTree));
        (*newTree)->data = T->data;
        Copy(T->lChild,&(*newTree)->lChild); 
//注意带*号变量指向成员时要加括号
        Copy(T->rChild,&(*newTree)->rChild); //注意第二个参数穿的是地址，所以需要在前面加取地址符号 & 
    }
}

这里用了二级指针存放了指针地址，如果不用二级指针，则需要用返回值的形式来返回新树的地址。如下：程序改为了：

BinTree *Copy(BinTree *T)  //只需要传入T即可，直接返回一个新的地址
{
if(T == NULL)
    {
        newTree = NULL;
return newTree;
    }

else
    {
        newTree = (BinTree *)malloc(sizeof(BinTree));
        newTree->data = T->data;
        newTree->lChild=Copy(T->lChild);
        newTree->rChild=Copy(T->rChild);
    }
return newTree;
}

6、其他操作：

int Sumleaf(BinTree *T)   //求叶结点总数
{
    int sum=0,m,n;
if (T)
    {
if ((!T->lChild) && (!T->rChild))
        {
sum++;
        }
        m=Sumleaf(T->lChild);
sum+=m;
        n=Sumleaf(T->rChild);
sum+=n;
    }
return sum;
}

int Depth(BinTree *T)  //树的深度
{
    int dep=0,dep1,depr;
if (!T)
    {
        dep=0;
    }
else   //分别对左右孩子遍历，看谁的层数大就取谁的值
    {
        dep1=Depth(T->lChild);
        depr=Depth(T->rChild);
        dep=1+(dep1>depr ? dep1:depr);
    }
return dep;
}

总结：

1、递归的时候一定要注意参数传入：

在这个过程中，遇到最大问题就是在复制二叉树那段代码。因为对二级指针操作不是太熟练，所以递归的时候开始的时候老是提示错误：

expected ‘struct BinTree **’ but argument is of type ‘struct BTree *’

后来不断检查才知道，因为二级指针要传的是地址，第一次传了地址，但是第二次没有加取地址符。

2、注意带 * 号变量指向问题：

带*号变量应该正确的指向方法应该是：（*p)->a 而不应该是*p->a

完整代码：

#include <stdio.h>
#include <stdlib.h>  //for malloc 
typedef struct BTree
{
    char data;
    struct BTree *lChild;
    struct BTree *rChild;
}BinTree;

BinTree *CreateTree(BinTree *p)
{
    char ch;
    scanf("%c",&ch);
if (ch == '#')  //# standard for the leaf node
    {
return NULL;   
    }

    p=(BinTree *)malloc(sizeof(BinTree));
    p->data = ch;
    p->lChild = CreateTree(p->lChild);
    p->rChild = CreateTree(p->rChild);

return p;
}

int Sumleaf(BinTree *T)
{
    int sum=0,m,n;
if (T)
    {
if ((!T->lChild) && (!T->rChild))
        {
sum++;
        }
        m=Sumleaf(T->lChild);
sum+=m;
        n=Sumleaf(T->rChild);
sum+=n;
    }
return sum;
}

int Depth(BinTree *T)
{
    int dep=0,dep1,depr;
if (!T)
    {
        dep=0;
    }
else
    {
        dep1=Depth(T->lChild);
        depr=Depth(T->rChild);
        dep=1+(dep1>depr ? dep1:depr);
    }
return dep;
}

void PreOrder(BinTree *T)
{
if(T)
    {
        printf("%c",T->data);
        PreOrder(T->lChild);
        PreOrder(T->rChild);
    }
}

void MidOrder(BinTree *T)
{
if (T)
    {
        MidOrder(T->lChild);
        printf("%c",T->data);
        MidOrder(T->rChild);
    }
}

void LastOrder(BinTree *T)
{
if(T)
    {
        LastOrder(T->lChild);
        LastOrder(T->rChild);
        printf("%c",T->data);
    }
}

void Copy(BinTree *T,BinTree **newTree) 
{
if(T == NULL)
    {
*newTree = NULL;
return ;
    }

else
    {
*newTree = (BinTree *)malloc(sizeof(BinTree));
        (*newTree)->data = T->data;
        Copy(T->lChild,&(*newTree)->lChild);
        Copy(T->rChild,&(*newTree)->rChild);
    }
}

int main()
{
    BinTree *Tree;
    BinTree *newtree;
    printf("请以前序遍历的方式输入扩展二叉树，用“#”表示空结点：\n");
    Tree=CreateTree(Tree);

    printf("前序遍历:\n");
    PreOrder(Tree);

    printf("\n中序遍历:\n");
    MidOrder(Tree);

    printf("\n后序遍历:\n");
    LastOrder(Tree);

    printf("\n叶结点总数：%d\n",Sumleaf(Tree));
    printf("\n树的层数：%d\n",Depth(Tree));

    Copy(Tree,&newtree);
//如果Copy()函数是返回值的形式调用应该如此：
//newtree=Copy(Tree);

    printf("\n复制树后序遍历:\n");
    LastOrder(newtree);  //用来检验是否成功

return 0;
}

测试：
要创建如下二叉树，并且输出：先/中/后序遍历结果
二叉树的基本操作

输入（先序遍历输入）：AB##C#D##
测试结果：
二叉树的基本操作

本文参考：http://www.cnblogs.com/liuamin/p/6269950.html
标签：

相关文章