866数据结构笔记 - 第五章树和二叉树

度为m的树和m叉树的区别？
满二叉树和完全二叉树有什么特点？
树和二叉树的常考性质（第i层最多结点、高度为h最多结点、最小高度h）
N个结点二叉链表空链域有多少？
二叉树和遍历序列之间如何转换（必考）
层次遍历的思想和代码
线索二叉树怎么构造？
孩子兄弟表示法怎么做？
树的先根和后根遍历与二叉树遍历有什么关系？
二叉排序树怎么逐步构造？相同值怎么处理？
二叉排序树插入和删除代码
二叉排序树的删除情况和ASL计算
平衡二叉树的逐步构造
高度为h的平衡二叉树最少结点个数？
哈夫曼树构造及哈夫曼编码
如何判断是否为完全二叉树？
如何判断是否是二叉排序树？
如何判断是否是平衡二叉树？

一、概念

树的基本概念：节点，边，根节点，叶子结点，分支结点，子树，父结点（双亲节点），孩子结点，祖先结点，子孙结点，兄弟结点，堂兄弟结点。
结点之间的路径：两个结点之间所经过结点序列。
结点路径长度：路径上所经过的边个数。
树的路径长度：树根到每个结点的路径长度和。
结点层次（深度）：从根结点，自顶向下逐层累加。
结点高度：从叶子结点，从底向上逐层累加。
树的高度：树中结点最大层数。
结点的度：结点的分支数。
树的度：树中各结点度的最大值。

度为m的树：至少由一个结点度为m，一定是非空树。

m叉树：允许所有结点的度都小于等于m，可以是空树。

有序树vs无序树：逻辑上看，各子树是否有序。
森林：由m（m>=0）棵互不相交的树的集合。

二叉树基本概念：

二叉树：n(n>=0)个结点的有限集，它或者是空集（n=0），或者由一个根结点及两颗互不相交的分别称作这个根的左子树和右子树的二叉树组成。
满二叉树：一颗深度为k且有2^k-1个结点的二叉树称为满二叉树。每一层上的结点数都达到最大。叶子全部在最低层。

特点：

1.只有最后一层有叶子结点

2.不存在度为1的结点。

3.按层序从1编号，结点i的左孩子为2i，右孩子为2i+1，父结点i/2

完全二叉树：深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树。

特点：

1.只有最后两层有叶子结点

2.最多存在一个度为1的结点。

3.按层序从1编号，结点i的左孩子为2i，右孩子为2i+1，父结点i/2

4.i<=n/2为分支结点，否则为叶子结点

二叉排序树：左子树关键字 < 根结点关键字 <= 右子树关键字（866特别之处）
平衡二叉树：树上任一结点左右子树深度之差不超过1。

树常考性质：（图片来自《王道》数据结构笔记整理2022_胖胖的懒羊羊的博客-CSDN博客_王道数据结构）

二叉树常考性质：

在二叉树的第i层上至多有2^（i-1）个结点（i>1）。
深度为k的二叉树至多有2^k-1个结点（k>=1）。
对任何一颗二叉树T，如果其叶子数为n0，度为2的结点数为n2，则n0=n2+1.
具有n个结点的完全二叉树的深度为(log2N)+1。
完全二叉树有2k(偶数)个结点则n1（度为1结点数）=1，n0=k，n2=k-1。
完全二叉树有2k-1(奇数)个结点则n1（度为1结点数）=0，n0=k，n2=k-1。

二、二叉树存储结构

1.顺序存储

二叉树的顺序存储中，把二叉树的结点编号与完全二叉树对应起来。只适合存储完全二叉树。最坏情况：高度为h，只有n个结点单支树，也至少需要2^h -1 个存储单元。

// 初始化让所有结点的标记为空，让第一个位置空缺
// 保证数组下标和结点编号一致。

#define MaxSize 100

struct TreeNode{
   ElemType value; //结点中的数据元素
   bool isEmpty;   //结点是否为空
}

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

2.链式存储

n个结点的二叉链表共有n+1个空链域。

typedef struct BiTnode{
   ElemType data;          //数据域
   struct BiTNode *lchild, *rchild; //左、右孩子指针
}BiTNode, *BiTree;

