Dev - jw

树形结构 - 树和二叉树小结

树

首先，我们先简单来了解一下数据结构中的树形结构，也称树状图。

在下图中，A是根结点，I、J、K是叶子结点

image-20200428143958384

树是由n个有限结点组成一个具有层次关系的集合，具有以下特点：

  • 每个结点有0个或多个子结点
  • 没有父节点的结点称为根结点
  • 每一个非根结点有且只有一个父结点
  • 除了根结点外，每个子结点可以分为多个不相交的子树

树的种类：

  • 无序树：树种任意结点的子结点之间没有顺序关系
  • 有序树：树种任意结点的子结点之间有顺序关系
  • 二叉树：每个结点最多含有两个子树的树称为二叉树
  • 哈夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树

高度：对于任意结点n，n的高度为从n到某一个叶子结点的最长路径长，所有的叶子结点的高度为0

深度 ：对于任意结点n，n的深度为从根结点到n的唯一路径长，根结点的深度为0

层数：根结点的层定义为1；根的孩子为第二层结点，依此类推；

对于一棵树来说，最深的叶子结点的深度就是树的深度；树根的高度就是树的高度；

对于树种相同深度的每个结点来说，它们的高度不一定相同，这取决于每个结点下面的叶子结点的深度


二叉树

image-20200428202520943

在一棵树种，每个结点最多有两个子树的树形结构，称为二叉树。通常子树被称作”左子树“和”右子树“

一颗树的层数为K，且有$2^K-1$个结点的二叉树，称为满二叉树

在一颗二叉树中，除了最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边确实连续若干结点，则此二叉树为完全二叉树

具有n个结点的完全二叉树的深度为$floor(log_2n) + 1$

深度为K的完成二叉树，至少有$2^{K-1}$个叶子结点，至多有$2^K -1$个结点


二叉树的基本形态：

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态

image-20200428202945299

  1. 空二叉树
  2. 只有一个根节点的二叉树
  3. 只有左子树
  4. 只有右子树
  5. 完全二叉树

二叉树性质

  1. 在非空二叉树中，第i层的结点总数不超过$2^{i-1}$，i>=1
  2. 深度为h的二叉树最多有$2^h-1$个结点（h>=1），最少有h个结点
  3. 对于任意一颗二叉树，如果其叶子结点为N0，而度数为2的结点总数为N2，则N0 = N2 + 1
  4. 具有n个结点的完全二叉树的深度为$floor(log_2n) + 1$
  5. 具有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
    • 若L为结点编号，则如果L>1， 则其父节点的编号为L/2
    • 如果2*L<=N，则其做左子树的根结点的编号为2*L；若2*L > N，则无左孩子
    • 如果2*L+1<=N，则其右孩子的结点编号为2*L+1；若2*L+1>N，则无右孩子。
  6. 给定 N 个结点，能构成h(N)种不同的二叉树
    • h(N)是卡特兰数的第N项。 h(n) = C(2 *n, n) / (n + 1)

二叉树的存储结构

  • 顺序存储

    // 二叉树的最大结点数
#define MAX_TREE_SIZE 100
  
typedef int TElemType;
  
TElemType Nil = 0;  /* 设整型以0位空 */
  
typedef TElemType SeqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根节点 */

  • 链式存储

    typedef struct BTreeNode {
    TElemType data;
    struct BTreeNode *leftTree; /* 左子树 */
    struct BTreeNode *rightTree;/* 右子树 */
}BTreeNode, *BitTree;

二叉树的遍历

二叉树的遍历是指二叉树按某种顺序进行访问二叉树的每一个结点。遍历时，一般选择先左后右的顺序，所以有三种遍历方式，分别是先序，中序，后序

  • 先序遍历（NRL）
    • 访问根结点
    • 先序遍历左子树
    • 先序遍历右子树
  • 中序遍历（LNR）
    • 中序遍历左子树
    • 访问根结点
    • 中序遍历右子树
  • 后序遍历（LRN）
    • 后序遍历左子树
    • 后序遍历右子树
    • 访问根结点
  • **层次遍历：**层次遍历既是每一层每一层依次遍历节点

image-20200429152630095

二叉树顺序存储下的基本操作

顺序存储二叉树，通常只考虑完全二叉树

1. 构建二叉树

Status initTree(SeqBiTree T) {
    for (int i = 0; i < MAX_TREE_SIZE; i++) {
        T[i] = Nil;
    }
    return OK;
}

2. 清空二叉树

#define clearTree initTree

3. 判断二叉树为空

int isEmptyTree(SeqBiTree T) {
    if (T[0] == Nil) {
        return TRUE;
    }else return FALSE;
}

4. 二叉树的深度

