10--二叉树

[toc]

重要概念

** 树是非线性结构**

• 结点

  
  32d5452ed9d2d991153f0e038560c205

  结点是数据结构中的基础，是构成复杂数据结构的基本组成单位。

• 树

  • 树（Tree）是n（n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中：

        1.  有且仅有一个特定的称为根（Root）的结点；
        2.  当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、......、Tn，其中每一个集合本身又是一棵树，并且称为根的子树。

此外，树的定义还需要强调以下两点：

1.   n>0时根结点是唯一的，不可能存在多个根结点，数据结构中的树只能有一个根结点。
2.  m>0时，子树的个数没有限制，但它们一定是互不相交的。

示例树：

d8d8826012fd7943d08e3291ba0ae9ef

• 树的度

结点拥有的子树数目称为结点的度。

e0655ec48c23c7f9e60d25a8d0388944

• 结点的关系

结点子树的根结点为该结点的孩子结点。相应该结点称为孩子结点的双亲结点。

图中，A为B的双亲结点，B为A的孩子结点。
同一个双亲结点的孩子结点之间互称兄弟结点。
图中，结点B与结点C互为兄弟结点。

• 结点高度 深度 层次

7a1404d02bd367aba1d3d2c7e6e9d4fc

• 层 从根开始定义起，根为第一层，根的孩子为第二层，以此类推。
• 树中结点的最大层次数称为树的深度或高度。

二叉树

• 定义

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。

3415c81cbcd4ab30841738538ae50f82

• 特点

由二叉树定义以及图示分析得出二叉树有以下特点：

1.  每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。

2. 左子树和右子树是有顺序的，`次序不能任意颠倒`。

3. 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

• 二叉树性质

  1. 在二叉树的第i层上最多有2i-1 个节点 。（i>=1）
  2. 二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1）
  3. n0=n2+1 n0表示度数为0的节点数，n2表示度数为2的节点数。
  4. 在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]是向下取整。）

5. 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如下特性：