三、二叉树遍历

1.分类

先序遍历（前序遍历）：根左右 NLR
中序遍历：左根右 LNR
后序遍历：左右根 LRN
层次遍历

2.先序遍历

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

void PreOrder(BiTree T){
   if(T!=NULL){
      visit(T);                 //访问根结点
      PreOrder(T->lchild);      //递归遍历左子树
      PreOrder(T->rchild);      //递归遍历右子树
   }
}

3.中序遍历

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

void InOrder(BiTree T){
   if(T!=NULL){
      InOrder(T->lchild);       //递归遍历左子树
      visit(T);                 //访问根结点
      InOrder(T->rchild);       //递归遍历右子树
   }
}

4.后序遍历

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

void PostOrder(BiTree T){
   if(T!=NULL){
      PostOrder(T->lchild);       //递归遍历左子树    
      PostOrder(T->rchild);       //递归遍历右子树
      visit(T);                 //访问根结点
   }
}

5.层次遍历

初始化一个辅助队列。
根节点入队。
若队列非空，则队头结点出队，访问该结点，依次将其左、右孩子插入队尾（如果有的话）。
重复以上操作直至队列为空。

//二叉树的结点(链式存储)
typedef struct BiTnode{
   ElemType data;          
   struct BiTNode *lchild, *rchild; 
}BiTNode, *BiTree;

//链式队列结点
typedef struct LinkNode{
   BiTNode * data;
   typedef LinkNode *next;
}LinkNode;

typedef struct{
   LinkNode *front, *rear;  
}LinkQueue;

//层序遍历
void LevelOrder(BiTree T){
   LinkQueue Q;
   InitQueue (Q);          //初始化辅助队列
   BiTree p;
   EnQueue(Q,T);           //将根节点入队
   while(!isEmpty(Q)){     //队列不空则循环
      DeQueue(Q,p);        //队头结点出队
      visit(p);            //访问出队结点
      if(p->lchild != NULL)
         EnQueue(Q,p->lchild);   //左孩子入队
      if(p->rchild != NULL)
         EnQueue(Q,p->rchild);   //右孩子入队
   }
}

6.由遍历序列构造二叉树

先序序列 + 中序序列
后序序列 + 中序序列
层序序列 + 中序序列
key: 找到树的根节点，并根据中序序列划分左右子树，再找到左右子树根节点。

四、线索二叉树

在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。在普通二叉树结点上增加了两个标志位，Itag，rtag

Itag == 1，lchild指向前驱。
Itag == 0，lchild指向左孩子。
rtag == 1，rchild指向后继。
rtag == 0，rchild指向右孩子。

//线索二叉树结点
typedef struct ThreadNode{
   ElemType data;
   struct ThreadNode *lchild, *rchild;
   int ltag, rtag;                // 左、右线索标志
}ThreadNode, *ThreadTree;

五、树的存储结构

1.双亲表示法

顺序存储、每个结点中保存指向双亲的指针。

增：新增数据元素，无需按逻辑上的次序存储；（需要更改结点数n）
删（叶子结点）：① 将伪指针域设置为-1；②用后面的数据填补；（需要更改结点数n）
查询：①优点-查指定结点的双亲很方便；②缺点-查指定结点的孩子只能从头遍历，空数据导致遍历更慢。

#define MAX_TREE_SIZE 100  //树中最多结点数

typedef struct{      //树的结点定义
   ElemType data; 
   int parent;      //双亲位置域
}PTNode;

typedef struct{                   //树的类型定义
   PTNode nodes[MAX_TREE_SIZE];   //双亲表示
   int n;                         //结点数
}PTree;

2.孩子表示法

孩子链表：把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储，则n个结点有n个孩子链表（叶子的孩子链表为空表）。而n个头结点又组成一个线性表，用顺序表（含n个元素的结构数组）存储。

struct CTNode{
   int child;    //孩子结点在数组中的位置
   struct CTNode *next;    // 下一个孩子
};

typedef struct{
   ElemType data;
   struct CTNode *firstChild;    // 第一个孩子
}CTBox;

