「データ構造高得点ノート」ツリーとフォークツリー

記事の目次

二叉樹の再帰遍歴(前中後)

ツリー型の表現式

を計算します.

ツリーの深さを求める

は、ある結点が木の中にあるかどうかを確認する

.

において、K番目のノード値

が順次巡回出力される.

段階巡回

プリアンブル非再帰的実現

におけるシーケンス非再帰的実現

二叉の木の再帰遍歴(前中後)

typedef struct BTNode{
     char data;
     struct BTNode *lchild, *rchild;
}BTNode;

//previous order
void preorder(BTNode *p){
     if(p == NULL) return ;
     visit(p);
     preorder(p->lchild);
     preorder(p->rchild);
}

//in order
void inorder(BTNode *p){
     if(p == NULL) return;
     inorder(p->lchild);
     visit(p);
     inorder(p->rchild);
}

//post order
void postorder(BTNode *p){
     if(p == NULL) return;
     postorder(p->lchild);
     postorder(p->rchild);
     visit(p);
}

ツリー型の表式を計算します.
ツリー型表現の特徴は、操作数はすべて葉の結点にあり、操作子はみな分岐点にあります.したがって、一つのノードの左右の子供が全部空の時に再帰を終了し、この時点でこの結点の操作数を返します.後の順序に似ています.

using namespace std;

const int maxn = 100;

typedef struct BTNode{
     char data;
     struct BTNode *lchild, *rchild;
}BTNode;
BTNode tree[maxn];
//        ，          ，        
int op(int a, int b, char c){
     if(c == '+') return a + b;
     if(c == '-') return a - b;
     if(c == '*') return a * b;
     if(c == '/' && b != 0) return a / b;
     else return 0;
}

//         ，        ，    
int comp(BTNode *root){
     //          ，            ，           
     if(root->lchild == NULL && root->rchild == NULL) return  root->data - '0';
     int left = comp(root->lchild);
     int right = comp(root->rchild);
     return op(left, right, root->data);
}

//        ，        
BTNode* create(int n){
     queue<BTNode*> Q;
     BTNode *root = NULL, *top;
     char c;
     for(int i = 1; i <= n; i ++){
          //    
          scanf("%c", &c);
          BTNode *p = NULL;
          //       -，       ，    
          if(c != ' '){
               p = (BTNode*)malloc(sizeof(BTNode));
               p->data = c, p->lchild = NULL, p->rchild = NULL;
               Q.push(p);
               top = Q.front();//         ，          
               if(i == 1) root = p;//      ，        
               else if(i % 2 == 0) top->lchild = p;//           ，      
               else if(i % 2 == 1) top->rchild = p;
          }
          if(i % 2 == 1 && i != 1) Q.pop();//       

     }
     return root;
}

int main()
{
     int n;
     scanf("%d", &n);
     getchar();
     BTNode *root = create(n);
     int ans = comp(root);
     printf("%d
", ans);
     return 0;
}

木の深さを求める
帯戻り値の再帰的実現を用いて、左サブツリーと右サブツリーの深さをそれぞれ求め、両者の最大値＋1を返し、現在のノードの深さとします.再帰的終了の条件は、葉の結点の次の層に訪問することである.

int getDepth(BTNode *root){
     if(root == NULL) return 0;//           ，   
     int left = getDepth(root->lchild);
     int right = getDepth(root->rchild);
     return (left > right ? left : right) + 1;//            
}

ある結点が木にあるかどうかを確認します.
先に巡回した方法で検索します.現在の結点値が目標値に等しいかどうかを先に判断します.等しいなら、見つけ、終了します.さもなくば左の子樹に行って探して、必要でない循環を減らすため、左の子樹は探し当てていない時やっと右の子樹に行って検索します(つまり適当に枝を切ります);

//               
void Search(BTNode *root, BTNode *&q, char k){
     if(root == NULL) return;
     if(root->data == k) q = root;
     else{
          Search(root->lchild);
          if(q == NULL) Search(root->rchild);//  ，                      
     }
}

中で順番にK番目の結点値を出力します.
実際には、結点を探すなら、最初の順序で遍歴したほうがいいです.中順と後序は2回目か3回目の結点を通過した時に目標値であるかどうかを判断します.効率は高くないです.本題に戻ります.もし中間が巡回したら、判断文を中間に置くだけでいいです.しかし、枝を切ってはいけません.きっと右の木を遍歴している時に目標値を見つけます.

void trave(BTNode *root, int k){
     if(root == NULL) return;
     trave(root->lchild, k);
     n ++;
     if(n == k) {
          printf("%c", root->data);
          return ;
     }
     //        ，           ，            ，                 
     //              
     trave(root->rchild, k);
}

巡回
循環隊列によって実現され、毎回チームの先頭要素を取り出して出力する.もしチームの一番の要素が子供を左右すると入隊します.列が空になるまで繰り返します.

void level(BTNode * root){
     if(root == NULL) return;
     //initialize queue 
     int rear = 0, front = 0;//  ，    ，                 ，            
     BTNode *queue[maxn], *top = NULL;
     //push root into queue 
     rear = (rear + 1) % maxn;
     queue[rear] = root; 
     //undo until queue is empty
     while(rear != front){
          //pop up front elem
          front = (top + 1) % maxn;
          top = queue[front];
          cout << top->data;
          //push left child when left child is not empty 
          if(top->lchild) {
               rear = (rear + 1) % maxn;
               queue[rear] = top->lchild;
          }
          //push right child when right child is not empty 
          if(top->rchild) {
               rear = (rear + 1) % maxn;
               queue[rear] = top->rchild;
          }
     }
     
}

最初の順序は再帰的ではない.
まずルートノードをスタックに入れて、循環のたびにスタックトップ要素をイジェクトして、この要素を巡回することを表すスタックをシミュレーションする.次に、右のサブツリーが空かどうかを確認します.空でなければ、スタックに入ります.左のサブツリーが空かどうか確認してください.空でなければ、スタックに入れます.(スタックの先进的な后出のため、右サブツリーの要素は先にスタックに入る);

void preorderNonrecursion(BTNode *root){
     if(root == NULL) return;
     //initialize stack
     BTNode *stack[maxn];
     BTNode *p = NULL;
     int top = -1;
     //push root into stack
     stack[++top] = root;
     while(top != -1){
          p = stack[top--];//every loop must have elem is popped,but push elem when it has child
          Visit(p);
          //first push right child , then push left child
          if(p->rchild) stack[top++] = p->rchild;
          if(p->lchild) stack[top++] = p->lchild;
     }
}

中順非再帰的実現
核心はいつスタックを出るかをはっきりさせることです.左の木が空いている時にのみスタックが出ます.その後、スタックトップノードにアクセスして、右サブツリーのルートノードをスタックに押し込む.

void inorderNonrecusion(BTNode *root){
     if(root == NULL) return;
     BTNode *stack[maxn];
     int top = -1;
     BTNode *p = root;
     //       ，             
     while(top != -1 || p != NULL){
          //         ，            ，        
          while(p != NULL){
               stack[++top] = p;
               p = p->lchild;
          }
          //                   ，                
          if(top != -1){
               p = stack[top--];
               Visit(p);
               p = p->rchild;//               ，       
          }
     }
}