如何实现这样的树!!!欢迎来讨论

Question

这两天碰到无数问题,大家一块来看看:
问题3:
要求
1. 创建一个丰满树,  只有一个数据,一个int 变量
2. 树的节点的值是从左到右,从小变大,顺序排列.
3. 创建一个窗口(win32,MFC,OpenGL,D3D都可),在窗口里显示这个丰满树,每个节点都用方框显示,方框中心显示变量,而节点和节点之间用线连着..(注意,任何节点之间不得有重叠现象,否则算零分)
而且窗体的pageSize要随着丰满树的变化而变,简单的说是让你给窗体加入V,Hscroll,显示整个丰满树.反正用户一定要看到整个丰满树.
4. 当用户想输入节点时,弹出一输入对话框.5. 总的意思是
6. 用对话框输入新节点,窗体以图形的方式显示整个丰满树就可. 

Answer 1

这几天刚好做了一个类似这样的东西。我讲讲我的思路吧
定义一个树类：每个节点除了有你说的整数之外，还有一个矩形框。用CScrollView类，每次生成树之后 调用一个子程序，这个子程序是设置CScrollView的宽度和深度的。
这个子程序的基本思想是：
1.用后序遍历算出树的深度，然后按  2 的（深度-1） 次方算出完全树的子结点的数目，然后再按你的子结点的数目＊（每个节点的宽度+节点间隔的宽度） 设置View.2.先序遍历，设置你树的每个节点的矩形框的位置（根据用View的宽度和深度）。
3.先序遍历，找出所有节点在内的最小矩形框。
4.根据最小矩形框，设置View的宽度和高度，并算出原来的View宽，高和现在的View的偏移。
5.先序遍历，根据偏移，使每个节点的矩形框都加上偏移。6.View的OnDraw()中，先序，画出每个节点的框，并画出连线（如果这个节点没有子结点，就不用画线了。）基本就是这样子，因为我的树不是平衡树，所以多了3，4，5。如果你是平衡树，就不用这几步了。

Answer 2

我是这样想的,在得到一个升序数组后,把它用平衡树表示出来.
我作了一个递规,取出数组的中点,然后在对数组分成左右两部分.说求中点在递规中不好定位;我给我的程序你看看:
int CMyTreeView::GetMid(int first ,int last, int array[])
{

int i=last-first;
int n;//寻找数组的中点 if((last-first)>2)
{ if(i%2==0)
{
n=i/2;
}
else
{
n=(i+1)/2;
}
}
else
{ }
return n;
}void  CMyTreeView::DevideTree(int first,int last,int array[])
{   
     if((last-first)>2)
{
mid=GetMid(first,last,array);
str1.Format("%d",array[mid-1]);
dc.TextOut(minpointx,minpointy,str);
DevideTree(first,mid-1,array[]);
DevideTree(mid+1,last,array[]);
}
else
{
}
}
说求的mid不知道是那个层的,而且左右位置也不知道;

Answer 3