/* 深度为h的二叉树最多有2^h-1个结点（h>=1），最少有h个结点 */
int deepOfTree(SeqBiTree T) {
    /* 深度 */
    int j = -1;
    /* 记录最后一个结点位置 */
    int i;
    
    for (i = MAX_TREE_SIZE; i >=0; i--) {
        if (T[i] != Nil) {
            break;
        }
    }
    
    do {
        j++;
    } while (powl(2, j) <= i);
    return j;
}

5. 先序遍历

void PreTraverse(SeqBiTree T,int e){
    
    //打印结点数据
    visit(T[e]);
    
    //先序遍历左子树
    if (T[2 * e + 1] != Nil) {
        PreTraverse(T, 2*e+1);
    }
    //最后先序遍历右子树
    if (T[2 * e + 2] != Nil) {
        PreTraverse(T, 2*e+2);
    }
}

Status PreOrderTraverse(SeqBiTree T){
    
    //树不为空
    if (!isEmptyTree(T)) {
        PreTraverse(T, 0);
    }
    printf("\n");
    return  OK;
}

6. 中序遍历

void InTraverse(SeqBiTree T, int e){
    
    /* 左子树不空 */
    if (T[2*e+1] != Nil)
        InTraverse(T, 2*e+1);
    
    visit(T[e]);
    
    /* 右子树不空 */
    if (T[2*e+2] != Nil)
        InTraverse(T, 2*e+2);
}

Status InOrderTraverse(SeqBiTree T){
    
    /* 树不空 */
    if (!isEmptyTree(T)) {
        InTraverse(T, 0);
    }
    printf("\n");
    return OK;
}

7. 后序遍历

void PostTraverse(SeqBiTree T,int e)
{   /* 左子树不空 */
    if(T[2*e+1]!=Nil)
        PostTraverse(T,2*e+1);
    /* 右子树不空 */
    if(T[2*e+2]!=Nil)
        PostTraverse(T,2*e+2);
    
    visit(T[e]);
}
Status PostOrderTraverse(SeqBiTree T)
{
    if(!isEmptyTree(T)) /* 树不空 */
        PostTraverse(T,0);
    printf("\n");
    return OK;
}

8. 层次遍历

void levalOrder(SeqBiTree T) {
    /* 找到最后一个非空结点的序号 */
    int i = MAX_TREE_SIZE - 1;
    while (T[i] == Nil) {
        i--;
    }
    
    /* 从根结点起,按层序遍历二叉树 */
    for (int j = 0; j <= i; j++) {
        /* 只遍历非空结点 */
        if (T[j] != Nil) {
            visit(T[j]);
        }
    }
}

9. 其他操作

/* 处于{层，本层序号}的结点值 */
TElemType valueOfPosition(SeqBiTree T, int leval, int order) {
    return T[(int)pow(2, leval) + order - 2];
}

/* 获取结点值e的双亲结点的值 */
TElemType parent(SeqBiTree T, TElemType e) {
    if (T[0] == Nil) {
        return Nil;
    }
    for (int i = 0; i < MAX_TREE_SIZE; i++) {
        if (T[i] == e) {
            return T[ (i + 1) / 2 -1];
        }
    }
    return Nil;
}

/* 获取某个结点的左孩子 */
TElemType leftChild(SeqBiTree T, TElemType e){
        if (T[0] == Nil) {
        return Nil;
    }
    for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) {
        if (T[i] == e) {
            return T[ i * 2 + 1 ];
        }
    }
    return Nil;
}

/* 获取某个结点的右孩子 */
TElemType rightChild(SeqBiTree T, TElemType e){
        if (T[0] == Nil) {
        return Nil;
    }
    for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) {
        if (T[i] == e) {
            return T[ i * 2 + 2 ];
        }
    }
    return Nil;
}

二叉树链式存储下的基本操作

1. 构建二叉树

Status initTree(BitTree *T) {
    *T = NULL;
    return OK;
}

2. 清空二叉树

Status clearTree(BitTree *T) {
    if (*T) {
        if ((*T)->leftTree) {
            clearTree(&(*T)->leftTree);
        }
        if ((*T)->rightTree) {
            clearTree(&(*T)->rightTree);
        }
        free(*T);
        *T = NULL;
    }
    return OK;
}

3. 判断二叉树为空

Status isEmptyTree(BitTree T) {
    if (T) {
        return FALSE;
    }else return TRUE;
}

4. 二叉树的深度

int deepOfTree(BitTree T) {
    int left, right;
    
    if (!T) {
        return 0;
    }
    
    if (T->leftTree) {
        left = deepOfTree(T->leftTree);
    }else {
        left = 0;
    }
    
    if (T->rightTree) {
        right = deepOfTree(T->rightTree);
    }else {
        right = 0;
    }
    
    return left > right ? left + 1 : right + 1;
}

5. 先序遍历

