树与二叉树

树与二叉树

1.相关概念

1.树的基本概念

1.空树：结点树为0的树

2.非空树：

1）有且仅有一个根节点

2）没有后继节点的节点称为“叶子结点”

3）有后继节点的节点称为“非叶子结点”

3.除了根节点外，任何一个节点都有且仅有一个前驱；每个节点可以有0个或多个后继

4.路径：只能从上往下；路径长度，路径经过的节点个数

2.节点之间的关系描述

1.节点关系

1）祖先节点

2）子孙节点

3）双亲节点（父节点）

4）孩子节点

5）兄弟节点

6）堂兄弟节点（在同一层）

2.属性

1）节点的层次（深度）——从上往下数

2）节点的高度——从下往上数

3）树的高度（深度）——总共多少层

4）节点的度——有几个孩子（分支）

5）树的度——各个节点的度的最大值

3.有序树&无序树

1.有序树——从逻辑上看，树中节点的各子树从左至右是有次序的，不能互换

2.无序树——逻辑上看，树中节点的各子树从左至右是无次序的，可以互换

4.森林

森林是m（m > 0）颗互不相交的树的集合

注意：森林和树的相互转化问题

2.树的常见性质

1.节点数 = 总度数 + 1

2.度为m的树和m叉树

3.度为m的树第i层至多有m^(i - 1)个节点（i>=1）

4.高度为h的m叉树至多有多少个节点

3.二叉树

1.基本概念

2.满二叉树&完全二叉树

3.二叉排序树

4.平衡二叉树

左右子树的深度之差不能超过1

5.二叉树的性质

完全二叉树：

6.树的存储结构

1.双亲表示法：每个节点中保存指向双亲的“指针”==>适合用顺序存储结构（数组），链式结构无法访问叶节点

2.孩子表示法：顺序+链式：找孩子方便，找双亲不方便

3.孩子兄弟表示法：链式，左指针指向做孩子，右指针指向兄弟

7.树和二叉树的转化

8.森林和二叉树的转换

将森林中的每棵树转换为二叉树，然后将每颗树的根节点当做兄弟节点

二叉树转为森林，则右子树中的节点是每颗树的根节点

9.树和森林的遍历

1.树的遍历

1）先根遍历

根节点->左子树先跟遍历->右子树先根遍历

树的先根遍历与树转化为二叉树后的先序遍历结果一致

2）后根遍历

左子树先跟遍历->右子树先根遍历->根节点

树的后根遍历序列与这棵树的相应二叉树的中序序列相同

3）层序遍历

和二叉树的层序遍历类似

2.森林的遍历

1）先序遍历：依次对每个树进行先序序列；与森林转化为二叉树的先序遍历结果一致

2）中序遍历：等同于依次对各个树进行后根遍历，与森林转化为二叉树的中序遍历结果一致

3.总结

4.二叉树的存储结构

1.顺序存储

#define MaxSize 100
struct TreeNode{
  ElemType value;        //节点中的数据元素
  bool isEmpty;        //节点是否为空
};
//定义一个长度为MaxSize的数组t，按照从上至下，从左至右的顺序依次存储完全二叉树中的各个节点
TreeNode t[MaxSize];

void Init(){
  for(int i = 0; i < MaxSize; ++i){
    t[i].isEmpty = true;
  }
}

2.链式存储

代码：

struct ElemType{
  int value;
};