你上面的是建树的过程（即设树节点的int值）
to:说求的mid不知道是那个层的,而且左右位置也不知道;在建树的时候不用知道mid是哪个层,也不用知道左右位置
设节点的位置的过程是在生成树之后，对树的先序遍历的时候进行的我把我的设置过程贴出来吧void CDiTree::SetNodesPos()
{
TRACE("CDiTree::SetNodesPos()\n");
TRACE("CDiTree::GetHeight(m_pRoot)");
int nHeight = GetHeight(m_pRoot);
TRACE("\t Height is %d\n",nHeight);

int Width,Height;
CPoint point;
point.x = 0;
point.y = 0;
CShowTreeView* pView =(CShowTreeView*)m_pScView;//(((CMainFrame*)AfxGetMainWnd())->m_wndSplitter.GetPane(0,0));
//应该根据CShowTreeView显示的节点中的字体大小
//来确定每个节点的大小,在此把最大节点的包含的
//矩形存放在m_rectBound中
    m_rectBound.SetRect(0,0,0,0);
CDC* pDC = pView->GetDC();
pDC->SelectObject(pView->m_SelFont);
PreOrder(FindBoundNodeRect,m_pRoot,pDC);
pView->ReleaseDC(pDC);
CSize sizeNode ;
m_rectBound.InflateRect(m_rectBound.Width()/3,m_rectBound.Height()/4);
sizeNode.cy = m_rectBound.bottom * 2;
sizeNode.cx = m_rectBound.right / 2 + 1;
int nHInterval = sizeNode.cy + sizeNode.cy / 3; //节点间的间距
int nWInterval = sizeNode.cx / 2;

// 设置显示区的大小
CSize sizeTotal;
sizeTotal.cx = 500;
sizeTotal.cy = 300;
CSize sizePage,sizeLine; double nWid= pow(2,nHeight-1) ;
Width = (int)(nWid*sizeNode.cx+(nWid-1)*nWInterval);
Height = (int)(nHeight*sizeNode.cy+(nHeight-1)*nHInterval);
TRACE("width is %d,height is %d\n",Width,Height);
sizeTotal.cx = Width;
sizeTotal.cy =  Height;
TRACE("void CDiTree::SetNodesPosition(node *n, int tag, int nlevel, int nWith,CPoint point)\n");
    SetNodesPosition(m_pRoot,LeftNode,1,Width,point,sizeNode);
m_rectBound = m_pRoot->m_Rect ;
PreOrder(FindBoundRect,m_pRoot,NULL);
TRACE("the boundRect center point is %d ,%d\n",m_rectBound.CenterPoint().x,m_rectBound.CenterPoint().y);
CRect rectClient ;
pView->GetClientRect(rectClient);
    
if((m_rectBound.left >= rectClient.left)
&&(m_rectBound.top >= rectClient.top)
&&(m_rectBound.bottom <= rectClient.bottom)
&&(m_rectBound.right <= rectClient.right))
{
//若树大小小于客户区，把树放置在客户区中间

        PreOrder(SetTreeViewCenter,m_pRoot,pView);
}
else
{
//若树大小大于客户区，使整个树向左上偏移，除去视图内多余的区域
PreOrder(SubTreeViewMarge,m_pRoot,pView);
sizeTotal.cx = m_rectBound.Width() + 2*LeftRightMargin;
sizeTotal.cy = m_rectBound.Height() + 2*TopBottonMargin;
}
pView->SetScrollSizes(MM_TEXT,sizeTotal);
    }

Answer 4

再说一下我原来的想法:我先对输入的数据进行排序,然后做一个取中间值的函数,在做一个将原有数组分成两个,一个左一个右的数组,然后递规调用,这样好像挺简单,但是我要把他们显示出来,而且每次mid后不知道怎么做了,就是不知道中间的这个点是在左边还是在右边,是在哪一个层上,真烦人:(

Answer 5

怎么没见你new一个结点呀？应该是这个样子：
找到mid元素，就new一个节点，把这个节点作为父节点的左子节点或右子结点，然后再输入这个数组的起始和终点递归生成树就可以了把你和程序改动如下void  CMyTreeView::DevideTree(int first,int last,int array[],node* n)
{   
     if((last-first)>2)
{
mid=GetMid(first,last,array);
                  node* nn= new node;
                  nn->lp = NULL;
                  nn->rp = NULL;
                  nn->nSum = mid;
if(mid<first)
                      n->lp = nn; //左子结点
                  else
                      n->rp = nn;  
DevideTree(first,mid-1,array[]);
DevideTree(mid+1,last,array[]);
}
else
{
             return;
}
}
调用的时候，输入node* 为根节点就是了

Answer 6

忘了，
DevideTree(first,mid-1,array[]);
DevideTree(mid+1,last,array[]);改为
DevideTree(first,mid-1,array[],n->lp);
DevideTree(mid+1,last,array[],n->rp);

Answer 7

to:qinghero(水阔长江) 
我还要改改看,按你的去做把,昨天的还没有作出来,今天又给了我一个任务,就是要实现一个图形在3D坐标下,绕一个坐标轴旋转,我实现了2d的转换,但是3d的效果不知道怎么下手,你能看看吗?给我你的EMAIL,我给你传一个实例过去,也就是效果.多谢你了

Answer 8

对了,vc 中的坐标不知道有没有z轴,在2d情况下,我乘一个矩阵就行了,但是当3d时,我又3d的旋转矩阵,但是坐标轴不知道怎么表示.比如说2d时,ddc->moveto(x,y)就行了,但三d时,是不是moveto(x,y,z),好像没有这样用的,而且还不能用OpenGL.

Answer 9

这要用到图形学的东西吧
很久不用了，不知道还记不记得
[email protected]