《数据结构》复习笔记--二叉树1

前端之家收集整理的这篇文章主要介绍了《数据结构》复习笔记--二叉树1前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

二叉树:

计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树二叉堆

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2^(i-1)个结点;深度为k的二叉树至多有2^k-1个结点;对任何一棵二叉树T,如果其终端结点数为n1,度为2的结点数为n2,则n1=n2+1

一棵深度为k,且有2^k-1个节点称之为满二叉树;深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为完全二叉树

与树不同,树的结点个数至少为1,而二叉树的结点个数可以为0;树中结点的最大度数没有限制,而二叉树结点的最大度数为2;树的结点无左、右之分,而二叉树的结点有左、右之分。


二叉树的抽象数据类型定义

类型名称:二叉树
数据对象集:一个有穷的结点集合。
若不为空,则由根结点和其左、右二叉子树组成。
操作集: BT BinTree,Item  ElementType,重要操作有:
1、Boolean IsEmpty( BinTree BT ): 判别BT是否为空;
2、void Traversal( BinTree BT ):遍历,按某顺序访问每个结点;
3、BinTree CreatBinTree( ):创建一个二叉树。
常用的遍历方法有:
void PreOrderTraversal( BinTree BT ):先序----根、左子树、右子树;
void InOrderTraversal( BinTree BT ): 中序---左子树、根、右子树;
void PostOrderTraversal( BinTree BT ):后序---左子树、右子树、根
void LevelOrderTraversal( BinTree BT ):层次遍历,从上到下、从左到右

二叉树的遍历
(1)先序遍历:

根节点--》先序遍历左子树--》先序遍历右子树。

void PreOrderTraversal(BinTree bt)/*先序遍历*/
{
 if(bt)
 {
 printf("%d",bt->data);
 PreOrderTraversal(bt->left);
   PreOrderTraversal(bt->right);
 }
}

(2)中序遍历:

中序遍历左子树--》根节点--》中序遍历右子树

void InOrderTraversal( BinTree bt)
{
    if(bt)
    {
        InOrderTraversal(bt->Left);
        printf(“%d”,bt->Data);
        InOrderTraversal(bt->Right);
    }
}

(3)后序遍历

后序遍历左子树--》根节点--》后续遍历右子树

void PostOrderTraversal( BinTree bt )
{
    if(bt)
    {
        PostOrderTraversal(bt->Left );
        PostOrderTraversal(bt->Right);
        printf(“%d”,bt->Data);
    }
}

猜你在找的数据结构相关文章