第六章 6-10~6-17
6-10 一棵高度为h的满k叉树有如下性质；第h层上的结点都是叶结点，其余各层上每个结点都有k课非空子树，如果按层次自顶向下，同层自左向右，顺序从1开始对全部结点进行编号，试问：
(1)各层结点个数是多少？
(2)编号为i的结点的父结点(若存在)的编号是多少？
(3)编号为i的结点的第m个孩子结点(若存在)的编号是多少？
(4)编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？

(1)
第0层 1
第1层 k
第2层 k^2
...
第h层 k^h

(2)假设i为第m层元素，那么i层i是第几个 N=i - m层前所有元素个数
而i的父结点在上层的序号位置正好是N/k的上整
那么该父结点的序号是m-1层前所有元素+N/k的上整
上整外取，得到如下公式
上整『(1-k^(m-1))/(1-k)+(i-(1-k^m)/(1-k))/k』
化简得到取上整『(i-1)/k)』


(3)和2相反
(i-1)k+1+m

(4)i结点有右兄弟，条件就是i不是该层子树的最后一个元素。
即(i-1)%k!=0 有兄弟 右兄弟为i+1;

6-11 试用判定树的方法给出在中序线索化二叉树上：
(1) 如何搜索指定结点的在中序下的后继。
(2) 如何搜索指定结点的在前序下的后继。
(3) 如何搜索指定结点的在后序下的后继。

看树的线索化去……
第2小题结果好复杂！！@@

6-12 已知一棵完全二叉树存放于一个一维数组T[n]中，T[n]中存放的是各结点的值。试设计一个算法，从T[0]开始顺序读出各结点的值，建立该二叉树的二叉链表表示.

思路：利用完全二叉树的性质 T[i]应该插入的位置是 下整『(i-1)/2』 (i-1)/2整除则正好是该点的左子女，否则右子女.简化代码，不写类和模板了。

CreatTree(int T[],int n,int i,BinTreeNode *ptr){
  if(i >=n)ptr=NULL;
  else{
    ptr=new BinTreeNode(T[i]);
    ConstructTree(T,n,2*i+1,ptr->leftChild);
    ConstructTree(T,n,2*i+2,ptr->rightChild);
  }
}

程序从CreatTree(t,n,0,root)开始，事先先创建一棵空树.

6-13 试编写一个算法，把一个新结点l作为结点s的左子女插入到一棵线索化二叉树中，s原来的左子女变成l的左子女。
假定是中序线索化二叉树

template< class Type > void ThreadTree< Type >::
InsertRight(ThreadNode< Type > *s,ThreadNode< Type > *l){
  l->leftChild=s->leftChild;
  l->leftThread=s->leftThread;
  l->rightChild=s;L->rightThread=1;
  s->leftChild=l;s->leftThread=0;
  if(l->leftThread==0){
    current=l->leftChild;
    ThreadNode< Type > *temp=Last();
    temp->rightChild=l;
  }
}

发现和右插入简直就是镜像啊

6-15 判断以下序列是否是堆？如果不是，将它调整为堆。
(1) {100,86,48,73,35,39,42,57,66,21}
(2) {12,70,33,65,24,56,48,92,86,33}
(3) {103,97,56,38,66,23,42,12,30,52,06,20}
(4) {05,56,20,23,40,38,29,61,35,76,28,100}

(1)

             100
        86         48
     73    35   39     42
  57  66 21

              100
        86         48
     73    21   39     42
  57  66 35

              100
        86         48
     57    21   39     42
  73  66 35

              100
        86         39
     57    21   48     42
  73  66 35

              100
        21         39
     57    35   48     42
  73  66 86

              21
        35         39
     57    86   48     42
  73  66 100
就做一题了 {21 35 39 57 86 48 42 73 66 100}

6-17 在森林的二叉树表示中，用llink存储指向结点第一个子女的指针，用rlink存储指向结点下一个兄弟的指针，用data存储节点的值。如果我们采用静态二叉链表作为森林的存储表示，同时按森林的先根次序依次安放森林的所有结点，则可以在它们的结点中用只有一个二进位的标志ltag代替llink，用rtag代替rlink。并设定若rtag！=0，则该结点有下一个兄弟。试给出这种表示的结构定义，并设计一个算法，将这种表示存储的森林转换成用llink-rlink表示的森林。

先在草稿纸上画出这样表示的森林和二叉树结构表，理解相互之间的转换方式。

先定义llink-rlink表示的结点定义
template< class Type >class LchRsibNode{
protected:
  Type data;
  int llink,rlink;
public:
  LchRsibNode():llink(-1),rlink(-1){}
  LchRsibNode(Type x):llink(-1),rlink(-1),data(x){}
}  

双标记类节点定义
template< class Type >class DoublyTagNode{
protected:
  Type data;
  int ltag,rtag;
public:
  DoublyTagNode():ltag(0),rtag(0){}
  DoublyTagNode(Type x):ltag(0),rtag(0),data(x){}
}

静态链表类定义
template< class Type >class staticlinkList
  :public LchRsibNode< Type >,pubic DoublyTagNode< Type >{
private:
  LchRsibNode< Type > *V;
  DoublyTagNode< Type > *U;
  int MaxSize,CurrentSize;
public:
  dstaticlinkList(int Maxsz ):MaxSize(Maxsz),CurrentSize(0){
     V=new LchRsibNode< Type >[Maxsz];
     U=new DoublyTagNode< Type >[Maxsz];
}

森林的双标记先根次序表示 向 左子女-右兄弟链表示先根次序表示的转换
void staticlinkList< Type >::DtagF-LchRsibF(){
  Stack< int >st; int k;
  for(int i=0;i< CurrentSize; i++){
    switch(U[i].ltag){
      case 0:switch(U[i].rtag){
         case 0:V[i].llink=V[i].link=-1;
                if(!st.IsEmpty())
                 {k=st.GetTop();
                  st.Pop();
                  V[k].rlink=i+1;
                }break;
         case 1:V[i].link=-1;
                V[i].rlink=i+1;
                break;
         }
      case 1: V[i].llink=i+1;
              if(U[i].rtag==0)                
                V[i].rlink=-1;
              else
                st.Push(i);
              break;
     }
   }
}

感觉用switch结构并不好，不过实在太饿了，懒得改写了。
13:43 | Category: | 0 评论

Comments (0)

发表评论