树及二叉树

 

1.什么是树

定义:树是一个或多个结点的有限集合,其中

a) 存在一个称为根的特定结点

b) 其余的结点被分成n>=0个互不相关的集合T1,...,Tn,其中每个集合都是一棵树

 

什么是结点的度?

一个结点的度是指该结点的子树个数.

 

结点的层是其父结点的层号加1,而树的高度或深度是树中所有结点的最大层号.

2.什么是二叉树

定义:二叉树是有限多个结点的集合,这个集合或者是空集,或者由一个根结点和两棵互不相交的

、分别称为左子树和右子树的二叉树组成。

 

二叉树的主要特点是对任意给定结点的度都不会超过二，二叉树和树的区别如下：

a) 树至少要含有一个结点，而二叉树可以为空

b) 二叉树可以根据子树的顺序来区分不同的二叉树，而树不行

3. 二叉树的遍历

      

a) 中序遍历,从二叉树的根结点开始，向树的左下方移动，直到遇到空结点为止，然后访问空结点的父结点，接着遍历该结点的右子树

 

如上图所示，中序遍历的顺序为H,D,I,B,E,A,F C,G，遍历代码如下

void inorder(tree_pointer ptr)
{
   if(ptr)
   {
      inorder(ptr->left_child);
      printf("%d", ptr->data);
      inorder(ptr->right_child);
   }
}

 

b) 前序遍历,先访问结点，然后访问左分支上遇到的每一个结点，直到遇到空结点为止，然后返回到最近的有右儿子的祖先结点，并从该结点的右儿子开始继续遍历。

 

如上图所示，前序遍历的顺序为A,B,D,H,I,E,C,F,G，遍历代码如下 

void preorder(tree_pointer ptr)
{
   if(ptr)
   {

      printf("%d", ptr->data);
      inorder(ptr->left_child);
      inorder(ptr->right_child);
   }
}

 

c) 后序遍历,先访问结点的左右儿子，再对该结点进行访问

 

如上图所示，后序遍历的顺序为H,I,D,E,B,F,G,C,A，遍历代码如下  

void postorder(tree_pointer ptr)
{
   if(ptr)
   {
      inorder(ptr->left_child);
      inorder(ptr->right_child);

      printf("%d", ptr->data);
   }
}

 

3. 线索二叉树

从上图可发现一个规律，当二叉树使用链接式存储表示时，空链的数目大于非空链的数目，即在总共2n个链中，有n+1个是空链。

线索二叉树使用指向其它结点的指针（线索）代替这些空链，它们具有以下特性：

a) 如果结点的左儿子ptr->left_child为空，则在中序遍历中，用指向ptr之前访问的结点的指针代替ptr->left_child

b) 如果结点的右儿子ptr->right_child为空，则在中序遍历中，用指向ptr之后访问的结点的指针代替ptr->right_child

还是以上图为例，对于中序遍历，访问顺序为H,D,I,B,E,A,F C,G，可以看到，结点H的左右子节点都为空，因此，使用线索二叉树表示时，H结点的左儿子不确定（在访问顺序中H已是第一位），H结点的右儿子的线索可确定为D。

很明显，在线索二叉树中，需要额外增加域用以记录这些线索信息，结点结构如下所示：

typedef struct threaded_tree *threaded_pointer;

struct threaded_tree{
   short int left_thread;//当left_thread为真时，left_child记录为线索
   threaded_pointer left_child;
   char data;
   short int right_thread;//当right_thread为真时，right_child记录为线索
   threaded_pointer right_child;
}

４．特殊二叉树

a)倾斜树，只有左儿子或只有右儿子的树

b)满二叉树，深度为k，具有2^k -1个结点的二叉树

c)完全二叉树，从第一层的根结点开始编号，然后对第二层的所有结点进行编号，以此类推，同一层结点按照从左到右的顺序进行编号(注意，只是编号，并不代表关键字)．

5. 堆

堆是一种完全二叉树,如下图所示,分为最大堆和最小堆:

a)最大堆(最大树),在树中,如果一个结点有儿子结点,其关健字值都不小于其儿子结点的关健字值

b)最小堆,与最小堆相反,如果一个结点有儿子结点,其关健字值都不大于其儿子结点的关健字值.

经常使用堆来实现优先级队列,其插入操作与删除操作时间复杂度都为O(log2^n),现在简单说明一下这些操作的过程:

a)最大堆的插入操作.因为堆是完全二叉树,因此插入的位置已确定在上图2的第7位中,插入后要判断是否小于父节点的关键值，对于最大堆而言，如果不是的话，则需要与父节点交换位置以符合最大堆的定义（所有子结点的值必须小于父结点的关键值）

b)最大堆的删除动作．从最大堆删除元素时，总是从根节点删除，删除过程分下面几步：

• 删除根节点元素
• 使用最后一个元素替换根节点
• 循环比较根节点与子节点，使其符合堆定义

６．二叉查找树

从第5节可以看到，堆非常适合用于优先级对列中（节点从最后添加，从根开始删除），相对应的，堆并不适合用于删除任意元素的应用．

当进行插入、删除和查找操作时，二叉查找树的性能是最好的，那什么是二叉查找树呢？

二叉查找树是一棵二叉树，可以为空也可以不为空，具有如下性质：

a)每个元素都有关键字，关键字是唯一的

b)非空左子树的关键字一定小于其子树根结点的关键字

c)非空右子树的关键字一定大于其子树根结点的关键字

以上定义可以看到，二叉查找树与堆不一样，它并不是一个完全二叉树，二叉查找树的递归查找表示起来比较简单：

tree_pointer search(tree_pointer root, int key)
{
   if(!root) return NULL;
   if(key == root->data) return root;

   if(key < root->data)
      return search(root->left_child, key);
   return search(root->right_child, key);
}

二叉查找树的插入

因为二叉查找树的关键字是唯一的，因此在做插入操作前必须通过查找确定其关键字的唯一性。如果没有找到有重合的关键字，则返回最后查找的节点指针，而新节点将在该节点指针中插入。因此，可以看出，二叉查找树的插入过程中，树的结点是不需要改变，新结点一定是在叶结点中删除。

二叉查找树的删除

对于非叶结点的删除可以使用左子树的最大元素或右子树的最小元素代替删除结点。