文章目录
  1. 树的定义
  2. 树的实现
  3. 树的遍历
  4. 二叉树

树的定义

对树采用递归定义：树是一些节点的集合、这个集合可以是空集；否则，这棵树由称为根的节点R以及多个非空的子树$T_{1}, …, T_{k}$组成，这些子树中每一棵树的根都被来自根R的一条有向边所连接。

树的实现

如下结构体可以用来表示树。

1
2
3
4
5
6
7
typedef struct TreeNode * PtrToNote;

struct TreeNode{
    ElementType Element;
    PtrToNode FirstChild;
    PtrToNode Nextsibling;
}

这样就能将一棵树组织起来。

 

树的遍历

树的遍历有三种方式：先序、中序以及后序。

  • 先序：父节点优先于子节点(从左向右)遍历；
  • 中序：先遍历左子节点，再遍历父节点，最后遍历右子节点；
  • 后序：父节点晚于子节点(从左向右)遍历；

二叉树

二叉树是一棵树，且每个节点的子节点数都不大于2。

由于二叉树的每个节点最多有两个子节点，因此在表示二叉树时，可以直接用指针指向每个节点的左右子节点。

1
2
3
4
5
6
7
typedef struct TreeNode * PtrToNote;

struct TreeNode{
    ElementType Element;
    PtrToNode Left;
    PtrToNode Right;
}