数据结构-核心算法

树的性质

证明：
第i层上最多的结点数为m^i-1。 （i=1~h）
显然当高度为h的m次树为满m次树时结点个数最多，因此有以下关系。

最多结点数=每一层最多结点数之和=m⁰+m¹+m²+…+m^h-1= $\frac{m^h-1}{m-1}$

证明：
设具有n个结点的m次树的最小高度为h，若在该树中前h-1层都是满的，即每一层的结点树都等于m^i-1（1≤i≤h-1）个，第h层（即最后一层）的结点树可能满，也可能不满，但至少有一个结点，则该树具有最小的高度。

---

⭐线性结构和树形结构的比较

---

⭐⭐二叉树先序、中序、后序遍历递归算法

void PreOrder(BiTree bt)
{
//先序遍历
    if(bt!=NULL)
    {
        printf("%c",bt->data);
        PreOrder(bt->lchild);
        PreOrder(bt->rchild);
    }
}

void InOrder(BiTree bt)
{
//中序遍历
    if(bt!=NULL)
    {
        InOrder(bt->lchild);
        printf("%c",bt->data);
        InOrder(bt->rchild);
    }

}

void PostOrder(BiTree bt)
{
//后序遍历
    if(bt!=NULL)
    {
        PostOrder(bt->lchild);
        PostOrder(bt->rchild);
        printf("%c",bt->data);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

⭐⭐⭐⭐⭐二叉树的深度

求二叉树b的高度的递归模型f(b)如下：

f(b) = 0		//若b=NULL
f(b) = MAX { f(b->lchild),f(b->rchild)}+1 //其他情况
1
2

递归算法如下：

int BTHeight(BiTree bt)
{
    int lchild,rchild;
    if(bt==NULL)
        return 0;
    else{
        lchild=BTHeight(bt->lchild);
        rchild=BTHeight(bt->rchild);
        return (lchild>rchild)?(lchild+1):(rchild+1);
    }
}
1
2
3
4
5
6
7
8
9
10
11

---

⭐⭐孩子兄弟链存储结构

以孩子兄弟链作为树的存储结构设计一个求树t的高度的递归算法

typedef struct tnode
{
    char data; //节点的值
    struct tnode *hp; //指向兄弟
    struct tnode *vp; //指向孩子节点
} TSBNode; //孩子兄弟链存储结构类型
1
2
3
4
5
6

int TreeHeight2(TSBNode *t)
{
    TSBNode *p;
    int h, maxh = 0;
    if (t == NULL)
    {
        return 0; //空树返回0
    }
    else
    {
        cout << "t = " << t->data << endl;
        p = t->vp; //指向第1个孩子节点
        while (p != NULL) //扫描t的所有子树
        {
            h = TreeHeight2(p); //求出p子树的高度
            cout << "h = " << h << endl;
            if (maxh < h)
                maxh = h; //求所有子树的最大高度
            p = p->hp; //继续处理t的其他子树
        }
        return (maxh + 1); //返回maxh+1
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

孩子链存储结构

以孩子链表作为树的存储结构，设计一个求树t的高度的递归算法

int	TreeHeight1(TSonNode *t)
{
	TSonNode *p;
	int i,h,maxh=0;
	if(t==NULL)
		return 0;//空树返回高度0
	else{
		for(i=0;i<MaxSons;i++)
		{
			p=t->sons[i];	//p指向t的第i+1个孩子结点
			if(p!=NULL)//若存在第i+1个孩子
			{
				h=TreeHeight1(p);//求出对应子树的高度
				if(p!=NULL)
				{
					if(maxh<h)
						maxh=h;//求出所有子树的最大高度
				}
			}
		}
		return (maxh+1); //返回maxh+1
	}	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

二叉树的性质

完全二叉树的性质

性质5：

---

二叉树的顺序存储和链式存储的优缺点

---

⭐⭐根据前序和中序（中序和后序）画出二叉树

---

⭐⭐哈夫曼的构造