typedef struct{
   CTBox nodes[MAX_TREE_SIZE];
   int n, r;   // 结点数和根的位置
}CTree;

3.孩子兄弟表示法（链式）

左孩子右兄弟，将树转换成二叉树。

typedef struct CSNode{
   ElemType data;                               //数据域
   struct CSNode *firstchild, *nextsibling;     
//第一个孩子和右兄弟指针, *firstchild 看作左指针，*nextsibling看作右指针
}CSNode. *CSTree;

六、树和森林的遍历

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

七、二叉排序树（BST）/ 二叉搜索树

1.定义

王道：左子树结点值 < 根结点值 < 右子树结点值（默认无关键字相同结点）
866数据结构：左子树结点值 < 根结点值 <= 右子树结点值（重点考察关键字相同结点）

2.操作

查找

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

//在二叉排序树中查找值为key的结点（非递归）
//最坏空间复杂度：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;
}

//在二叉排序树中查找值为key的结点（递归）
//最坏空间复杂度：O(h)
BSTNode *BSTSearch(BSTree T, int key){
   if(T == NULL)
      return NULL;
   if(Kry == T->key)
      return T;
   else if(key < T->key)
      return BSTSearch(T->lchild, key);
   else 
      return BSTSearch(T->rchild, key);
}

插入

//在二叉排序树中插入关键字为k的新结点（递归）
//最坏空间复杂度：O(h)
int BST_Insert(BSTree &T, int k){
   if(T==NULL){           //原树为空，新插入的结点为根结点
      T = (BSTree)malloc(sizeof(BSTNode));
      T->key = k;
      T->lchild = T->rchild = NULL;
      return 1;                       //插入成功
   }
   // else if(K == T->key)               //树中存在相同关键字的结点，插入右孩子
   //     return 0;
   else if(k < T->key)                 
      return BST_Insert(T->lchild,k);
   else 
      return BST_Insert(T->rchild,k);
}

逐步构造

删除

删除叶子结点：直接删除，不会破坏BST性质。
被删除结点只有一棵左子树或者右子树：让该子树成为父节点。
被删除结点既有左子树又有右子树：让其直接前驱（左子树中最大）或直接后继（右子树中最大）替换，然后删除这个直接前驱（直接后继）。

3.查找效率分析

查找长度：查找运算中，需要对比关键字的次数，反映了查找操作时间复杂度。
最好情况：n个结点二叉树最小高度logn+1，O(logn)
最坏情况：每个结点只有一个分支，O(n)

八、平衡二叉树（AVL树）

定义：在插入和删除二叉树的结点时，要保证任意结点的左右子树的高度差的绝对值不超过1，将这样的树称为平衡二叉树。
结点平衡因子：左子树高 - 右子树高（平衡二叉树平衡因子只能是0,1,2）
LL: 在A结点的左孩子的左子树中插入导致不平衡。调整： A的左孩子结点右上旋
RR: 在A结点的右孩子的右子树中插入导致不平衡。调整： A的右孩子结点左上旋
LR: 在A结点的左孩子的右子树中插入导致不平衡。调整： A的左孩子的右孩子，先左上旋再右上旋
RL: 在A结点的右孩子的左子树中插入导致不平衡。调整： A的右孩子的左孩子，先右上旋再左上旋
查找效率分析：若树高为h，则最坏情况下，查找一个关键字最多需要对比h次，即查找操作的时间复杂度不可能超过O(h)。
高为h的平衡二叉树最少结点数：Nk=Nk-1+Nk-2+1（N0=0，N1=1）

//平衡二叉树结点
typedef struct AVLNode{
   int key;         //数据域
   int balance;     //平衡因子
   struct AVLNode *lchild; *rchild; 
}AVLNode, *AVLTree;

九、哈夫曼树

1.概念：

结点的权：某种特定含义的数值。
结点的带权路径长度：从根节点到该结点之间的路径长度与该节点的权的乘积。
树的带权路径长度：树中所有叶子结点的带权路径长度。
哈夫曼树（最优二叉树）：带权路径最短的树。

2.构造哈夫曼树：

