一、 树的定义
树的定义
二、树的抽象数据类型
树的抽象数据类型
三、树的存储结构
双亲表示法
#define MAX_TREE_SIZE 100
typedef int TElemType;
typedef struct PTNode {
TElemType data; //结点数据
int parent; //双亲位置
}PTNode;
typedef struct {
PTNode nodes[MAX_TREE_SIZE]; //结点数组
int r, n; //跟的位置和结点数
} PTree;
孩子表示法
#define MAX_TREE_SIZE 100
typedef int TElemType;
typedef struct CTNode { //孩子结点
int child;
struct CTNode *next;
} *ChildPtr;
typedef struct { //表头结构
TElemType data;
ChildPtr firstchild;
} CTBox;
typedef struct { //树结构
CTBox nodes[MAX_TREE_SIZE]; //结点数组
int r, n; //跟位置，结点数
} CTree;
孩子兄弟表示法
typedef int TElemType;
typedef struct CSNode {
TElemType data;
struct CSNode *firstchild, *rightslb;
} CSNode, *CSTree;
四、二叉树的定义
- 斜树
- 满二叉树
-
完全二叉树
五、二叉树的性质
- 二叉树第i层上至多有2i-1个结点
- 深度为k的二叉树，最少有2k-1个结点
- 对任意二叉树，终端结点数为n0，度为2的结点数为n2，则，n0 = n2 + 1
六、二叉树的存储结构
二叉链表
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
七、遍历二叉树
前序遍历
void BiTree::PreOrderTraverse(biTree T)
{
if (T == NULL)
return;
cout << T->data << endl;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}v
中序遍历
void BiTree::PostOrderTraverse(biTree T)
{
if (T == NULL)
return;
PreOrderTraverse(T->lchild);
cout << T->data << endl;
PreOrderTraverse(T->rchild);
}
后序遍历
void BiTree::PostOrderTraverse(biTree T)
{
if (T == NULL)
return;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout << T->data << endl;
}
已知前序中序求后序
特性A，对于前序遍历，第一个肯定是根节点；
特性B，对于后序遍历，最后一个肯定是根节点；
特性C，利用前序或后序遍历，确定根节点，在中序遍历中，根节点的两边就可以分出左子树和右子树；
特性D，对左子树和右子树分别做前面3点的分析和拆分，相当于做递归，我们就可以重建出完整的二叉树；
例：；
七、二叉树的建立
void BiTree::CreateBiTree(biTree * T)
{
TElemType ch;
cin >> ch;
if (ch == '#') {
T = NULL;
}
else {
*T = (biTree)malloc(sizeof(BiTNode));
if (!*T) {
exit(OVERFLOW);
}
(*T)->data = ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
八、线索二叉树
中序遍历线索化
void BiThrTree::InThreading(biThrTree p)
{
if (p) {
InThreading(p->lchild);
if (!p->lchild) {
p->LTag = Thread;
p->lchild = pre;
}
if (!pre->rchild) {
pre->RTag = Thread;
pre->rchild = p;
}
pre = p;
InThreading(p->rchild);
}
}
九、 树、二叉树、森林的转化
1. 树->二叉树
森林->二叉树
二叉树->树
二叉树->森林
十、哈夫曼树
