內部路徑長度

Question

我有我需要的幫助一個問題：

寫一個程序計算擴展二叉樹的內部路徑長度。用它來根據經驗調查在隨機生成的二叉搜索樹中搜索的關鍵比較的平均數量。

編輯：

所以我想出了一個C++類二叉樹

#include <iostream> 

/*Binary tree class based on the struct. Includes basic functions insert, delete, search */ 

struct node 
{ 
    int data; 
    node *left; 
    node *right; 
}; 

class binarytree{ 
public: 
    binarytree(); 
    ~binarytree(); 

    void insert(int key); 
    node *search(int key); 
    void destroy_tree(); 

private: 
    void destroy_tree(node *leaf); 
    void insert(int key, node *leaf); 
    node *search(int key, node *leaf); 

    node *root; 

}; 

binarytree::binarytree(){ 
    root = NULL; 
} 

binarytree::~binarytree(){ 
    destroy_tree(); 
} 

void binarytree::destroy_tree(node *leaf) 
{ 
    if(leaf!=NULL) 
    { 
      destroy_tree(leaf->left); 
      destroy_tree(leaf->right); 
      delete leaf; 
    } 
} 

void binarytree::insert(int key, node *leaf){ 
    if(key < leaf->data){ 
      if(leaf->left!=NULL) 
       insert(key, leaf->left); 
      else{ 
       leaf->left = new node; 
       leaf->left->data=key; 
       leaf->left->left=NULL; 
       leaf->left->right=NULL; 
      } 
    } 
    else if(key>=leaf->data){ 
      if(leaf->right!= NULL) 
       insert(key, leaf->right); 
      else{ 
       leaf->right = new node; 
       leaf->right->data=key; 
       leaf->right->left=NULL; 
       leaf->right->right=NULL; 
      } 
    } 
} 

node *binarytree::search(int key, node *leaf){ 
    if(leaf!=NULL){ 
      if(key==leaf->data) 
       return leaf; 
      if(key<leaf->data) 
       return search(key, leaf->left); 
      else 
       return search(key, leaf->right); 
    } 
    else return NULL; 
} 

我剛纔的問題是，我需要在實施幫助。現在，如果我的二叉樹實現是正確的（如果沒有，請隨時告訴我），有人能幫我找到計算擴展二叉樹內部路徑長度的算法嗎？我認爲我的實現應該覆蓋擴展的二叉樹，但我不知道如何找到內部路徑長度。我已經看遍了整個互聯網，但似乎沒有人能夠解釋它或有一個算法來找到它。

再次感謝您的幫助！對此，我真的非常感激！

Answer 1

語言：C/C++：

像創建一個結構：

int count = 0;    //treat count,count1, count2 as global variable 
int count1 = 0;   // so define these outside main() 
int count2 = 0; 
int count3 = 0; 
struct node{ 
int data;     //data or value at that particular node 
struct node* left;   //left pointer 
struct node* right; 
}Node;      //Node is a type of node 

Node node1 = (Node)((malloc) sizeof(Node)) 
    //to create a space in memory (if available) and 99.99% times it's available 

現在，你可以使用任何你想要的功能。 如果你想找到長度一樣：

int findLength(Node* head){ 

node* temp = head;    //initialize temp to head to use it further 

    if(temp->left != NULL || temp->right!=NULL){ 
    count1 += findLength(temp->left); 
    count2 += findLength(temp->right); 
    //next line: if(count1>count2, make count3=count1 , else count3=count2) 

    count3 = (count1>count2)? count1 : count2; 
    count += count3;      //add count3 to previous value of count 
    return count+1; 
    } 

    if(temp->left == NULL && temp->right == NULL){ 
    return 1; 
    } 

    else if(head == NULL) 
     return 0; 
    return count++; 
}