根据给定的n个权值，构建n棵只有根结点的二叉树，这n棵二叉树构成一个森林F。
在森林中选取两棵根结点的权值最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上的权值之和。
在森林F中删除这两颗树，同时将新得到的二叉树加入F中。
重复2和3，直到F中只含一颗树时为止。这棵树便是哈夫曼树。

3.哈夫曼树特点：

没有度为1的结点（每个非叶子结点都是由两个最小值的结点构成）
n个叶子结点的哈夫曼树总共有2n-1个结点。
每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
哈夫曼树并不唯一，但WPL必然相同且最优。

4.哈夫曼编码：左分支编码为字符0，右分支编码为字符1，将从根节点到叶子节点的路径上分支字符组成的字符串作为叶子节点字符的编码，这便是赫夫曼编码。

十、代码题（重点题目）

866数据结构考研真题：

22年：判断是否为完全二叉树。
20年：哈夫曼编码。
19年：二叉排序树种查找值为k的结点并删除。
17年：统计二叉树总正整数个数。
15年：二叉树中度为2的结点个数。
14年：二叉树结点个数。
13年：二叉树叶子结点个数，广度优先遍历。
12年：深度为h的平衡二叉树最少结点个数。
11年：二叉树中是否存在key,并且路径长度为length。
11年：判断是否为二叉排序树。
10年：二叉树中是否存在度为1的结点。
07年：判断是否为完全二叉树。
06年：按data域递增访问BST。
05年：求二叉树高度。
03年：二叉树中任意两个结点最小距离。

湖大本科期末题：

交换左右子树。
统计二叉树中叶子结点个数。
递归求二叉树高度。
打印data域为数字的字符。
求二叉树中值为x的双亲。
建立二叉排序树。
判断两个二叉树是否相同。
二叉树是否为二叉排序树。
结点在二叉排序树中层次。
二叉树中所有结点之和。
二叉排序树中查找值为x的结点。
二叉树中最小值。
判断二叉树是否为斜树。
判断是否为平衡二叉树。
求二叉树中距离根最近的叶子结点高度。

1.编写后序遍历二叉树的非递归算法

/*
算法思想：后序非递归遍历二叉树的顺序是先访问左子树，再访问右子树，
最后访问根结点。当用堆栈来存储结点时，必须分清返回根结点时是从左子树返回的还是从右子树返回的。
所以，使用辅助指针r，其指向最近访问过的结点。也可在结点中增加一个标志域，记录是否已被访问。
PS:访问一个结点*p时，栈中结点恰好是*p结点的所有祖先。
从栈底到栈顶结点再加上*p结点，刚好构成从根结点到*p结点的一条路径。
在很多算法设计中都利用了这一特性求解，如求根结点到某结点的路径、
求两个结点的最近公共祖先等，都可以利用这个思路来实现。
*/
void postOrder(BiTree T)
{
    InitStack(S);
    p = T;
    r = NULL;
    while(p|| !IsEmpty(S))
    {
        if(p){   //走到最左边
           push(S,p);
           p = p->lchild;
        }
        else{  //向右
            GetTop(S,p);  //取栈顶结点
            if(p->rchild && p->rchild != r)  //若右子树存在，且未被访问过
            {
                p = p->rchild;  //转向右
                push(S,p);      //压入栈
                p = p->lchild;  //再走到最左
            }
            else{               //否则，弹出结点并访问
                pop(S,p);       //将结点弹出
                visit(p->data); //访问该结点
                r = p;          //记录最近访问过的结点
                p = NULL;       //结点访问完后，重置该指针
            }
        }//else
    }//while
}

2.编写二叉树的自下而上、自右到左的层次遍历算法

