数据结构（六）：树与二叉树

一、树的基本概念

1. 树的定义
   树（Tree）是由 n（n ≥ 0）个节点组成的有限集合，当 n = 0 时称为空树。非空树中：

   • 有且仅有一个根节点（Root）；

   • 其余节点可以划分为若干个互不相交的子树，每个子树本身也是一棵树。

2. 树的节点与术语

   • 节点包含数据和若干分支；

   • 度（Degree）：节点拥有的子树数量；

   • 叶子节点：度为 0 的节点；

   • 非终端节点：度不为 0 的节点（又称分支节点）；

   • 孩子（Child）与双亲（Parent）：节点间的直接连接关系；

   • 兄弟节点（Sibling）：同一双亲下的节点；

   • 祖先与子孙：从根到某节点的路径上所有节点为祖先，某节点下所有子节点为子孙。

3. 其他概念

   • 层次（Level）：根为第一层，孩子为第二层，以此类推；

   • 深度（Depth）或高度：节点最大层次；

   • 有序树与无序树：若子树顺序不能交换则为有序树，否则为无序树。

二、树的存储结构

树的存储可分为：

• 顺序结构（如数组）；

• 链式结构（如链表）；
  实际开发中，树通常采用链式结构实现。

三、二叉树的基本概念

1. 定义
   二叉树是每个节点最多有两个子树（左子树和右子树）的树结构。这两个子树有先后顺序，不能颠倒。二叉树可能为空，也可能只有一个根节点。

2. 特点

   • 节点度最大为 2；

   • 必须区分左子树和右子树，即使只有一个孩子；

   • 子树顺序不可交换。

3. 二叉树的五种基本形态

   • 空二叉树；

   • 只有根节点；

   • 只有左子树；

   • 只有右子树；

   • 同时有左右子树。

四、特殊的二叉树

1. 斜树

   • 左斜树：每个节点只有左子树；

   • 右斜树：每个节点只有右子树。

2. 满二叉树
   满足：

   • 所有非叶子节点都有左右两个子树；

   • 所有叶子节点都在同一层；

   • 特点：整棵树结构完全对称，节点数最多。

3. 完全二叉树
   满足：

   • 叶子只出现在最下两层；

   • 最下层叶子靠左连续；

   • 最后一层若不满，叶子也必须靠左；

   • 同样节点数下，深度最小。

五、二叉树的性质（重点公式）

1. 第 i 层最多有 2^(i-1) 个节点（i≥1）

2. 深度为 k 的二叉树最多有 2^k - 1 个节点

3. 叶子数 = 度为 2 的节点数 + 1

4. n 个节点的完全二叉树深度为 log₂(n) + 1

5. 编号为 i 的节点：

   • 若 i=1，它是根节点；

   • 左孩子编号为 2i；

   • 右孩子编号为 2i + 1（若存在）；

   • 双亲编号为 i / 2（i > 1 时）。

六、二叉树的遍历方式

1. 前序遍历：根 → 左 → 右

2. 中序遍历：左 → 根 → 右

3. 后序遍历：左 → 右 → 根

注：遍历时虽然“根”在描述中写在前面，但实际执行顺序是递归的，需要先进入子树再处理根节点。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef char DataType;

typedef struct BiTNode
{
    DataType data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode;

char data[] = "Abd#g###ce#h##fi###";

int ind = 0;

void CreateTree(BiTNode **root)
{
    char c = data[ind++];
    if('#' == c)
    {
        *root = NULL;
        return ;
    }
    else
    {
        *root = malloc(sizeof(BiTNode));
        if(*root == NULL)
        {
            printf("malloc errror\n");
            *root = NULL;
            return ;
        }
        (*root)->data = c;
        CreateTree(&(*root)->lchild);
        CreateTree(&(*root)->rchild);
    }
    return ;
}
//根左右
void PreOrderTraverse(BiTNode *root)
{
    if(NULL == root)
    {
        return ;
    }
    else
    {
        printf("%c", root->data);
        PreOrderTraverse((*root).lchild);
        PreOrderTraverse((*root).rchild);
    }
    return ;
}
//左根右
void InOrderTraverse(BiTNode *root)
{
    if(NULL == root)
    {
        return ;
    }
    else
    {
        InOrderTraverse(root->lchild);
        printf("%c", root->data);
        InOrderTraverse(root->rchild);
        return ;
    }
}

//左右根
void PostOrderTraverse(BiTNode *root)
{
  if (NULL == root)
  {
    return;
  }
  PostOrderTraverse(root->lchild);
  PostOrderTraverse(root->rchild);
  printf("%c", root->data);
  return;
}

void DestroyTree(BiTNode *root)
{
  if (NULL == root)
  {
    return;
  }
  DestroyTree(root->lchild);
  DestroyTree(root->rchild);
  free(root);
  root = NULL;
  return;
}

int main(int argc, char const *argv[])
{
    
    BiTNode *root;
    CreateTree(&root);

    PreOrderTraverse(root);
    printf("\n");
    InOrderTraverse(root);
    printf("\n");
    PostOrderTraverse(root);
    printf("\n");
    DestroyTree(root);
    root = NULL;

    return 0;
}