typedef struct BiTNode{
  ElemType data;
  struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

BiTree root = NULL;

//插入根节点
root = (BiTree)malloc(sizeof(BiTNode));
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;
//新节点p做为根节点的左子树
BiTNode *p = (BiTNode*)malloc(sizeof(BiTNode));
p->data = {2};
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p;

5.二叉树的遍历

遍历：按照某种次序访问所有节点

1.先序遍历

根左右

void PreOrder(BiTree T){
  if(T != NULL){
    visit(T);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
  }
}

2.中序遍历

左根右

void InOrder(BiTree T){
  if(T != NULL){
    InOrder(T->lchild);
    visit(T);
    InOrder(T->rchild);
  }
}

3.后序遍历

左右根

void PostOrder(BiTree T){
  if(T != NULL){
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    visit(T);
  }
}

4.遍历算法的应用

1.求树的深度

int treeDepth(BiTree T){
  if(T == NULL){
    return 0;
  }
  int l = treeDepth(T->lchild);
  int r = treeDepth(T->rchild);
  return l > r ? l + 1: r + 1;
}

5.层序遍历

设置辅助队列

void level(BiTree T){
  if(T == NULL){
    return;
  }
  queue<BiTree> q;
  q.push(T);
  while(!q.empty()){
    BiTree* p = q.top;
    q.pop();
    visit(p);
    if(p->lchild != NULL){
      q.push(p->lchild);
    }
    if(p->rchild != NULL){
      q.push(p->rchild);
    }
  }
}

6.构建二叉树

注意：如果只给出一颗二叉树的 前/中/后/层 序遍历中的一种，不能唯一确定一颗二叉树

以下三种可以唯一确定一个颗二叉树

1.前序 + 中序遍历序列

2.后序 + 中序遍历序列

3.层序 + 中序遍历序列

注意：层序遍历的特点是：先是根节点 -》左子树的根—》右子树的根

6.线索二叉树

1.线索二叉树的作用

普通二叉树的遍历，只能从根节点开始，无法从某个节点开始遍历其他节点，找前驱、后继很不方便，遍历操作必须从根开始

线索二叉树：方便从一个指定节点出发，找到其前驱、后继；方便遍历

2.中序线索化

二叉树的线索化：中序线索化、先序线索化、后序线索化

typedef struct ThreadNode{
  ElemType data;
  struct ThreadNode *lchild,*rchild;
  int ltag,rtag;
}ThreadNode,*ThreadTree;

//全局变量
ThreadNode *pre = NULL;

void CreateInThread(ThreadTree T){
  pre = NULLL;
  if(T != NULL){
    InThread(T);
    //修改最后一个节点的tag位
    if(pre->rchild == NULL){
      pre->rtag = 1;
    }
  }
}

//中序遍历二叉树，一边遍历一边线索化
void InThread(ThreadTree T){
  if(T != NULL){
    InThread(T->lchild);
    visit(T);
    InThread(T->rchild);
  }
}

//线索：q指针修改左指针，pre修改右指针
void visit(ThreadNode *q){
  //左指针为空，指向前驱q->lchild = pre
  if(q->lchild == NULL){
    q->lchild = pre;
    q->ltag = 1;
  }
  //右指针为空，指向后继pre->rchild = q
  if(pre != NULL && pre->rchild == NULL){
    pre->rchild = q;
    pre->rtag = 1;
  }
  pre = q;
}

3.先序线索化

//全局变量
ThreadNode *pre = NULL;

void CreateInThread(ThreadTree T){
  pre = NULLL;
  if(T != NULL){
    InThread(T);
    //修改最后一个节点的tag位
    if(pre->rchild == NULL){
      pre->rtag = 1;
    }
  }
}

//中序遍历二叉树，一边遍历一边线索化
void PreThread(ThreadTree T){
  if(T != NULL){
    visit(T);
    //只用ltag=0即左指针指向孩子时，才访问，否则不访问
    //不设置该条件会导致死循环
    if(T->ltah == 0)
        InThread(T->lchild);
    InThread(T->rchild);
  }
}

//线索：q指针修改左指针，pre修改右指针
void visit(ThreadNode *q){
  //左指针为空，指向前驱q->lchild = pre
  if(q->lchild == NULL){
    q->lchild = pre;
    q->ltag = 1;
  }
  //右指针为空，指向后继pre->rchild = q
  if(pre != NULL && pre->rchild == NULL){
    pre->rchild = q;
    pre->rtag = 1;
  }
  pre = q;
}

4.后序线索化

//全局变量
ThreadNode *pre = NULL;

void CreateInThread(ThreadTree T){
  pre = NULLL;
  if(T != NULL){
    InThread(T);
    //修改最后一个节点的tag位
    if(pre->rchild == NULL){
      pre->rtag = 1;
    }
  }
}

void PostThread(ThreadTree T){
  if(T != NULL){
    PostThread(T->lchild);
    PostThread(T->rchild);
    visit(T);
  }
}

void visit(ThreadNode *q){
  if(q->lchild == NULL){
    q->lchild = pre;
    q->ltag = 1;
  }
  if(pre != NULL && pre->rchild == NULL){
    pre->rchild = q;
    pre->rtag = 1;
  }
  pre = q;
}

注意：

1、线索化，最重要的是为了方便找当前节点的前驱和后继，因此在线索化过程中，如果发现当前指针q的左子树为空，则指向前驱节点，如果发现前驱节点pre的右子树为空，则pre的后继一定是q

2、线序需要在visit中特殊判断，否则会导致死循环

5.线索二叉树找前驱/后继

1、中序线索二叉树找前驱/后继

代码多看几遍！！！！

在中序中，根节点的后继一定是右子树中最左下的节点，根节点的前驱一定是左子树最右下的节点

//找到以p为根的子树中，第一个被中序遍历的节点
ThreadNode *FirstNode(ThreadNode *p){
  //没有被线索化
  while(p->ltag == 0) p = p->lchild;
  return p;
}
//在中序线索二叉树中找到p的后继节点
ThreadNode* NextNode(ThreadNode* p){
  //如果没有被线索化，右子树中最左下节点
  if(p->trag == 0) return FirstNode(p->rchild);
  else return p->rchild;
}

//找到以p为根的子树中，最后一个被中序遍历的节点
ThreadNode* LastNode(ThreadNode *p){
  while(p->rtag == 0) p = p->rchild;
  return p;
}

//在中序线索二叉树中找到p的前驱节点
ThreadNode* PreNode(ThreadNode *p){
  //如果没有被线索化,左子树中最右下的节点
  if(p->ltag == 0) return LastNode(p->lchild);
  else return p->lchild;
}

//对中序线索二叉树进行中序遍历，利用线索实现非递归算法
void Inorder(ThreadNode *T){
  for(ThreadNode* p = FirstNode(T); p != NULL; p = NextNode(p))
    visit(p);
}

//对中序线索二叉树进行逆中序遍历，利用线索实现非递归算法
void RevInorder(ThreadNode *T){
  for(ThreadNode *p = LastNode(T); p != NULL; p = PreNode(p))
    visit(p);
}

2、先序线索二叉树找前驱/后继

在先序中，左右子树中的节点只可能是根的后继，不可能是前驱，因此是无法找到当前节点的前驱和后继的，只能用土办法从根节点开始遍历

如果二叉树中有父节点指针，且该父节点存在，则可以找到前驱：如果该节点是父节点的右孩子，则前驱是父节点的左子树中先序遍历的最后一个节点

3、后序线索二叉树找前驱/后继

在后序遍历中，左右子树只可能是当前节点的前驱，不可能是后继，除非从根节点开始遍历；

如果二叉树中有父节点指针，则可以找到后继：

6.总结

7.二叉排序树BST

1.定义

左子树节点值 < 根节点值 < 右子树节点值

进行中序遍历，可以得到一个递增的有序序列

typedef struct BSTNode{
  int key;
  struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

2.二叉排序树的查找

//非递归版本  最坏空间复杂度 O(1)
BSTNode *BST_Search(BSTree T, int key){
  while(T != NULL && key != T->key){
    if(key < T->key){
      T = T->lchild);
    }
    else{
      T = T->rchild;
    }
  }
  return T;
}

//递归版本        最坏空间复杂度 O(N)
BSTNode *BST_Search2(BSTree T, int key){
  if(T == NULL){
    return NULL;
  }
  if(key == T->key){
    return T;
  }
  if(key < T->key){
    BST_Search2(T->lchild, key);
  }
  else{
    BST_Search2(T->rchild, key);
  }
}

查找效率分析：

查找成功时的平均查找长度：

ASL = 每层的层数 * 每层的节点数 加起来

查找失败时的平均查找长度:

ASL = 查找失败时指针可能停留的位置所在的层数 加起来 除以 可能停留位置的个数

3.二叉排序树的插入

插入操作不能破坏平衡二叉树的性质；注意二叉排序树中不允许有两个值相等的节点

bool BST_Insert(BSTree T, int key){
  if(T == NULL){
    T = (BSTree)malloc(sizeof(BSTNode));
    T->key = key;
    T->lchild = NULL;
    T->rchild = NULL;
    return true;
  }
  else if(k == T->key){
    return false;            //值已经存在，插入失败
  }
  else if(key < T->key){
    BST_Insert(T->lchild, key);
  }
  else{
    BST_Insert(T->rchild, key);
  }
}

//构建一颗二叉排序树
str = [5,7,3,6,8,1,2];
BSTree T = NULL;

void Creat_BST(BSTree &T, int str[], int n){
  T = NULL;
  int i = 0;
  while(i < n){
    BST_Insert(T, str[i]);
    i++;
  }
}

4.二叉树的删除

//叶子节点：直接删除
//只有左子树：左子树替换要删除的节点
//只有右子树：右子树直接疾患要删除的节点
//既有左子树，又有右子树：
//            1)找后继：找到中序遍历的下一个节点，替换当前节点
//            2)找前驱：找到中序遍历的前一个节点，替换当前节点
//            替换后删除前驱或者后继

8.平衡二叉树AVL

1.定义

树上的任一节点的左子树和右子树的高度差不超过1

节点的平衡因子 = 左子树高 - 右子树高

2.插入操作

插入操作类似BST，但是为了保持平衡因子，所以需要调整

3.插入新节点后调整问题

调整策略	备注
LL	在A的左孩子的左子树中插入导致不平衡
RR	在A的右孩子的右子树中插入导致不平衡
LR	在A的左孩子的右子树中插入导致不平衡
RL	在A的右孩子的左子树中插入导致不平衡
LL

RR

LR:

RL

4.查找效率

最坏情况下，查找一个关键字最多需要对比n次，即查找操作的时间复杂度不可能超过O(h)

9.哈夫曼树

1.结点的权

有某种显示含义的数值（如：表示节点的重要性）

2.节点带权路径长度

从树的根到该节点的路径长度（经过的边数）与该节点上权值的乘积

3.树的带权路径长度

树中所有叶节点的带权路径长度之和（WPL）

4.哈夫曼树

1.定义

在含有n个带权叶节点的二叉树中，其中带权路劲长度WPL最小的二叉树称为哈夫曼树，也称为最优二叉树

2.构造

5.哈夫曼编码

可变长度编码——允许对不同字符用不等长的二进制位表示

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码

注意：因为哈夫曼树不唯一，所以哈夫曼编码不唯一