/* 递归实现*/ 
void preOrderTraverse(BitTree T) {
    if (T) {
        visit(T->data);
        preOrderTraverse(T->leftTree);
        preOrderTraverse(T->rightTree);
    }
}

/* 非递归实现 - 利用栈的思想 */
void preOrder(BitTree T) {
    BTreeNode *stack[MAX_TREE_SIZE];
    int top = -1;
    stack[++top] = T;
    
    BTreeNode *temp;
    while (top != -1) {
        while ((temp = stack[top]) != NULL) {
            visit(temp->data);
            stack[++top] = temp->leftTree;
        }
        top--;
        if (top != -1) {
            temp = stack[top--];
            stack[++top] = temp->rightTree;
        }
    }
}

void preOrderEx(BitTree T) {
    BTreeNode *stack[MAX_TREE_SIZE];
    int top = -1;
    BTreeNode *temp = T;
    while (temp || top != -1) {
        if (temp) {
            stack[++top] = temp;
            visit(temp->data);
            temp = temp->leftTree;
        }else {
            temp = stack[top--];
            temp = temp->rightTree;
        }
    }
}

6. 中序遍历

/* 递归实现 */
void inOrderTraverse(BitTree T) {
    if (T) {
        inOrderTraverse(T->leftTree);
        visit(T->data);
        inOrderTraverse(T->rightTree);
    }
}

/* 非递归实现 - 利用栈的思想 */
void inOrder(BitTree T) {
    BTreeNode *stack[MAX_TREE_SIZE];
    int top = -1;
    stack[++top] = T;
    
    BTreeNode *temp;
    while (top != -1) {
        while ((temp = stack[top]) != NULL) {
            stack[++top] = temp->leftTree;
        }
        top--;
        if (top != -1) {
            temp = stack[top--];
            visit(temp->data);
            stack[++top] = temp->rightTree;
        }
    }
}

void inOrderEx(BitTree T) {
    BTreeNode *stack[MAX_TREE_SIZE];
    int top = -1;
    BTreeNode *temp = T;
    while (temp || top != -1) {
        if (temp) {
            stack[++top] = temp;
            temp = temp->leftTree;
        }else {
            temp = stack[top--];
            visit(temp->data);
            temp = temp->rightTree;
        }
    }
}

7. 后序遍历

/* 递归实现 */
void postOrderTraverse(BitTree T) {
    if (T) {
        postOrderTraverse(T->leftTree);
        postOrderTraverse(T->rightTree);
        visit(T->data);
    }
}

/** 非递归实现
 1. 先从左遍历到头
 2. 判断当前的结点是否有右子树，或者说有右子树并且没有被访问，则进栈，再从左遍历到头
 3. 到头后如果没有孩子，或者有右子树但是被访问过，则输出结点信息，并将游标指向它
 */
void postOrder(BitTree T) {
    BTreeNode *stack[MAX_TREE_SIZE];
    int top = -1;
    BTreeNode *temp = T;
    BTreeNode *cur  = NULL; /* 游标指向上一个被访问的结点 */
    
    while (temp || top != -1) {
        if (temp) {
            stack[++top] = temp;
            temp = temp->leftTree;
        }else {
            temp = stack[top];
            if (temp->rightTree && temp->rightTree != cur) {
                temp = temp->rightTree;
                stack[++top] = temp;
                temp = temp->leftTree;
            }else {
                temp = stack[top--];
                visit(temp->data);
                cur = temp;
                temp = NULL;
            }
        }
    }
}

8. 层次遍历

/* 先拿到深度，再一层一层的打印 */
void levalTree(BitTree T, int leval) {
    if (T == NULL) {
        return;
    }else if (leval == 1) {
        visit(T->data);
    }else {
        levalTree(T->leftTree, leval -1);
        levalTree(T->rightTree, leval -1);
    }
}

void levalOrder(BitTree T) {
    int deep = deepOfTree(T);
    int i = 1;
    while (i != deep) {
        levalTree(T, i++);
    }
}

完整代码

小结

二叉树是递归定义的，因而常用递归/DFS的思想处理二叉树相关问题。

  • 递归是一个树结构，每个分支都可以探究到最远，发现无法继续的时候往回走，每个结点只会访问一次。

  • 迭代是一个环结构，每次迭代都是一个圈，不会拉掉其中的某一步，然后不断循环，每个节点都会被循环访问

关于遍历

除了递归方式遍历二叉树外，可以借助堆栈实现先序、中序、后序遍历，使用队列实现层次遍历。

LeetCode部分习题

104. Maximum Depth of Binary Tree

112. Path Sum

437. Path Sum III

100. Same Tree

543. Diameter of Binary Tree

563. Binary Tree Tilt

257. Binary Tree Paths

671. Second Minimum Node In a Binary Tree

572. Subtree of Another Tree

110. Balanced Binary Tree

606. Construct String from Binary Tree