首页 C&C++ 数据结构与算法分析

# 证明在 N 个节点的二叉树中，存在 N+1 个 NULL 指针代表 N+1 个儿子

证明：假设有 N 个节点，则指针 point 有 2N 个，非 NULL 指针为 N-1 个，则 NULL 指针为2N−(N−1)=N+12N-(N-1)=N+1 个，所以存 N+1 个 NULL 指针未来可代表 N+1 个儿子。

# 证明在高度为 H 的二叉树中，节点的最大个数是2H+1−12^{H+1}-1

证明：假设这是一颗完全二叉树，则有最大节点，其中高度为 H 时，层数为 H+1。
则第一层，节点数N=20N = 2^0, 第二层，节点数N=21N = 2^1, 第三层，节点数N=22N = 2^2, 以此类推得每层节点数N=2HN = 2^H。
由等比数列前 N 项和Sn=a11−qn1−qS_n=a_1\frac{1-q^n}{1-q}, 其中a1=1a_1=1,n=H+1n=H+1。所以节点的最大个数为2H+1−12^{H+1}-1。

# 满节点 (full node) 是具有两个儿子的节点。证明满节点的个数加 1 等于非空二又树的树叶的个数

证明：假设有一颗完全二叉树，高度为 H, 则每层节点数N=2HN = 2^H, 二叉树全部节点数M=2(H+1)−1M=2^{(H+1)-1}。
则满节点个数等于二叉树全部节点数减去叶子节点数，即n=2(H+1)−1−2H=2H−1n=2^{(H+1)-1} - 2^H = 2^H-1, 而叶子节点数m=2Hm =2^H, 满足m=n+1m = n+1 所以满节点的个数加 1 等于非空二又树的树叶的个数。

# 设二叉树有树叶ι1,ι2,....ιM\iota_1,\iota_2,....\iota_M, 各树叶的深度分别为d1,d2,...,dMd_1,d_2,...,d_M。证明∑i=1M2−di≤1{\textstyle \sum_{i=1}^{M}2^{-d_i}} \le 1 并确定何时等号成立

证明：假设只有一个节点的树，树叶深度did_i 为 0, 则∑i=1M2−di=1{\textstyle \sum_{i=1}^{M}2^{-d_i}} =1。
假设有一颗完全二叉树，则左右子树各树叶深度did_i 为12H\frac{1}{2^H}, 则左右子树树叶深度之和为12\frac{1}{2}, 恰好∑i=1M2−di=1{\textstyle \sum_{i=1}^{M}2^{-d_i}} = 1。
对于非完全二叉树，左右子树树叶深度之和始终小于12\frac{1}{2}, 有∑i=1M2−di<1{\textstyle \sum_{i=1}^{M}2^{-d_i}} < 1。所以二叉树始终有∑i=1M2−di≤1{\textstyle \sum_{i=1}^{M}2^{-d_i}} \le 1, 且当二叉树为完全二叉树或只有一个节点时等号生效。

# 写出实现基本二叉查找树操作的例程

应该不会有人写不出来吧。

