第五章 树和二叉树

树的基本概念

1.某节点所拥有的字数的个数称为该节点的度；树中各节点度的最大值称为树的度。
2.路径上经过的边数为路径长度。
3.规定根节点的层数为1，树中所有节点的最大层数称为树的深度；书中每一层结点个数的最大值称为树的宽度。

注意：两个序列中必须有一个中序才能唯一确定一棵二叉树。
根据树的前序和中序确定一棵树：

Binode* Create_pre(char *pre,char *mid,int ipre,int imid,int n)
{
    
	if(n==0)
	return NULL;
	Binode *p=new Binode;
	p->data=pre[ipre];
	int i=0;
	while(pre[ipre]!=mid[imid+i]) i++;
	p->lc=Create_pre(pre,mid,ipre+1,imid,i);
	p->rc=Create_pre(pre,mid,ipre+i+1,imid+i+1,n-i-1);
	return p;
}

确定树的高度：

int Height(Binode* p)
{
    
    if(p==NULL)
        return 0;
    int left,right;
    left=Height(p->lc);
    right=Height(p->rc);
    if(left>right)
        return left+1;
    else
        return right+1;
}