内通路长度

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++;
}