数据结构---树

二叉树

特征

1. 二叉树每个结点最多有2个子结点
2. 二叉树的子树有左右之分

引理

1. 二叉树中层数为 i 的结点至多有2^i个，i≥0

2. 高度为k (k >=0)的二叉树中至少有k+1个结点。含有k (k >=1)个结点的二叉树高度至多为k-1

3. 高度为k的二叉树中至多有2^(k+1)－1 (k>=0) 个结点

4. 设T是由n个结点构成的二叉树，其中，叶结点个数为n_0，度为2的结点个数为n_2，则n_0和n_2 的关系是: n_0 = n_2 + 1

满二叉树

一棵非空高度为k( k >= 0)的满二叉树，是有2^(k+1) – 1个结点的二叉树

完全二叉树

定义:

一棵有 n 个结点、高为 k 的二叉树 T，一棵高为 k 的满二叉树 T^，用正整数按层次顺序分别编号 T 和 T^ 的所有结点，如果T 之所有结点恰好对应于T^的前 n 个结点，则称 T 为完全二叉树。

层次顺序：按从上至下，即从第 0 至第 k 层，每层由左到右的次序。

特点:

1. 树中只有最下面两层结点的度可以小于2

2. 树中最下面一层的结点都集中在该层最左边的若干位置上（满二叉树意义上)

3. 树中叶结点只能在层数最大的两层上出现，即存在一个非负整数k使得树中每个叶结点或在第k层或第k + 1层上

4. 对树中所有结点，按层次顺序，用自然数从1开始编号，仅仅编号最大的非叶结点可以没有右孩子，其余非叶结点都有两个孩子结点

引理:

①设若将一棵具有n个结点的完全二叉树按层次次序从1开始编号，则对编号为i (1 <= i <= n)的结点有：

1. 若i≠1，则编号为 i 的结点的父结点的编号为 (i/2)下限.

2. 若2i <= n，则编号为 i 的结点的左孩子的编号为 2i, 否则 i 无左孩子

3. 若2i+1 <= n，则 i 结点的右孩子结点编号为2i+1,否则 i 无右孩子

②具有n个结点的完全二叉树的高度是(log2n)下限

注意: 仅仅编号最大的非叶结点可无右孩子, 但必须有左孩子, 其余非叶结点都有两个孩子结点

二叉树的存储形式:

顺序存储

1. 一维数组A存储二叉树, A[1]存储二叉树的根结点，A[i]存储二叉树中编号为i的结点，并且结点A[i]的左孩子（若存在）存放在A[2i]处，而A[i]的右孩子（若存在）存放在A[2i+1]处。
2. 优点: 简单、节省空间
   只存储结点信息域、未存储其左孩子和右孩子。通过计算可找到它的左孩子、右孩子和父 结点，寻找子孙结点和祖先结点也非常方便
3. 缺点: 编号不能与结点一一对应
   解决方案：先加入若干虚结点将其转换成一棵“完全二叉树”，然后再对原来的结点和虚结点统一编号，最后完成顺序存储。但这 增加了用于存储虚结点的空间。

链式存储

二叉树的遍历:

#include<iostream>
using namespace std;

typedef struct node
{
	struct node* left;
	char data;
	struct node* right;
}node;

//根据先跟序列创建二叉树, NULL用'#'表示
void CBT(node* &T)
{
	char ch;
	ch = getchar();
	if(ch == '#')
	{
		T = NULL;
	}
	else
	{
		T = new node;
		T->data = ch;
		CBT(T->left);
		CBT(T->right);
	}
}

//先根遍历
void  Preorder(node* p)
{
	if(p != NULL)	
	{
		cout<<p->data;
		Preorder(p->left);
		Preorder(p->right);
	}
}

//中根遍历
void  Inorder(node* p)
{
	if(p != NULL)	
	{
		Inorder(p->left);
		cout<<p->data;
		Inorder(p->right);
	}
}

//后根遍历
void  Postorder(node* p)
{
	if(p != NULL)	
	{
		Postorder(p->left);
		Postorder(p->right);
		cout<<p->data;
	}
}

int main(){
	
	node* T = NULL;
	cout<<"输入:"<<endl;
	
	CBT(T);
	
	Preorder(T);
	cout<<endl;
	
	Inorder(T);
	cout<<endl;
	
	Postorder(T);
	
	return 0;
}