/*
一般的二又树层次遍历是自上而下、从左到右，这里的遍历顺序恰好相反。
算法思想：利用原有的层次遍历算法，
出队的同时将各结点指针入栈在所有结点入栈后再从栈顶开始依次访问即为所求的算法。
具体实现如下：
1）把根结点入队列。
2）把一个元素出队列，遍历这个元素
3）依次把这个元素的右孩子、左孩子入队列。
4）若队列不空，则跳到（2），否则结束。
*/
void InvertLevel(BiTree bt){
	Stack s;
    Queue Q;
    if(bt!=NULL)
    {
        InitStack(s);  //栈初始化，栈中存放二叉树结点的指针
        InitQueue(Q);  //队列初始化，队列中存放二叉树结点的指针
        EnQueue(Q,bt);
        while(IsEmpty(Q)==false) //从上而下层次遍历
        {
            DeQueue(Q,p);
            Push(s,p); //出队，入栈
            if(p->lchild)
                EnQueue(Q,p->lchild); //若左子女不空，则入队列
            if(p->rchild)
                EnQueue(Q,p->rchild); //若右子女不空，则入队列
        }
        while(IsEmpty(s) == false){
            Pop(s,p);
            visit(p->data);
        }  //自下而上、自右到左的层次遍历
    }//if结束
}

3.非递归算法求二叉树的高度

/*
采用层次遍历的算法，设置变量1eve1记录当前结点所在的层数，
设置变量last指向当前层的最右结点，每次层次遍历出队时与last 指针比较，
若两者相等，则层数加1，并让last指向下一层的最右结点，直到遍历完成。
1eve1的值即为二叉树的高度。
*/
int Btdepth(BiTree T)
{
    if(!T)
        return 0;  //树空，高度为0
    int front= -1, rear = -1;
    int last = 0,level = 0; //last指向下一层第一个结点的位置
    BiTree Q[MaxSize]; //设置队列Q，元素是二叉树结点指针且容量足够
    Q[++rear] = T;  //将根结点入队
    BiTree p;
    while(front < rear) //队不空，则循环
    { 
        p = Q[++front]; //队列元素出队，即正在访问的结点
        if(p->lchild)
            Q[++rear] = p->lchild;  //左孩子入队
        if(p->rchild)
            Q[++rear] = p->rchild; //右孩子入队
        if(front == last){  //处理该层的最右结点
            level++; //层数增1
            last = rear; //last指向下层
        }
     }
    return level;
}

/*
求某层的结点个数、每层的结点个数、树的最大宽度等，都采用与此题类似的思想。
当然，此题可编写递归算法，其实现如下
*/
int Btdepth2(BiTree T)
{
    if(T==NULL)
        return 0;  //空树，高度为0
    ldep = Btdepth(T->lchild); //左子树高度
    rdep = Btdepth(T->rchild); //右子树高度
    if(ldep > rdep)
        return ldep+1; //树的高度为子树最大高度加根节点
    else
        return rdep+1;
}

4. 二叉树按二叉链表形式存储，写一个判别给定二叉树是否是完全二叉树的算法

/*
根据完全二叉树的定义，具有n个结点的完全二叉树与满二又树中编号从1～n的结点一一对应。
算法思想：采用层次遍历算法，将所有结点加入队列（包括空结点）。
遇到空结点时，查看其后是否有非空结点。若有，则二又树不是完全了叉树。
*/
bool IsComplete(BiTree T)
{
    InitQueue(Q);
    if(!T)
        return 1; //空树为满二叉树
    EnQueue(Q,T);
    while(!IsEmpty(Q))
    {
        DeQueue(Q,p);
        if(p)  //结点非空，将其左、右子树入队列
        {
            EnQueue(Q,p->lchild); 
            EnQueue(Q,p->rchild);
        }
        else   //结点为空，检查其后是否有非空结点
            while(!IsEmpty(Q)){
                DeQueue(Q,p);
                if(p)    //结点非空，则二叉树为非完全二叉树
                    return 0;
            }
    }
    return 1;
}

5.二叉树按二叉链表形式存储，计算一棵给定二叉树的所有双分支结点个数

/*
计算一棵二叉树b中所有双分支结点个数的递归模型f（b）如下:
f(b)=0		                            若b=NULL
f(b)=f(b->1chi1d) + f(b->rchild) + 1    若*b为双分支结点
f(b)=f(b->1chi1d) + f(b->rchild)        其他情况（*b为单分支结点或叶子结点）
*/
int DsonNodes(BiTree b)
{
    if(b==NULL)
    	return 0;
    else if(b->lchild!=NULL && b->rchild!=NULL)
        return DsonNodes(b->lchild) + DsonNodes(b->rchild)+1;
    else
        return DsonNodes(b->lchild) + DsonNodes(b->rchild);
}

