数据结构---树
二叉树
特征
- 二叉树每个结点最多有2个子结点
- 二叉树的子树有左右之分
引理
-
二叉树中层数为 i 的结点至多有2^i个，i≥0
-
高度为k (k >=0)的二叉树中至少有k+1个结点。含有k (k >=1)个结点的二叉树高度至多为k-1
-
高度为k的二叉树中至多有2^(k+1)－1 (k>=0) 个结点
-
设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 层，每层由左到右的次序。
特点:
-
树中只有最下面两层结点的度可以小于2
-
树中最下面一层的结点都集中在该层最左边的若干位置上（满二叉树意义上)
-
树中叶结点只能在层数最大的两层上出现，即存在一个非负整数k使得树中每个叶结点或在第k层或第k + 1层上
-
对树中所有结点，按层次顺序，用自然数从1开始编号，仅仅编号最大的非叶结点可以没有右孩子，其余非叶结点都有两个孩子结点
引理:
①设若将一棵具有n个结点的完全二叉树按层次次序从1开始编号，则对编号为i (1 <= i <= n)的结点有：
-
若i≠1，则编号为 i 的结点的父结点的编号为 (i/2)下限.
-
若2i <= n，则编号为 i 的结点的左孩子的编号为 2i, 否则 i 无左孩子
-
若2i+1 <= n，则 i 结点的右孩子结点编号为2i+1,否则 i 无右孩子
②具有n个结点的完全二叉树的高度是(log2n)下限
注意: 仅仅编号最大的非叶结点可无右孩子, 但必须有左孩子, 其余非叶结点都有两个孩子结点
二叉树的存储形式:
顺序存储
- 一维数组A存储二叉树, A[1]存储二叉树的根结点，A[i]存储二叉树中编号为i的结点，并且结点A[i]的左孩子（若存在）存放在A[2i]处，而A[i]的右孩子（若存在）存放在A[2i+1]处。
- 优点: 简单、节省空间
只存储结点信息域、未存储其左孩子和右孩子。通过计算可找到它的左孩子、右孩子和父 结点，寻找子孙结点和祖先结点也非常方便 - 缺点: 编号不能与结点一一对应
解决方案：先加入若干虚结点将其转换成一棵“完全二叉树”，然后再对原来的结点和虚结点统一编号，最后完成顺序存储。但这 增加了用于存储虚结点的空间。
链式存储
二叉树的遍历:
#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;
}