【数据结构】二叉树-阿里云开发者社区

树的概念

树是一种非线性的数据结构，它是由n(n>=0)个有限结点组成一个有层次关系的集合

将其称之为数，由于其看似一颗倒挂树，根朝上，叶朝下。

树的特点：

1.有个特殊的结点，称为根节点，根结点没有前驱结点

2.除根节点外，其余结点被分为M(M>0)个不相关的集合T1，T2，T3…Tm，其中每一个集合Ti(1<=i<=m)又是一个与树类似的子树，每棵子树的根结点有且只有一个前驱，可以有0个或多个后结点

3.树是递归定义的

任何一棵树都有俩部分组成：根与子树

树的相关概念

结点的度：一个结点含有的子树的个数称为该结点的度。

叶结点或终端结点：度为零的结点。

非终端结点或分支结点：度不为零的结点

双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点

孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点

兄弟结点：具有相同父结点的结点互称为兄弟结点（亲兄弟）

树的度：一个树中最大的结点的度称为树的度

结点的层次：从根开始定义起，根为第一层，根的子结点为第二层，以此类推

树的高度或深度：树中结点的最大层次

堂兄弟结点：双亲在同一层的结点互为堂兄弟

结点的祖先：从根到该结点所经分支上的所有结点

子孙：以某结点为根的子树中任一结点都称为该结点的子孙

森林：由m(m>0)棵互不相关的树的集合称为森林

树的注意事项

子树是不相交的
除了根结点外，每个结点有且仅有一个父节点
一棵N个结点的树有N-1条边

左孩子右兄弟表示法

typedef int DataType;
struct TreeNode
{
  struct TreeNode* FirstChild;//第一个孩子结点
  struct TreeNode* NextBroter;//指向其下一个兄弟结点
  DataType data;//结点中的数据域
};

树实际中的应用

二叉树

二叉树的概念

一棵二叉树是结点的一个有限集合，该集合：

要么为空
要么由一个根结点加上俩棵别称为左子树和右子树的二叉树组成

二叉树的注意事项

二叉树不存在度大于2的结点
二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

特殊二叉树

满二叉树

一个二叉树，如果每一层的结点数都达到最大值，则这个二叉树就是满二叉树。即如果一个二叉树的层数为k，且结点总数是2^k-1，则为满二叉树

完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的，对于深度为k的，由n个结点的二叉树，当且仅当其每一个结点都与深度的k满二叉树中编号从1至n的结点——对应时称为完全二叉树

二叉树的性质

对于任何一棵完全二叉树，如果度为0其叶结点个数为n0，度为2的分支结点个数为n2，则n0=n2+1。（度为0的永远比度为2的多一个）
高度为h的完全二叉树，结点数量范围[2^h-1,2^h-1]
结点为N的完全二叉树，结点数量的范围[log(N+1),log(N+1)]

二叉树的存储形式

顺序存储

顺序结构存储就是使用数组存储，一般数组只能用来表示完全二叉树（不是完全二叉树会浪费很多空间），二叉树顺序存储在物理上是一个数组，在逻辑上是一棵二叉树。

表示二叉树的值在数组位置中的下标关系：

parent = (child - 1) / 2;
leftchild = parent * 2 + 1;
rightchild = parent * 2 + 2;

链式存储

二叉树的链式存储结构是指用链表表示一棵二叉树，使用链来表示元素之间的逻辑关系。

通常方法是链表中每个结点由三个域组成，数据域与左右指针域。

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
   struct BinTreeNode* _pLeft; // 指向当前节点左孩子
   struct BinTreeNode* _pRight; // 指向当前节点右孩子
   BTDataType _data; // 当前节点值域
}

链式结构又分为二叉链与三叉链

typedef int BTDataType;
// 三叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pParent; // 指向当前节点的双亲
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}；

二叉树链式结构

前面的知识已经对二叉树有了些许了解，总的来讲，普通二叉树没有意义，但是学习二叉树可以对后期了解更多与二叉树有关的知识进入交互学习。

比如搜索二叉树也是二叉树的一种：其左子二叉树小于右子二叉树，搜索二叉树也叫排序二叉树。

类似二分查找，但二分查找的劣势：

1.数组不便于增删查找

2.需要升序或者降序

实际上经常被用来搜索的数据结构有：平衡二叉搜索树、哈希表、B树

简单初始化

进入了解二叉树之前需要简单对二叉树进行初始化，以便对二叉树有清晰的认知。

#include<stdio.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
  BTDataType data;
}BTNode;
BTNode* BuyBTNode(BTDataType x)
{
  BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->left = NULL;
  newnode->right = NULL;
}
BTNode* CreatBTNode()
{
  BTNode* node1 = BuyBTNode(1);
  BTNode* node2 = BuyBTNode(2);
  BTNode* node3 = BuyBTNode(3);
  BTNode* node4 = BuyBTNode(4);
  BTNode* node5 = BuyBTNode(5);
  BTNode* node6 = BuyBTNode(6);
  node1->left = node2;
  node1->right = node4;
  node2->left = node3;
  node4->left = node5;
  node4->right = node6;
  return node1;
}

二叉树的遍历

所谓二叉树遍历是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个结点只操作一次访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

二叉树的遍历有：前序遍历、中序遍历、后续遍历

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

前序遍历

前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

根-左子树-右子树

void PreOrder(BTNode* node)
{
  if (node == NULL)
  {
    printf("NULL ");
    return;
  }
  printf("%d ", node->data);
  PreOrder(node->left);
  PreOrder(node->right);
}

