树

基本概念

• 根结点：没有父结点的结点

• 叶子结点:没有子结点的结点

• 非叶结点

• 祖先结点

• 子孙结点

• 结点的度：该结点子结点的个数

• 树的度:树中结点度最大值即为整棵树的度

• 路径

• 路径长度

• 有向树

• 无向树

• 结点的层数：从根结点开始, 根结点为0层, 以此类推

• 结点的深度: 对任意结点\(x\),深度表示根结点到\(x\)的路径长度,根结点深度为0

• 树的深度: 一棵树中结点的最大深度

二叉树:

• 定义: 度不大于2的树

根-左子树-右子树

二叉树的性质:

• 第\(i\)层最多有\(2^{i}\)个结点(默认根结点为第0层)

• 树的深度为\(h\), 最少有\(h\)个结点, 最多有\(2^{h} - 1\)个结点

• 结点数为\(n\),深度最多为\(n\), 最少为\(\lceil log_{2}(n + 1) \rceil\)

• 叶子结点数为\(n_{0}\),度为2的结点数为\(n_{2}\),则\(n_{0} = n_{2} + 1\)

特殊二叉树

• 满二叉树:除了根结点, 所有结点的度均为2(除叶子结点,所有结点都有左右孩子)

• 完全二叉树:如果一个二叉树去掉最后一层为一个满二叉树,且最后一层的叶子结点从左到右依次分布

森林、树、二叉树

1. 一般树转化为二叉树:
   左孩子，右兄弟结构

2. 树与森林
   树=根+子树森林

二叉树的存储

struct BiNode{
	int data;
	struct BiNode* lchild, rchild;
};

typedef struct BiNode* Tree;

int Init(Tree &T)
{
	T = nullptr;
	return 0;
}

二叉树的遍历

先序遍历:

• 根+左子树+右子树

void PreSearch(BiTree T)
{
	if (T == nullptr)
		return;
	
	cout << T -> data << ' ';
	PreSearch(T -> lchild);
	PreSearch(T -> rchild);
	
}

中序遍历:

• 左子树+根+右子树

void InSearch(Tree T)
{
	if (T == nullptr);
		return;
	
	InSearch(T -> lchild);
	cout << T -> data << ' ';
	InSearch(T -> rchild);
}

后序遍历

• 左子树+右子树+根

void SucSearch(Tree T)
{
	if (T == nullptr)
		return;
	
	SucSearch(T -> lchild);
	SucSearch(T -> rchild);
	cout << T -> data << ' ';
	
}

层序遍历

• 按层遍历,每一层从左到右

void CenSearch(Tree T)
{
	queue<int> q;
	if (T != nullptr)
		q.push_back(T);

	while (!q.empty()){
		auto it = q.front();
		q.pop();


		if (it -> rchild != nullptr)
			q.push_back(it -> rchild);
		if (it -> lchild != nullptr)
			q.push_back(it -> lchild);
	}
}

应用:

1. 求树的深度

int Get_depth(Tree T)
{
	if (T == nullptr)
		return 0;

	return max(Get_depth(T -> lchild), Get_depth(T -> rchild)) + 1;
}

2. 求结点总数

int Get_num(Tree T)
{
	if (T == nullptr)
		return 0;
	return Get_num(T -> lchild) + Get_num(T -> rchild) + 1;
}

3. 确定一个二叉树

• 中序+前序
• 中序+后序