(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
(2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；
(3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点

• 斜树

斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

e90c0dab0b27ed118fa955cd2413b997

• 满二叉树

满二叉树：在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

满二叉树的特点有：

1. 叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
2. 非叶子结点的度一定是2。

3. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

   
   8bff6e14fd9a03b72b645d76d4c9ff3f

• 完全二叉树

完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

11a31cd5005747b1615c1f3a509105da

特点:
1. 叶子结点只能出现在最下层和次下层。
2. 最下层的叶子结点集中在树的左部。
3. 倒数第二层若存在叶子结点，一定在右部连续位置。
4. 如果结点度为1，则该结点只有左孩子，即没有右子树。
5. 同样结点数目的二叉树，完全二叉树深度最小。

注：满二叉树一定是完全二叉树，但反过来不一定成立。

二叉树 顺序存储

二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。

• 初始化

typedef {
    int level;
    int order
} Position;

//构造空二叉树
Status InitBitTree(CElemType *T){
    for (int i=0; i<PAGE_MAX_SIZE; i++) {
        T[i] = Nil;
    }
    return OK;
}

• 创建

Status CreateBiTree(SqBiTree T){
    int I;
    I=0;
    while (i<10) {
        T[i] = I+1;
        //(i+1)/2-1 双亲节点
        if (i==0 && T[(i+1)/2-1] == Nil && T[i] == Nil){
            exit(ERROR);
        }
        I++;
    }
    while (i<MAX_TREE_SIZE) {
        T[i] = Nil;
        I++;
     }
}

• 清空

#define ClearBiTree InitBiTree

• 树的深度

int BiTreeDepth(SqBiTree T){
    int j = -1;
    int I;
    for (i=MAX_TREE_SIZE; i>=0; i++) {
        while (T[i] != Nil) {
            break;
        }
    }
    do {
        j++;
    } while (powl(2, j)<=i);
    return j;
}

• 查找

CElemType Value(SqBiTree T,Position e){
   
    //1.每一层其实是pow(2, e.level-1)
    //数数从1开始,打印从0开始起
    
    return T[(int)pow(2, e.level-1)-1 +e.order-1];
    
}

• 层次遍历

void LevelOrderTraverse(SqBiTree T){
    int I;
    for (i=MAX_TREE_SIZE-1; i>=0; i++) {
        while (T[i] != Nil) {
            break;
        }
    }
    for (int j=0; j<i; j++) {
        printf("%d ",T[j]);
        
    }
}

• 前序

void PreTraverse(SqBiTree T,int e){
    printf("%d",T[e]);
    if(T[2*e+1] != Nil){
        PreTraverse(T,2*e+1);
    }
    if(T[2*e+2] != Nil){
        PreTraverse(T,2*e+2);
    }
}

• 中序

void InTraverse(SqBiTree T,int e){
   
    if(T[2*e+1] != Nil){
        PreTraverse(T,2*e+1);
    }
     printf("%d",T[e]);
    if(T[2*e+2] != Nil){
        PreTraverse(T,2*e+2);
    }
}

• 后续

void PostTraverse(SqBiTree T,int e){
    if(T[2*e+1] != Nil){
        PreTraverse(T,2*e+1);
    }
    if(T[2*e+2] != Nil){
        PreTraverse(T,2*e+2);
    }
    printf("%d",T[e]);
}

二叉树 链式存储

• 配置

#include "string.h"
#include "stdio.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100
typedef int Status;

• 宏 ,字符串处理

#pragma mark--二叉树构造
int indexs = 1;
typedef char String[24]; /*  0号单元存放串的长度 */
String str;

//字符串构造
Status StrAssign(String T,char *str){
    if(strlen(str)>MAXSIZE){
        return ERROR;
    }
    T[0] = strlen(str);
    for (int i=1; i<T[0]; i++) {
        T[i] = *(str + i-1);
    }
    return OK;
}

• 创建二叉树

typedef char ChartType;

ChartType Nil = ' ';
typedef struct BitNode{
    ChartType data;
    struct BitNode *lNode,*rNode;//左右结点
}BitNode;
typedef BitNode* BitTree;
//二叉树创建
//"ABDH#K###E##CFI###G#J##"
void InitTwoTree(BitTree *T){
    char ch;
    ch = str[indexs++];
     printf("------%c\n",ch);
    if(ch == '#'){
        *T = NULL;
        return; //可省略,条件不满足退回上一次
    }
    
    *T = (BitTree)malloc(sizeof(BitNode));
    (*T)->data = ch;
    InitTwoTree(&((*T)->lNode));
    InitTwoTree(&((*T)->rNode));
}

• 判空

Status IsNullTree(BitTree T){
    if(T){
        return true;
    }
    return false;
}

• 二叉树深度

每一颗树的最大深度都是左右子树中的最大深度再加1

int BiTreeDepth(BiTree T){
    
    int i,j;
    if(!T)
        return 0;
        
    return BiTreeDepth(T->lchild)>BiTreeDepth(T->rchild)?BiTreeDepth(T->lchild)+1:BiTreeDepth(T->rchild)+1;
}

• 二叉树根

ChartType Root(BitTree T){
    if(IsNullTree(T)){
        return Nil;
    }
    return T->data;
}

c1e3ff3771cd504f602773a613e30bc8

• 前序遍历

前序遍历通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。
A B D H K E C F I G J
先输出ABDH,在输出K
返回到D,在返回到B,输出E
其他依次类推

void PreOrderTraverse(BiTree T){
    if(T = NULL){
        return;
    }
    printf("%c",T->data);
    PreOrderTraverse(T->lNode);
    PreOrderTraverse(T->lNode);
}

• 中序遍历

中序遍历就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。
H K D B E A I F C G J

void CenterOrderTraverse(BiTree T){
    if(T = NULL){
        return;
    }
    PreOrderTraverse(T->lNode);
    printf("%c",T->data);
    PreOrderTraverse(T->lNode);
}

• 后序遍历

后序遍历就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。
KHDEBIFJGCA

void PostOrderTraverse(BiTree T){
    if(T = NULL){
        return;
    }
    PreOrderTraverse(T->lNode);
    PreOrderTraverse(T->lNode);
    printf("%c",T->data);
}

二叉树的四种遍历