中序遍历

中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

左子树-根-右子树

void InOrder(BTNode* node)
{
  if (node == NULL)
  {
    printf("NULL ");
    return;
  }
  InOrder(node->left);
  printf("%d ", node->data);
  InOrder(node->right);
}

后续遍历

后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

左子树-右子树-根

void PostOrder(BTNode* node)
{
  if (node == NULL)
  {
    printf("NULL ");
    return;
  }
  PostOrder(node->left);
  PostOrder(node->right);
  printf("%d ", node->data);
}

三种遍历代码实现

#include<stdio.h>
#include<stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
  BTDataType data;
}BTNode;
BTNode* BuyBTNode(BTDataType x)
{
  BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  newnode->data = x;
  newnode->left = NULL;
  newnode->right = NULL;
  return newnode;
}
BTNode* CreatBTNode()
{
  BTNode* node1 = BuyBTNode(1);
  BTNode* node2 = BuyBTNode(2);
  BTNode* node3 = BuyBTNode(3);
  BTNode* node4 = BuyBTNode(4);
  BTNode* node5 = BuyBTNode(5);
  BTNode* node6 = BuyBTNode(6);
  node1->left = node2;
  node1->right = node4;
  node2->left = node3;
  node4->left = node5;
  node4->right = node6;
  return node1;
}
void PreOrder(BTNode* node)
{
  if (node == NULL)
  {
    printf("NULL ");
    return;
  }
  printf("%d ", node->data);
  PreOrder(node->left);
  PreOrder(node->right);
}
void InOrder(BTNode* node)
{
  if (node == NULL)
  {
    printf("NULL ");
    return;
  }
  InOrder(node->left);
  printf("%d ", node->data);
  InOrder(node->right);
}
void PostOrder(BTNode* node)
{
  if (node == NULL)
  {
    printf("NULL ");
    return;
  }
  PostOrder(node->left);
  PostOrder(node->right);
  printf("%d ", node->data);
}
int main(void)
{
  BTNode* node = CreatBTNode();
  PreOrder(node);
  printf("\n");
  InOrder(node);
  printf("\n");
  PostOrder(node);
  printf("\n");
  return 0;
}

层序遍历

二叉树除了可以前序遍历、中序遍历、后序遍历，还可以层序遍历，层序遍历就是从二叉树的根结点出发，首先访问根结点，然后第二层从左至右开始访问，以此类推…自上而下，从左往右。

原则：出上一层，入后一层

void levelOrder(BTNode* node)
{
  Queue q;
  QueueInit(&q);
  if (node)
  {
    QueuePush(&q, node);
  }
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    printf("%d ", front->data);
    if (front->left)
    {
      QueuePush(&q, front->left);
    }
    if (front->right)
    {
      QueuePush(&q, front->right);
    }
  }
  Queuedestory(&q);
}

二叉树相关代码实现

二叉树的结点个数

//二叉树结点个数
int BinaryTreeSize(BTNode* node)
{
  if (node == NULL)
    return 0;
  return BinaryTreeSize(node->left) + BinaryTreeSize(node->right) + 1;
}

//二叉树结点个数
int BinaryTreeSize(BTNode* node)
{
  return (node == NULL) ? 0
    : BinaryTreeSize(node->left)
    + BinaryTreeSize(node->right)
    + 1;
}

二叉树的高度

//二叉树的高度或者深度
int BinaryTreeHeight(BTNode* node)
{
  if (node == NULL)
    return 0;
  int leftHeight = BinaryTreeHeight(node->left) + 1;
  int rightHeight = BinaryTreeHeight(node->right) + 1;
  
  return (leftHeight > rightHeight) 
    ? leftHeight 
    : rightHeight;
}

二叉树的叶子结点个数

//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* node)
{
  if (node == NULL)
  {
    return 0;
  }
  if (node->left == NULL && node->right == NULL)
  {
    return 1;
  }
  return BinaryTreeLeafSize(node->left) + BinaryTreeLeafSize(node->right);
}

第k层结点个数

寻找第k层结点结合第一层与第k层距离为k，第二层与第k层距离为k-1…

//二叉树第k层结点个数
int BinaryTreelevel(BTNode* node, int k)
{
  if (node == NULL)
  {
    return 0;
  }
  if (k == 1)
  {
    return 1;
  }
  return BinaryTreelevel(node->left, k - 1) 
    + BinaryTreelevel(node->right, k - 1);
}

二叉树查找值为x的结点

//二叉树查找值为x的结点
BTNode* BinaryTreeFine(BTNode* node, BTDataType x)
{
  if (node == NULL)
  {
    return NULL;
  }
  if (node->data == x)
  {
    return node;
  }
  BTNode* left = BinaryTreeFine(node->left,x);
  BTNode* right = BinaryTreeFine(node->right, x);
  if (left != NULL)
  {
    return left;
  }
  if (right != NULL)
  {
    return right;
  }
  return NULL;
}

二叉树的销毁

void BinaryTreeDestory(BTNode* node)
{
  if(node==NULL)
  {
    return;
  }
  BInaryTreeDestory(node->left);
  BInaryTreeDestory(node->right);
  free(node);
  node->NULL;
}

DFS与BFS

DFS：深度优先遍历（二叉树有序遍历）——一般使用递归
BFS：广度优先遍历（二叉树层序遍历）——一般使用队列

【数据结构】二叉树