typedef int ElementType;
typedef struct _treeNode TreeNode;
typedef  TreeNode* SearchTree;
typedef SearchTree* SearchTreeAddress;
typedef  TreeNode* Position;
struct _treeNode{
    ElementType data;
    SearchTree left;
    SearchTree right;
};
// init binarySearchTree and create a empty tree
SearchTree MakeEmpty(SearchTree T)
{
    if(T!= NULL)
    {
        MakeEmpty(T->left);
        MakeEmpty(T->right);
        free(T);
    }
    return NULL;
}
// find element in the tree and return position
Position Find(SearchTree T, ElementType element)
{
    if(T==NULL)//when the point is null
      return NULL;
    else if(element<T->data)//if the element less than the data,go left
      return Find(T->left, element);
    else if(element>T->data)//if the element more than the data,go right
      return Find(T->right, element);
    else//if find the element
      return T;
}
// find the minimum element in the tree and return position
Position FindMin(SearchTree T)
{
    if(T==NULL)//when the point is null
      return NULL;
    else if(T->left==NULL)//if find the minimum element
       return T;
    else //if not find the minimum element,go left
      return FindMin(T->left);
}
// find the maximun element in the tree and return position
Position FindMax(SearchTree T)
{
    if(T==NULL)//when the point is null
      return NULL;
    while(T->right!=NULL)
    {
        T = T->right;//if not find the maximun element,go right
    }
    return T;
}
// insert element at the tree 
SearchTree Insert(SearchTree T,ElementType element)
{
    if(T==NULL)//when the point is null
    {
        // create a tree node for the tree
        T = malloc(sizeof(TreeNode));
        (T)->data = element;
        (T)->left = (T)->right = NULL;
    }
    else if((T)->data>element)//if the element less than the data,go left insert the element
      (T)->left = Insert((T)->left,element);
    else if((T)->data<element)//if the element is greater than the data,go right insert the element
      (T)->right = Insert((T)->right,element);
    return T;//insert completed successfully
}
// find the element at the tree and delete it(replace it with a right subtree minimum)
SearchTree DeleteRight(SearchTree T,ElementType element)
{
    Position temp = NULL;
    if(T==NULL)//when the point is null
      return NULL;
    else if(element<T->data)//go left
      T->left =  DeleteRight(T->left, element);
    else if(element>T->data)//go Right
      T->right =  DeleteRight(T->right, element);
    else if(T->right&&T->left)//have two children
    {
        temp = FindMin(T->right);
        T->data = temp->data;
        T->right =  DeleteRight(T->right,temp->data);
    }
    else //have one or zero children
    {
        temp = T;
        if(T->left==NULL) T = T->right;
        else if(T->right==NULL) T = T->left;
        free(temp);
    }
    return T;
}
# 使用类似于游标链表实现法的策硌，可以用游标实现二叉查找树。使用指针实现方法写出基本的二叉查找树例程。
除了重写 malloc () 和 free () 函数，其余操作其实和用指针操作二叉树没什么区别。
// init tree table example
/*
slot   Element    left    right
0                   1       0
1                   2       0
2                   3       0
3                   4       0
4                   5       0
5                   6       0
6                   7       0
7                   8       0
8                   9       0
9                   0       0
*/
#define SpaceSize 100
#define NONE 0
typedef int ElementType;
typedef int ptrNode;
typedef ptrNode Position;
typedef ptrNode SearchTree;
struct _treeNode {
    ElementType data;
    SearchTree left;
    SearchTree right;
};
struct _treeNode CursorSpace[SpaceSize];
//malloc 函数
static Position CursorAlloc()
{
    Position P;
    P = CursorSpace[0].left;
    CursorSpace[0].left = CursorSpace[P].left;
    return P;
}
//free 函数
static void CursorFree(Position P)
{
    CursorSpace[P].left = CursorSpace[0].left;
    CursorSpace[0].left = P;
}
// 初始化 Cursor 数组
void InitCursor()
{
    for (int i = 0; i < SpaceSize; i++)
    {
        CursorSpace[i].left = (i == SpaceSize - 1 ? 0 : i + 1);
        CursorSpace[i].right = 0;
    }
}
// init binarySearchTree
SearchTree MakeEmpty(SearchTree T)
{
    if(T!=NONE)
    {
        CursorSpace[T].left = MakeEmpty(CursorSpace[T].left);
        CursorSpace[T].right = MakeEmpty(CursorSpace[T].right);
        CursorFree(T);
    }
    return NONE;
}
// find the element from the binary search tree
Position Find(SearchTree T, ElementType element)
{
    if(T==NONE)
       return NONE;
    else if(element<CursorSpace[T].data)//if the element less than the data,go left
       return Find(CursorSpace[T].left,element);
    else if(element>CursorSpace[T].data)//if the element greater then the data,go right
       return Find(CursorSpace[T].right,element);
    return T;
}
// insert element at the binary search tree
SearchTree Insert(SearchTree T, ElementType element)
{
    if(T==NONE)
    {
        T = CursorAlloc();
        CursorSpace[T].data = element;
        CursorSpace[T].left = CursorSpace[T].right = NONE;
    }
    else if(element<CursorSpace[T].data)//if the element less than the data,go left
        CursorSpace[T].left = Insert(CursorSpace[T].left,element);
    else if(element>CursorSpace[T].data)//if the element greater then the data,go right
        CursorSpace[T].right = Insert(CursorSpace[T].right,element);
    return T;
}
Position FindMin(SearchTree T)
{
    if(T==NONE)
      return NONE;
    else if(CursorSpace[T].left==NONE)
      return T;
    else 
      return FindMin(CursorSpace[T].left);
}
Position FindMax(SearchTree T)
{
    if(T==NONE)
      return NONE;
    else if(CursorSpace[T].right==NONE)
      return T;
    else 
      return FindMax(CursorSpace[T].right);
}
SearchTree Delete(SearchTree T,ElementType element)
{
    Position temp = NONE;
    if(T==NONE)
      return NONE;
    else if(element<CursorSpace[T].data)//go left
      CursorSpace[T].left = Delete(CursorSpace[T].left,element);
    else if(element>CursorSpace[T].data)//go right
      CursorSpace[T].right = Delete(CursorSpace[T].right,element);
    else if(CursorSpace[T].left&&CursorSpace[T].right)//have two children
    {
        temp = FindMin(CursorSpace[T].right);
        CursorSpace[T].data = CursorSpace[temp].data;
        CursorSpace[T].right = Delete(CursorSpace[T].right,CursorSpace[temp].data);
    }
    else //have one or zero children
    {
        temp = T;
        if(CursorSpace[T].left==NONE)
          T = CursorSpace[T].right;
        else if(CursorSpace[T].right==NONE)
          T = CursorSpace[T].left;
        CursorFree(temp);
    }
    return T;
}
# 设欲做一个实验来验证由随机 Insert/Delete 操作对可能引起的问题。这里有一个策略，它不是完全随机的，但却是足够封闭的。通过插入从 1 到M=αNM=αN 之间随机选出的 N 个元素来建立一棵具有 N 个元素的树。然后执行N2N^2 对先插入后删除的操作。假设存在例程 RandomInteger（A,B）, 它返回一个在 A 和 B 之间（包括 A，B）的均匀随机整数
# a. 解释如何生成在 1 和 M 之间的一个随机整数，该整数不在这棵树上（从而随机插入可以进行）。用 N 和α\alpha 来表示这个操作的运行时间。
假设已经有 N 项元素插入树中，则 M-N 次后可能得到非二叉树上的数字。
则概率P=M−NM=αN−NαN=α−1αP = \frac{M-N}{M} = \frac{αN-N}{αN} = \frac{α-1}{α}, 则运行时间为O(αα−1)O(\frac{α}{α-1})。
# b. 解释如何生成在 1 和 M 之间的一个随机整数，该整数已经存在与这棵树上，（从而删除可以随机进行）。这个操作的运行时间是多少？
和 a 题类似。已知得到非二叉树上元素的概率P=α−1αP=\frac{α-1}{α}, 所以设 X 为得到二叉树上元素的概率。则P+X=1P+X=1, 解得X=1αX=\frac{1}{α}, 所以运行时间为O(α)O(α)。
# c. α 的最佳选择值是多少？为什么？
实际程序运行时间为O(α+αα−1)O(α+\frac{α}{α-1})。令f(a)=aa−1+af(a)=\frac{a}{a-1}+a。
化简得f(a)=1a−1+a+1f(a)=\frac{1}{a-1}+a+1, 有洛必达法则得f′(a)=1−1(a−1)2f{}' (a)=1-\frac{1}{(a-1)^2}
令f′(a)=0f{}' (a)=0, 得a(a−2)=0a(a-2)=0,a 为 0 不符合实际情况，所以选择a=2a=2。
# 编写一个程序，凭经验估计删除具有两个子节点的下列各方法：
# a. 用TLT_L 中最大节点 X 来代替，递归地删除 X。
其实就是用左子树得最大值替换删除得节点，书中得删除操作用的是右子树得最小节点。
// find the element at the tree and delete it(replace it with a left subtree maximun)
SearchTree DeleteLeft(SearchTree T,ElementType element)
{
  Position temp =  NULL;
  if(T==NULL)
    return NULL;
  else if(element<T->data)
    T->left = DeleteLeft(T->left, element);
  else if(element>T->data)
    T->right = DeleteLeft(T->right, element);
  else if(T->left&&T->right)//have two children
  {
    temp = FindMax(T->left);
    T->data = temp->data;
    T->left = DeleteLeft(T->left, temp->data);
  }
  else //have one or zero children
  {
    temp = T;
    if(T->left==NULL) T = T->right;
    else if(T->right==NULL) T = T->left;
    free(temp);
  }
  return T;
}
# b. 交替地用TLT_L 中最大节点以及 TR 中最小的节点来代替，并递归地删除适当的节点。
这里我直接使用个静态布尔值交替使用 DeleteLeft () 和 DeleteRight () 函数进行删除。
// alternately use DeleteLeft() and DeleteRight() to delete element
void AlternateDelete(SearchTree T, ElementType element)
{
  static bool flag = true;
  if(flag) DeleteLeft(T, element);
  else DeleteRight(T, element);
  flag = !flag;
}
# 随机地选用TLT_L 中最大的节点或TRT_R 中最小的节点来代替（递归地删除适当的节点）。哪种方法给出最好的平衡？哪种在处理整个操作序列过程中花费最少的 CPU 时间？
万恶得硬件生成随机数，所以 C 是最耗 CPU 时间得，A、B 则较少，但平衡性最好得可能是 C,A 和 B 不太好达到理想平衡。
// hardware delay generation the random number
bool Rand()
{
  srand((unsigned)time(NULL));
  Sleep(1000);//delay 1S
  return rand() % 2;//scope is 0~1
}
// random use DeleteLeft() and DeleteRight() to delete element
void RandomDelete(SearchTree T, ElementType element)
{
  static bool flag = true;
  flag = Rand();
  printf("%d\n",flag);
  if(flag==true) DeleteLeft(T, element);
  else DeleteRight(T, element);
}
# 给出高度为 H 的 AVL 树中节点得最少个数得精确表达式
已知S(0)=1S(0)=1,S(1)=2S(1)=2, 有归纳法得S(H)=S(H−1)+S(H−2)+1S(H)=S(H-1)+S(H-2)+1。
# 写出实现 AVL 单旋转和双旋转的其余的过程
// roate the type of the LL
/*
       K2                K1
     /   \     LL       /  \   
    K1    Z    -->    x1    k2
   /  \              /     / \
  x1    Y           X2    Y   Z
 /
X2
*/
static Position SingleRoateLeft(Position K2)
{
    Position K1;
    K1 = K2->left;
    K2->left = K1->right;
    K1->right = K2;
    K2->height = MAX(Height(K2->left),Height(K2->right))+1;
    K1->height = MAX(Height(K1->left),K2->height)+1;
    return K1;
}
// roate the type of the RR
/*
       K1                       k2     
      /  \                     /  \
     X    k2      RR          K1   Z1
         /  \     -->        /  \    \
        Y   Z1              X    Y    Z2
             \  
              Z2  
*/
static Position SingleRoateRight(Position K1)
{
  Position K2;
  K2 = K1->right;
  K1->right = K2->left;
  K2->left = K1;
  // update node height
  K1->height = MAX(Height(K1->left),Height(K1->right))+1;
  K2->height = MAX(Height(K2->right),K1->height)+1;
  return K2;
}
// roate the type of the LR
/*
      K3                      K3                            K2
     /  \                    /  \                          /  \
    K1   D      RR          K2   D            LL          K1   K3
   /  \         -->        /  \               -->        / \   / \
  A    K2                 K1   C                        A   B C   D
      /  \               /  \                         
     B    C             A    B
*/
static Position DoubleRoateLeft(Position K3)
{
  K3->left = SingleRoateRight(K3->left);
  return SingleRoateLeft(K3); 
}
// roate the type of the RL
/*
        k1                           k1                         k2
       /  \                         /  \                       /  \
      A    K3        LL            A    K2         RR         K1   K3
          /  \       -->               /  \        -->       /  \  / \
         K2   D                       B    K3               A    B C  D   
        / \                               /  \
       B   C                             C    D 
*/
static Position DoubleRoateRight(Position K1)
{
  K1->right = SingleRoateLeft(K1->right);
  return SingleRoateRight(K1);
}
# 写出向 AVL 树进行插人的非递归函数。
不用递归，那就要自己手动用栈模拟递归了。
// Insert element in the AvlTree with no recursion
AvlTree AvlInsertNoRecursion(AvlTree T, AvlElementType element)
{
  Stack S = CreatStack(10);
  while(true)
  {
    // find the suitable position with the element
    // need a stack to record the path to the element
    if(T==NULL)
    {
      T = malloc(sizeof(AvlNode));
      T->height = 0;
      T->data = element;
      T->left = T->right = NULL;
      Push(S, T);
      break;
    }
    else if(element<T->data)//element less than node data,go left and push it
    {
      Push(S, T);
      T = T->left;
    }
    else if(element>T->data)//more than node data,go right and push it
    {
      Push(S, T);
      T = T->right;
    }
  }
  AvlTree Parent = NULL;
  while(!IsEmpty(S))
  {
    Parent = TopAndPop(S);
    if(T->data<Parent->data)
    {
      Parent->left = T;//element link to parent
      if(Height(Parent->left)-Height(Parent->right)==2)
      {
        if(element<Parent->left->data)
          Parent = SingleRoateLeft(Parent);//LL
        else
          Parent = DoubleRoateLeft(Parent);//LR
      }
    }
    else if(T->data>Parent->data)
    {
      Parent->right = T;//element link to parent
      if(Height(Parent->right)-Height(Parent->left)==2)
      {
        if(element>Parent->right->data)
          Parent = SingleRoateRight(Parent);//RR
        else
          Parent = DoubleRoateRight(Parent);//RL
      }
    }
    T = Parent;
    // update the parent height
    T->height = MAX(Height(T->left),Height(T->right))+1;
  }
  //update the parent height when you not use to roate
  //In fact,I did extra work,because Parent node height is repeatly calculated
  T->height = MAX(Height(T->left),Height(T->right))+1;
  return T;
}
# 如何能够在 AVL 树中实现（非懒惰）删除？
删除操作和普通二叉查找树差不多，只不过当删除某个元素时要检查 AVL 树是否失衡并更新高度信息。
此时有三种大情况：
  • 当你删除右子树中的节点时，返回根节点，有两种情况：
  1. 会出现 LR 的不平衡型
  2. 会出现 LL 的不平衡型
  • 当你删除左子树中的节点时，返回根节点，有两种情况：
  1. 会出现 RL 的不平衡型
  2. 会出现 RR 的不平衡型
  • 如果左子树的高度大于右子树的高度，找到左子树的最大值并将数据写入 T 节点，然后删除左子树的最大值；如果左子树的高度大于右子树的高度，找到左子树的最大值并将数据写入 T 节点，然后删除左子树的最大值