6.二叉树B按二叉链表形式存储，编写一个树B中所有结点的左、右子树进行交换的函数。

/*
采用递归算法实现交换二叉树的左、右子树，
首先交换b结点的左孩子的左、右子树，
然后交换b结点的右孩子的左、右子树，
最后交换b结点的左、右孩子，当结点为空时递归结束（后序遍历的思想）。
*/
void swap(BiTree b)
{
    if(b){
        swap(b->lchild);  //递归地交换左子树
        swap(b->rchild);  //递归地交换右子树
        temp = b->lchild;  //交换左、右孩子结点
        b->lchild = b->rchild;
        b->rchild = temp;
    }
}

7.二叉树按二叉链表形式存储，求先序遍历序列中第 k (1<=k<=二叉树中结点个数) 个结点的值

/*
设置一个全局变量i记录已访问过的结点的序号，其初值是根结点在先序序列中的序号，即1.
当二叉树b为空时返回特殊字符，
当i==k时，表示找到了满足条件的结点，返回b->data;
当i<k时，递归地在左子树中查找，若
找到则返回该值，否则继续递归地在右子树中查找，并返回其结果。
本题实质上就是一个遍历算法的实现，只不过用一个全局变量来记录访问的序号，
求其他遍历序列的第k个结点也采用相似的方法。
二叉树的遍历算法可以引申出大量的算法题，因此考生务必要熟练掌握二又树的遍历算法。
*/
int i=1;  //遍历序号的全局变量
int PreNode(BiTree b,int k)
{
    if(b==NULL) //空结点，则返回特殊字符
        return '#'; //相等，则当前结点即为第k个结点
    if(i==k)
        return b->data;
    i++; //下一个结点
    ch = PreNode(b->lchild,k); //左子树中递归寻找
    if(ch !='#') //在左子树中，则返回该值
        return ch;
    ch = PreNode(b->rchild,k); //在右子树中递归寻找
    	return ch;
}

8. 二叉树按二叉链表形式存储，设计求二叉树T的WPL的算法

/*
(1) 给出算法的基本设计思想
(2) 给出二叉树结点的数据类型定义
(3) C++语言描述算法,关键之处给出注释
*/

