ツリーのストレージ構造、およびチェーンテーブルの実現

ツリーのストレージ構造:
      
子供チェーンテーブル:K度のツリーで、1つのノードxにk人の子供がいて、もう1つのノードをxとして挿入する子供は、子供チェーンがいっぱいなので拡張する必要があり、静的配列のみをサポートするプログラム設計言語では、この場合の挿入操作は実現できません.C++言語は動的配列を提供し,子供のノードドメインchildrenを可変長順表に設計すると,挿入操作の拡張機能を実現できる.
多くのストレージ容量を消費する場合があります.ツリーにn個のノードがある場合、度はkであり、総鎖数はn*kであり、n−1個の非空鎖は根を除いたn−1個のノードを指す.空鎖と総鎖の比は以下の通りであり、k=10であれば空鎖が90%を占める.
     
子供兄弟チェーンテーブル:木の子供兄弟チェーンテーブルでは、子供ドメインと兄弟ドメインを区別し、呼び出すことはできません.このストレージ構造は、実際には1つのツリーを1つのツリーストレージに変換します.子供の兄弟の表現によると、1本の木は唯一の二叉木に変えることができる.逆に、1本の二叉木も唯一の木に還元することができます.木の根結点には兄弟がいないため,二叉木の根結点に対応する右子木は空である.
木の兄弟の子供のチェーン時計を実現します:
木の子兄弟チェーン時計

#include 
#include "DoubleNode.h" //      
template 
class Tree //          
{
public:
DoubleNode *root;

Tree ();
~Tree ();
    bool IsEmpty; //      
void DestroyTree (DoubleNode  *p);//     P     
DoubleNode *InsertElem (DoubleNode *p,T x);//   x    p   
friend ostream &operator << (ostream & out ,Tree &List);
//                          
void preRoot (DoubleNode *p,int n);//         P     
};


template 
Tree ::Tree()
{
this->root = NULL；
}
template 
Tree::~Tree()
{
DestroyTree (this ->root);
}
template 
bool Tree ::IsEmpty ()
{
  return root->prior == NULL;
}
template 
void Tree ::DestroyTree(DoubleNode *p)
{
  if(p != NULL)
  {
    DestroyTree(p->prior);
DestroyTree(p->next);
delete p;
  }
}

子供のノードを挿入

template
DoubleNode * Tree::InsertElem(DoubleNode *p, T x)  //   x    p   
{
    DoubleNode *q = NULL;
if(p!=NULL)
{
   q = new DoubleNode(x);  //       q
       if(p->prior == NULL)
   {
      p->prior =q;
   }
   else
   {
      p= p->prior;
  while(p->next!=NULL)
  p=p->next;
  p->next =q;
   }
}
return q;
}

ツリーの遍歴:
ツリーのルートループ:(1)ルートノードへのアクセス(2)ルートの各ツリーを左から右の順にルートします.
ツリーのバックグラウンドパス:(1)左から右の順にバックグラウンドパスルートの1本ずつのツリーにアクセス(2)ルートノードにアクセス

template 
ostream& operator<< (ostream& out,Tree&List)  //                        
{
   List.preRoot(List.root,0);
   return out;
}

template 
void Tree::preRoot(DoubleNode *p, int n)  //       P     ，  i       
{
  if(p!=NULL)
  {
     for(int j=0;jdata<prior,n+1);
 preRoot(p->next,n);
  }
}

雲南都市樹の印刷

#define _CRT_SECURE_NO_WARNINGS
#include "Tree.h"
void Creat(Tree &tree)  //     
{
  tree.root =new DoubleNode("  ");
  DoubleNode *km =tree.InsertElem(tree.root,"   ");
  tree.InsertElem (km,"   ");
  DoubleNode *qj = tree.InsertElem(tree.root,"   ");
  tree.InsertElem (qj,"   ");
  tree.InsertElem(tree.root,"   ");
  tree.InsertElem(tree.root,"   ");
}

int main()
{
   Treetree;
   Creat(tree);
   cout<

前へ次へ
»戻る