数据结构7：树与二叉树

树与二叉树

树是一种非线性数据结构，由 n（n≥0） 个有限节点构成具有层次关系的集合。

一些概念

结点：树中的一个独立单元。

结点的度：结点拥有的子树数称为结点的度。
树的度：树内各结点度的最大值。
叶子：度为 0 的结点或终端结点。
非终端结点：度不为 0 的结点。
双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。
层次：结点的层次从根开始定义，
根为第一层，根的孩子为第二层，
以此类推。

image-20250523204021005

二叉树

二叉树（Binary Tree）是 n（ ）个结点
所构成的集合，它或为空树（n=0），或为非
空树。对于非空树 T：
n ⩾ 0
（1）有且仅有一个 称为根的结点
（2）除根结点以外的其余结点分为两个互
不相交的子集 T1 和 T2 ，分别称为 T 的左
子树和右子树，且 T1 和 T2 本身又都是二叉
树。
（3）二叉树每个结点至多只有两棵子树。
（4）二叉树的子树有左右之分，其次序不能任意颠倒。

image-20250523215612638

基本形态

二叉树主要有以下几个基本形态：

image-20250523220257631

树也是一种数据结构.

实现

1
2
3
4
5
6
7
8
9
typedef char ElemType;

typedef struct TreeNode
{
  ElemType data;
  TreeNode *lchild;
  TreeNode *rchild;
  }TreeNode;
typedef TreeNode* BiTree;//给TreeNode类型的指针起了别名为BiTree

image-20250524201202428

类似于用指向表头的指针来代表链表，我们使用指向根结点的指针来代表整个树。

树的遍历

对于树的遍历，我们需要使用递归。这一块可能很难理解，可以辅助代码可视化。

image-20250524205550958

前序遍历

先访问根结点，然后访问左分支上遇到的每一个结点，持续这一过程，直到遇到空结
点为止。这时，返回到最近的有右孩子的祖先结点，并从该结点的右孩子开始继续遍历。

1
2
3
4
5
6
7
8
9
10
void preOrder(BiTree T) //前序遍历
{
if (T == NULL)
{
	return;
}
	printf("%c ", T->data);
	preOrder(T->lchild);   //先遍历左子节点再遍历右节点
	preOrder(T->rchild);
}

遍历顺序：**A B D H K E C F I G J **

中序遍历

先访问根结点，向树的左下方移动，直到遇到空结点为止，然后访问空结点的父结点。接着继续遍历该结点的右子树，如果右子树没的子树可以遍历，那么继续遍历上一层最后一个未被访问的结点。

1
2
3
4
5
6
7
8
9
10
void inOrder(BiTree T)
{
	if (T == NULL)
{
return;
}
	inOrder(T->lchild);   //顺序不一样了
	printf("%c ", T->data);
	inOrder(T->rchild);
}

遍历顺序：**H K D B E A I F C G J **

后序遍历

从根结点开始先访问结点的左右儿子，再对该结点进行访问。这就意味着结点的儿子
将在该结点之前输出。

1
2
3
4
5
6
7
8
9
10
void postOrder(BiTree T)
{
if (T == NULL)
{
return;
}
postOrder(T->lchild);
postOrder(T->rchild);
printf("%c ", T->data);
}

遍历顺序：**K H D E B I F J G C A **