/*
考查二叉树的带权路径长度，二叉树的带权路径长度为每个叶结点的深度与权值之积的总和，
可以使用先序遍历解决问题。
1）算法的基本设计思想。
基于先序递归遍历的算法思想是用一个static变量记录wpl，
把每个结点的深度作为递归函数的一个参数传递。
算法步骤如下：
① 若该结点是叶结点，则变量wpl加上该结点的深度与权值之积。
② 若该结点是非叶结点，则左子树不为空时，
对左子树调用递归算法，右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加1。
③最后返回计算出的wpl即可。

*/
// 二叉树结点的数据类型定义如下:
typedef struct BiTNode{
    int weight; 
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

int WPL(BiTree root){
	return wpl_PreOrder(root，0);
}

int wpl_Preorder(BiTree root,int deep){
	static int wpl=0;					//定义一个static变量存储wp1
	if(root->lchild==NULL && root->rchild==NULL)	//若为叶结点，累积wp1
		wpl += deep*root->weight;
    if(root->lchild !=NULL)				//若左子树不空，对左子树递归遍历
        wp1_PreOrder(root->1child,deep+1);
     if(root->rchild !=NULL)	//若右子树不空，对右子树递归遍历
        wp1_PreOrder(root->rchild,deep+1);
    return wpl;

9. 判断给定的二叉树是否是二叉排序树

/*
对二叉排序树来说，其中序遍历序列为一个递增有序序列。
因此，对给定的二叉树进行中序遍历，若始终能保持前一个值比后一个值小，
则说明该二又树是一棵二又排序树。
*/
int predt=-32767;//predt为全局变量，保存当前结点中序前驱的值，初值为-无穷。
int JudgeBST(BiTree bt){
	int b1,b2;
	if(bt==NULL)//空树
    	return 1;
	else{
		b1=JudgeBST(bt->1child);//判断左子树是否是二又排序树
		if(b1==0 || predt>=bt->data)//以若左子树返回值为0或前驱大于等于当前结点
			return 0; //不是二叉排序树
		predt=bt->data;//保存当前结点的关键字
		b2=JudgeBST(bt->rchild);//判断右子树
		return b2;   //返回右子树的结果
    }
}

10.设计一个算法，求出指定结点在给定二叉排序树中的层次

/*
算法思想：设二又树采用二又链表存储结构。在二叉排序树中，查找一次就下降一层。
因此，查找该结点所用的次数就是该结点在二又排序树中的层次。
采用二叉排序树非递归查找算法，用n保存查找层次，每查找一次，n就加1，直到找到相应的结点。
*/

int level(BiTree bt,BSTNode *p){
	//本算法计算给定结点在二叉排序树中的层次
	int n=0;//统计查找次数
	BiTree t=bt;
	if(bt!=NULL){
		n++;
		while(t->data!=p->data){
			if(t->data < p->data)//在左子树中查找
				t = t->lchild;
			else 				 //在右子树中查找
				t = t->rchild;
			n++;//层次加1
    	}
    }
    return n;
}

11.利用二叉树遍历的思想编写一个判断二叉树是否平衡二叉树的算法

/*
设置二叉树的平衡标记balance，标记返回二又树bt是否为平衡二叉树，若为平衡二叉树，
则返回1，否则返回0：h为二又树bt的高度。采用后序遍历的递归算法：
1）若bt为空，则高度为0，balance=1。
2）若bt仅有根结点，则高度为1，balance=1。
3）否则，对bt的左、右子树执行递归运算，返回左、右子树的高度和平衡标记，bt的高度
为最高子树的高度加1。若左、右子树的高度差大于1，则balance=0;若左、右子树的
高度差小于等于1，且左、右子树都平衡时，balance=1，否则balance=0。
*/

void Judge AVL（BiTree bt，int &balance，int sh）{
//本算法判断一个给定的二叉树是否为平衡二叉树
    int b1=0，br=0，hl=0，hr=0;//左、右子树的平衡标记和高度
    if（bt==NULL）{//空树，高度为0
        h=0;
        balance=1;
    }
    else if（bt->1child==NULL&6bt->xchild==NULL）{//仅有根结点，则高度为1
        h=1;
        balance=1;
    }
    Judge_AVL（bt->1child，bl，h1）;//递归判断左子树
    Judge_AVL（bts>rchild，br，hr）;//递归判断右子树
    h=（h1>hr？hl:hr）+1;
    if（abs（hl-hr）<2）//若子树高度差的绝对值<2，则看左、右子树是否都平衡
        balance=bl&&br;//逻辑与，即左、右子树都平衡时，二叉树平衡
    else
        balance=0;
}

12. 设计一个算法,求出给定二又排序树中最小和最大的关键字

/*
在一棵二又排序树中，最左下结点即为关键字最小的结点，最右下结点即为关键字最大的结点，
本算法只要找出这两个结点即可，而不需要比较关键字。
*/

int MinKey(BSTNode *bt){
    //求出二叉排序树中最小关键字结点
    while(bt->lchild != NULL)
        bt=bt->lchild;
    return bt->data;
}
          
int MaxKey(BSTNode *bt){
    //求出二叉排序树中最大关键字结点
    while(bt->rchild != NULL)
    	bt = bt->rchild;
    return bt->data;
}

13. 设计一个算法,从大到小输出二叉排序树中所有值不小于 k 的关键字

/*
由二叉排序树的性质可知，右子树中所有的结点值均大于根结点值，
左子树中所有的结点值均小于根结点值。
为了从大到小输出，先遍历右子树，再访问根结点，后遍历左子树。
*/

void OutPut(BSTNode *bt, int k)
{
    //本算法从大到小输出二叉排序树中所有值不小于k的关键字
    if(bt==NULL)
    	return;
    if(bt->rchild != NULL)
    	OutPut(bt->rchild,k);	//递归输出右子树结点
    if(bt->data >= k)
    	printf("%d",bt->data);	//只输出大于等于k的结点值
    if(bt->lchild !=NULL)
    	OutPut(bt->lchild,k);//递归输出左子树的结点
}