AvlTree AvlDelete(AvlTree T, AvlElementType element)
{
  Position temp = NULL;
  if(T==NULL)//when the point is null
    return NULL;
  else if(element<T->data)//go left
  {
    T->left = AvlDelete(T->left,element);
    // the statment is to deal with a parent node that has only one child node
    T->height = MAX(Height(T->left),Height(T->right))+1;
    // when you delete the node in the left subtree,return the root node
    // There are two situations:
    // 1. it will occur the unbalanced type of RL
    // 2. it will occur the unbalanced type of RR
    if(Height(T->right)-Height(T->left)==2)
    {
      if(Height(T->right->left)>Height(T->right->right))
        T = DoubleRoateRight(T);//RL
      else
        T = SingleRoateRight(T);//RR
    }
  }
  else if(element>T->data)//go right
  {
    T->right = AvlDelete(T->right,element);
    // the statment is to deal with a parent node that has only one child node
    T->height = MAX(Height(T->left),Height(T->right))+1;
    // when you delete the node in the right subtree,return the root node
    // There are two situations:
    // 1. it will occur the unbalanced type of LR
    // 2. it will occur the unbalanced type of LL
    if(Height(T->left)-Height(T->right)==2)
    {
      if(Height(T->left->right)>Height(T->left->left))
        T = DoubleRoateLeft(T);//LR
      else
        T = SingleRoateLeft(T);//LL
    }
  }
  else if(T->left&&T->right)//have two children
  {
    //if the height of left subtree more than the height of right subtree
    //find the maximun of the left subtree and write the data to T Node
    //then delete the maximun of the left subtree
    //otherwise use the opposite method
    if(Height(T->left)>Height(T->right))
    {
      temp = AvlFindMax(T->left);
      T->data = temp->data;
      T->left = AvlDelete(T->left,temp->data);
    }
    else
    {
      temp = AvlFindMin(T->right);
      T->data = temp->data;
      T->right = AvlDelete(T->right,temp->data);
    }
  }
  else//have one or zero children
  {
    temp = T;
    if(T->left==NULL) T = T->right;
    else if(T->right==NULL) T = T->left;
    free(temp);
  }
  //when the point is not NULL,update the height of the node
  if(T!= NULL)
    T->height = MAX(Height(T->left),Height(T->right))+1;
  return T;
}
# 为了存储一棵 N 节点的 AVL 树中一个节点的高度，每个节点需要多少比特（bit）？
令2n=log⁡2N−12^n=\log_{2}{N} -1, 两边取对数得
n=log⁡2log⁡2N−log⁡22n=\log_{2}{\log_{2}{N} -\log_{2}{2}}, 求得n=log⁡2log⁡2Nn=\log_{2}{\log_{2}{N}}。
# 写出执行双旋转的函数，其效率要超过执行两个单旋转。
//Here is another version of the double roation functions,
// it is said to be far more efficient than two single roation functions
// note: I have not tested either of these functions
// because i don't want to rewrite AvlDelete function,although it is not difficult\
// roate the type of the LR
/*
      K3                              K2
     /  \                            /  \
    K1   D      LR                  K1   K3
   /  \         -->                / \   / \
  A    K2                         A   B C   D
      /  \                                       
     B    C          
*/
static Position AnotherDoubleRoateLeft(Position K3)
{
  Position K1,K2;
  K1 = K3->left;
  K2 = K1->right;
  K1->right = K2->left;
  K3->left = K2->right;
  K2->left = K1;
  K2->right = K3;
  
  K1->height = MAX(Height(K1->left),Height(K1->right))+1;
  K3->height = MAX(Height(K3->left),Height(K3->right))+1;
  K2->height = MAX(Height(K2->left),Height(K2->right))+1;
  return K2;
}
// roate the type of the RL
/*
        k1                       k2
       /  \                     /  \
      A    K3        RL        K1   K3
          /  \       -->      /  \  / \
         K2   D              A    B C  D   
        / \                    
       B   C               
*/
static Position AnotherDoubleRoateRight(Position K1)
{
  Position K2,K3;
  K3 = K1->left;
  K2 = K3->left;
  K1->right = K2->left;
  K3->left = K2->right;
  K2->left = K1;
  K2->right = K3;
  K1->height = MAX(Height(K1->left),Height(K1->right))+1;
  K3->height = MAX(Height(K3->left),Height(K3->right))+1;
  K2->height = MAX(Height(K2->left),Height(K2->right))+1;
  return K2;
}
# 编写一些高效率的函数，只使用指向二叉树的根的一个指针 T，并计算：
a. T 中节点的个数
//Calculate the number of nodes
int CountNodes(BinaryTree T)
{
  if(T==NULL) return 0;
  return 1 + CountNodes(T->left) + CountNodes(T->right);
}
b. T 中树叶的片数
//Calculate the number of leaf nodes
int CountLeaves(BinaryTree T)
{
  if(T==NULL)
    return 0;
  else if(T->left==NULL&&T->right==NULL)
    return 1;
  
  return CountLeaves(T->left) + CountLeaves(T->right);
}
c. T 中满节点的个数
//Calculate the number of full nodes 
int CountFull(BinaryTree T)
{
  if(T==NULL) 
    return 0;
  return (T->left!=NULL&&T->right!=NULL)+
           CountFull(T->left) + CountFull(T->right); 
}
# 写出成一棵 N 节点随机二叉查找树的函数，该树具有从 1 直到 N 得不同关键字，你所编写得程序的运行时间是多少？
BinaryTree MakeBinaryRandomTree1(int lower,int upper)
{
  BinaryTree T;
  int RandomValue;
  T = NULL;
  if(lower<=upper)
  {
    T = malloc(sizeof(TreeNode));      
    if(T!= NULL)
    {
      T->data = RandomValue = RandInt(lower, upper);
      T->left =  MakeBinaryRandomTree1(lower, RandomValue-1);
      T->right = MakeBinaryRandomTree1(RandomValue+1, upper);
    }
  }
  return T;
}
BinaryTree MakeBinaryRandomTree(int N)
{
  return MakeBinaryRandomTree1(1, N);
}
运行时间为 O (N)。