数据结构 树的基本概念 7

目录：树和二叉树

1) 树的基本知识                       2)二叉树                          3）遍历二叉树和线索二叉树

4）树和森林                            5）赫夫曼树及其应用

---

                                         

特点：非线性结构，一个直接前驱，但可能有多个直接后继(1:n)

1.树的定义         

        由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树 。       

                                               

注1：过去许多书籍中都定义树为n≥1，曾经有“空树不是树”的说法，但现在树的定义已修改。

注2：树的定义具有递归性，即树中还有树。

2.若干术语

根——即根结点(没有前驱) 

叶子——即终端结点(没有后继)

森林——指m棵不相交的树的集合(例如删除A后的子树个数)

有序树——结点各子树从左至右有序，不能互换（左为第一）

无序树——结点各子树可互换位置

双亲——即上层的那个结点(直接前驱) parent

孩子——即下层结点的子树 (直接后继) child

兄弟——同一双亲下的同层结点（孩子之间互称兄弟）sibling

堂兄弟——即双亲位于同一层的结点（但并非同一双亲）cousin

祖先——即从根到该结点所经分支的所有结点

子孙——即该结点下层子树中的任一结点

结点——即树的数据元素

结点的度——结点挂接的子树数（有几个直接后继就是几度，亦称“次数”）

结点的层次——从根到该结点的层数（根结点算第一层）

终端结点——即度为0的结点，即叶子

分支节点——除树根以外的结点（也称为内部结点）

树的度——所有结点度中的最大值（Max{各结点的度}）

树的深度（或高度）——指所有结点中最大的层数（Max{各结点的层次}）

问：右上图中的结点数＝13  ；树的度＝ 3 ；树的深度＝4

3.树的表示法

图形表示法       嵌套集合表示法         广义表表示法         目录表示法           左孩子－右兄弟表示法

图形表示法：

广义表表示法：

( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ) 根作为由子树森林组成的表的名字写在表的左边

4.树的抽象数据类型定义

树的逻辑结构(特点)： 一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。

树的存储结构：

讨论1：树是非线性结构，该怎样存储？

           —仍然有顺序存储、链式存储等方式。

讨论2：树的顺序存储方案应该怎样制定？

可规定为：从上至下、从左至右将树的结点依次存入内存。 重大缺陷：复原困难（不能唯一复原就没有实用价值）。

讨论3：树的链式存储方案应该怎样制定？

可用多重链表：一个前趋指针，n个后继指针。 细节问题：树中结点的结构类型样式该如何设计？  即应该设计成“等长”还是“不等长”？ 缺点：等长结构太浪费（每个结点的度不一定相同）；       不等长结构太复杂（要定义好多种结构类型）。

讨论4：计算机如何实现各种不同进制的运算？

实现思路：先研究最简单、最有规律的二进制运算规律，然后设法把各种不同进制的运算转化二进制运算。

讨论5：树的存储可否借鉴这种思路呢？

解决思路：先研究最简单、最有规律的树，然后设法把一般的树转化为这种简单的树。

树的运算：

要明确：

1. 普通树（即多叉树）若不转化为二叉树，则运算很难实现。

2. 二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！  

（遍历——指每个结点都被访问且仅访问一次，不遗漏不重复）。

5.二叉树

为何要重点研究每结点最多只有两个 “叉” 的树？

二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。

二叉树的定义：

定义：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。

逻辑结构：  一对二（1：2）

基本特征: ① 每个结点最多只有两棵子树（不存在度大于2的结点）； ② 左子树和右子树次序不能颠倒（有序树）。

基本形态：

二叉树的抽象数据类型定义：

6.二叉树的性质

讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？

性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1）

证明： ∵ 二叉树中全部结点数n＝n0+n1+n2(叶子数＋1度结点数＋2度结点数) 又∵二叉树中全部结点数n＝B+1 ( 总分支数＋根结点 )        （除根结点外，每个结点必有一个直接前趋，即一个分支） 而 总分支数B= n1+2n2  (1度结点必有1个直接后继，2度结点必有2个) 三式联立可得： n0+n1+n2= n1+2n2 +1,   即n0=n2+1 实际意义：叶子数＝2度结点数＋1

满二叉树：

对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质：

7.二叉树的存储结构

一、顺序存储结构

按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。

问：顺序存储后能否复原成唯一对应的二叉树形状？

答：若是完全/满二叉树则可以做到唯一复原。而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i＋1（即性质5）    

例如，对应[2]的两个孩子必为[4]和[5],即B的左孩子必是D,右孩子必为E。

二、链式存储结构

用二叉链表即可方便表示，一般从根结点开始存储。 （相应地，访问树中结点时也只能从根开始）

注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。

二叉树结点数据类型定义：

typedef struct node *tree_pointer;
typedef struct node{
        int data;
        free_pointer lefet_child,right_child;
}node;

二叉链表示法： 

 

                                                                     

                                                             

                                                              

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
/*
typedef struct BiTNode
{
    int date;
    struct BiTNode* lchild,* rchild;
}BiTNode,*BiTree;
*/
//二叉链表示法
struct BiTNode
{
    int date;
    struct BiTNode* lchild,* rchild;
}BiTNode,*BiTree;
typedef struct BiTNode BiTNode;

typedef struct BiTNode *BiTree;
void main()
{
    BiTNode *p1,*p2,*p3,*p4,*p5;
    p1=( BiTNode *)malloc(sizeof(BiTNode));
    p2=( BiTNode *)malloc(sizeof(BiTNode));
    p3=( BiTNode *)malloc(sizeof(BiTNode));
    p4=( BiTNode *)malloc(sizeof(BiTNode));
    p5=( BiTNode *)malloc(sizeof(BiTNode));

    p1->data=1;
    p2->data=2;
    p3->data=3;
    p4->data=4;
    p5->data=5;

    //建立关系
    p1->lchild=p2;
    p1->rchild=p3;
    p2->lchild=p4;
    p3->lchild=p5;

    //树的遍历

    return;
}

三叉链表示法：

                                                    

                                                                   

                                             

//三叉链表
typedef struct TriTNode
{
     int data;
     //左右孩子指针
     struct TriTNode *lchild,*rchild;
     struct TriTNode *parent;
}TriTNode,*TriTree;

双亲链表法：

//双亲链表
#define MAX_TREE_SIZE 100
typedef struct BPTNode
{
	int data;
	int parentPosition;  //指向双亲的指针   //数组下标
	char LRTag;     //左右孩子标志域
}BPTNode;

typedef struct BPTree
{
	BPTNode nodes[100];    //因为节点之间是分散的，需要把节点存储到数组中
	int num_node;    //节点数目
	int root;     //根节点的位置   //注意此域存储的是父亲节点在数组的下标
}BPTree;

void main()
{
	BPTree tree;

	//根节点
	tree.nodes[0].parentPosition = 1000;

	//B
	tree.nodes[1].parentPosition = 0;
	tree.nodes[1].data = 'B';
	tree.nodes[1].LRTag = 1;

	//C
	tree.nodes[2].parentPosition = 0;
	tree.nodes[2].data = 'C';
	tree.nodes[2].LRTag = 2;
	system("pause");
}