randompicker.cpp

组播密钥的批次更新算法

#include "StdAfx.h"
#include <stdlib.h>
#include "randompicker.h"


CRandomPicker::CRandomPicker(CBinaryTree& tree):m_tree(tree)
{
}

CRandomPicker::~CRandomPicker(void)
{
}

int CRandomPicker::GetRandomLeafID(void)
{
	CNode* leaf=GetRandomLeaf(m_tree.m_root);
	if(leaf!=0)
		return leaf->m_nodeID;
	return -1;
}

CNode* CRandomPicker::GetRandomLeaf(CNode* subRoot)
{
	if(subRoot!=0)
	{
		if(subRoot->m_leftchild==0 && subRoot->m_rightchild==0)
			return subRoot;
		else
		{
			//对于一颗二叉树的某个节点,如果左右子树同时存在则使用随机函数判断走向
			if(subRoot->m_leftchild!=0 && subRoot->m_rightchild!=0)
			{
				int direction=rand() % 2;
				if(direction==0)
					return GetRandomLeaf(subRoot->m_leftchild);
				else
					return GetRandomLeaf(subRoot->m_rightchild);
			}
			else
			{
				//若该节点只有一侧的子树,则只能走这一侧了
				if(subRoot->m_leftchild!=0)
					return GetRandomLeaf(subRoot->m_leftchild);
				else
					return GetRandomLeaf(subRoot->m_rightchild);
			}
		}
	}
	return 0;
}