树的基本概念
- 树是递归定义的结构
结点
- 根节点：树只有一个根结点
结点的度：结点拥有的子树的数量
- 度为0：叶子结点或者终端结点
度不为0：分支结点或者非终端结点
- 分支结点除去根结点也称为内部结点
- 树的度：树中所有结点的度数的最大值
结点关系
祖先结点
- 根结点到该结点的唯一路径的任意结点
- 子孙结点
双亲结点
- 根结点到该结点的唯一路径上最接近该结点的结点
- 孩子结点
兄弟结点
- 有相同双亲结点的结点
层次，高度，深度，树的高度
- 层次：根为第一层，它的孩子为第二层，以此类推
- 结点的深度：根结点开始自顶向下累加
- 结点的高度：叶节点开始自底向上累加
- 树的高度（深度）：树中结点的最大层数
树的性质
1.树中的结点数等于所有结点的度数加1。
- 证明：不难想象，除根结点以外，每个结点有且仅有一个指向它的前驱结点。也就是说每个结点和指向它的分支一一对应。
假设树中一共有b个分支，那么除了根结点，整个树就包含有b个结点，所以整个树的结点数就是这b个结点加上根结点，设为n，则n=b+1。而分支数b也就是所有结点的度数，证毕。
* 2.度为m的树中第i层上至多有m^(i−1)个结点（i≥1）。
* 证明：（数学归纳法）首先考虑i=1的情况：第一层只有根结点，即一个结点，i=1带入式子满足。
假设第i-1层满足这个性质，第i-1层最多有m i-2个结点。
……… ..........
i-1层
………
又因为树的度为m,所以对于第i-1层的每个结点，最多
有m个孩子结点。所以第i层的结点数最多是i-1层的m
倍，所以第i层上最多有m ^(i-1)个结点。
* 3.高度为h的m叉树至多有(m^h-1)/(m-1)个结点
* 4.具有n个结点的m叉树的最小高度为logm(n(m-1)+1) 树的存储结构
顺序存储结构
- 双亲表示法：用一组连续的存储空间存储树的结点，同时在每个结点中，用一个变量存储该结点的双亲结点在数组中的位置。
链式存储结构
- 孩子表示法：把每个结点的孩子结点排列起来存储成一个单链表。所以n个结点就有n个链表；
如果是叶子结点，那这个结点的孩子单链表就是空的；
然后n个单链表的的头指针又存储在一个顺序表（数组）中。
* 孩子兄弟表示法：顾名思义就是要存储孩子和孩子结点的兄弟，具体来说，就是设置两个指针，分别指向该结点的第一个孩子结点和这个孩子结点的右兄弟结点。
顺序存储：
void InitBiTree_Sq(SqBiTree T)
{
int i;
for(i=0; i<MAX_TREE_SIZE; i++)
T[i] = '\0'; //空树无结点，以空字符填充数组
}
void ClearBiTree_Sq(SqBiTree T) //清空与构造算法一样
{
int i;
for(i=0; i<MAX_TREE_SIZE; i++)
T[i] = '\0';
}
void DestroyBiTree_Sq(SqBiTree T)
{
//二叉树无法销毁
}
Status BiTreeEmpty_Sq(SqBiTree T)
{
return T[0]=='\0' ? TRUE : FALSE;
}
Status CreateBiTree_Le_Sq(FILE *fp, SqBiTree T)
{
char ch;
int i = 0;
while(Scanf(fp, "%c", &ch)==1 && ch!='\n')
{
if(ch == '^')
T[i++] = '\0';
else
T[i++] = ch;
}
return OK;
}
Status CreateBiTree_Pre_Sq(FILE *fp, SqBiTree T, int i)
{
char ch;
Scanf(fp, "%c", &ch);
if(ch == '^')
T[i] = '\0';
else
{
T[i] = ch;
CreateBiTree_Pre_Sq(fp, T, 2*i+1);
CreateBiTree_Pre_Sq(fp, T, 2*i+2);
}
return OK;
}
int BiTreeLength_Sq(SqBiTree T)
{
int len;
for(len=MAX_TREE_SIZE; len-1>=0; len--) //寻找最后一个结点
{
if(T[len-1]!='\0')
break;
}
return len;
}
int BiTreeDepth_Sq(SqBiTree T)
{
int level=0;
while((int)pow(2, level)-1<BiTreeLength_Sq(T))
level++;
return level;
}
Status Root_Sq(SqBiTree T, TElemType_Sq *e)
{
if(BiTreeEmpty_Sq(T)) //空树无根结点
return ERROR;
*e = T[0];
return OK;
}
TElemType_Sq Value_Sq(SqBiTree T, Position s)
{
int i =(int)pow(2, s.level-1)+s.order-2; //将位序转变为树的次序（层序序列）
return T[i];
}
Status Assign_Sq(SqBiTree T, Position s, TElemType_Sq value)
{
int i =(int)pow(2, s.level-1)+s.order-2;
if(value=='\0' && (T[2*i+1]!='\0' || T[2*i+2]!='\0')) //元素value是空值但s位序的结点有子树
return ERROR;
else if(value!='\0' && T[(i+1)/2-1]=='\0') //元素value不为空但s位序的结点无双亲结点
return ERROR;
else
T[i] = value;
return OK;
}
TElemType_Sq Parent_Sq(SqBiTree T, TElemType_Sq e)
{
int i;
if(T[0]!='\0') //空树
{
for(i=0; i<MAX_TREE_SIZE; i++)
{
if(T[i]==e)
return T[(i+1)/2-1];
}
}
return '\0'; //未找到e
}
TElemType_Sq LeftChild_Sq(SqBiTree T, TElemType_Sq e)
{
int i;
if(T[0]=='\0')
return '\0'; //空树
for(i=0; i<MAX_TREE_SIZE; i++)
{
if(T[i]==e)
return T[2*i+1];
}
return '\0'; //未找到e
}
TElemType_Sq RightChild_Sq(SqBiTree T, TElemType_Sq e)
{
int i;
if(T[0]=='\0')
return '\0'; //空树
for(i=0; i<MAX_TREE_SIZE; i++)
{
if(T[i]==e)
return T[2*i+2];
}
return '\0'; //未找到e
}
TElemType_Sq LeftSibling_Sq(SqBiTree T, TElemType_Sq e)
{
int i;
if(T[0]=='\0')
return '\0'; //空树
for(i=0; i<MAX_TREE_SIZE; i++)
{
if(i%2==0 && T[i]==e) //i为偶序数
return T[i-1];
}
return '\0'; //未找到e
}
TElemType_Sq RightSibling_Sq(SqBiTree T, TElemType_Sq e)
{
int i;
if(T[0]=='\0')
return '\0'; //空树
for(i=0; i<MAX_TREE_SIZE; i++)
{
if(i%2!=0 && T[i]==e) //i为奇序数
return T[i+1];
}
return '\0'; //未找到e
}
void LevelOrderTraverse_Sq(SqBiTree T, void(Visit)(TElemType_Sq))
{
int i;
int len = BiTreeLength_Sq(T);
for(i=0; i<len; i++)
{
if(T[i]!='\0')
Visit(T[i]);
}
}
void PreOrderTraverse_Sq(SqBiTree T, void(Visit)(TElemType_Sq), int i)
{
if(T[i]!='\0')
{
Visit(T[i]);
PreOrderTraverse_Sq(T, Visit, 2*i+1);
PreOrderTraverse_Sq(T, Visit, 2*i+2);
}
}
void InOrderTraverse_Sq(SqBiTree T, void(Visit)(TElemType_Sq), int i)
{
if(T[i]!='\0')
{
InOrderTraverse_Sq(T, Visit, 2*i+1);
Visit(T[i]);
InOrderTraverse_Sq(T, Visit, 2*i+2);
}
}
void PostOrderTraverse_Sq(SqBiTree T, void(Visit)(TElemType_Sq), int i)
{
if(T[i]!='\0')
{
PostOrderTraverse_Sq(T, Visit, 2*i+1);
PostOrderTraverse_Sq(T, Visit, 2*i+2);
Visit(T[i]);
}
}
void Print_Sq(SqBiTree T)
{
int i, j, level;
char tmp[MAX_TREE_SIZE][MAX_TREE_SIZE] = {};
level = BiTreeDepth_Sq(T);
for(i=1; i<=level; i++)
for(j=1; j<=(int)pow(2,i-1); j++)
tmp[i-1][(int)pow(2,level-i)+(j-1)*(int)pow(2,level-i+1)-1] = T[(int)pow(2,i-1)-1+j-1];
for(i=0; i<level; i++)
{
for(j=0; j<2*(int)pow(2,level-1)-1; j++)
{
if(tmp[i][j]!='\0')
printf("%c", tmp[i][j]);
else
printf(" ");
}
printf("\n");
}
}双亲表示：
void InitTree_P(PTree *T)
{
(*T).n = 0; //结点数量
}
void ClearTree_P(PTree *T)
{
(*T).n = 0;
}
void DestroyTree_P(PTree *T)
{
//此存储结构下的树无法销毁
}
Status TreeEmpty_P(PTree T)
{
return (T.n ? FALSE : TRUE);
}
Status CreateTree_P(FILE *fp, PTree *T)
{
TElemType_P ch, p, tmp;
int i, j;
Scanf(fp, "%c", &ch);
printf("录入树的根结点 %c \n", ch);
Scanf(fp, "%c", &tmp); //跳过换行符
if(ch!='^')
{
i = 0; //根结点起点设为0
(*T).nodes[i].data = ch;
(*T).nodes[i].parent = -1;
j = -1;
while(!feof(fp))
{
Scanf(fp, "%c", &p);
printf("依次录入 %c 的孩子结点：", p);
j++;
while(1)
{
Scanf(fp, "%c", &ch);
if(ch=='^' || ch=='\n')
{
if(ch=='^')
{
printf("%c", ch);
Scanf(fp, "%c", &tmp); //跳过换行符
}
break;
}
else
{
printf("%c", ch);
i++;
(*T).nodes[i].data = ch;
(*T).nodes[i].parent = j;
}
}
printf("\n");
}
(*T).n = i+1;
}
return OK;
}
int TreeDegree_P(PTree T)
{
int i, tmp, count;
int max;
max = count = 0;
if(T.n)
{
tmp = T.nodes[0].parent;
for(i=0; i<T.n; i++)
{
if(T.nodes[i].parent!=tmp)
{
tmp = T.nodes[i].parent;
count = 1;
}
else
count++;
if(count>max)
max = count;
}
}
return max;
}
int TreeDepth_P(PTree T) //由于按层序序列存储，故最后存储的结点必在最大层
{
int k, level;
k = T.n-1;
level = 0;
if(T.n!=0)
{
level++;
k = T.nodes[k].parent;
while(k!=-1)
{
level++;
k = T.nodes[k].parent;
}
}
return level;
}
TElemType_P Root_P(PTree T)
{
if(T.n)
return T.nodes[0].data;
return '\0';
}
TElemType_P Value_P(PTree T, int i)
{
if(T.n && i>0 && i<=T.n)
return T.nodes[i-1].data;
else
return '\0';
}
int Order_P(PTree T, TElemType_P e)
{
int i;
int k = -1;
for(i=0; i<T.n; i++)
{
if(T.nodes[i].data==e)
{
k = i;
break;
}
}
return k;
}
Status Assign_P(PTree *T, TElemType_P e, TElemType_P value)
{
int i;
for(i=0; i<(*T).n; i++)
{
if((*T).nodes[i].data==e)
{
(*T).nodes[i].data = value;
return OK;
}
}
return ERROR;
}
TElemType_P ChildValue_P(PTree T, TElemType_P e, int order)
{
int i, p, count;
count = 0;
for(i=1; i<T.n; i++)
{
p = T.nodes[i].parent;
if(T.nodes[p].data==e)
{
count++;
if(count==order)
return T.nodes[i].data;
}
}
return '\0';
}
TElemType_P Sibling_P(PTree T, TElemType_P e, int mark)
{
int i;
if(!TreeEmpty_P(T) && e!=T.nodes[0].data)
{
for(i=1; i<T.n; i++)
{
if(mark==0) //左兄弟
{
if(T.nodes[i].data==e)
break;
if(T.nodes[i].data!=e && i+1<T.n && T.nodes[i+1].parent==T.nodes[i].parent && T.nodes[i+1].data==e)
return T.nodes[i].data;
}
if(mark==1) //右兄弟
{
if(T.nodes[i].data==e && i+1<T.n && T.nodes[i].parent==T.nodes[i+1].parent)
return T.nodes[i+1].data;
}
}
}
return '\0';
}
int ChildCount_P(PTree T, TElemType_P p)
{
int k1, k2, count;
if(TreeEmpty_P(T)) //空树
return -1;
k1 = Order_P(T, p);
if(k1<0) //p结点不存在
return -2;
k2 = k1 + 1;
count = 0;
while(k2<T.n) //统计孩子个数
{
if(T.nodes[k2].parent==k1)
count++;
if(T.nodes[k2].parent>k1)
break;
k2++;
}
return count;
}
int ChildSeat_P(PTree T, TElemType_P p, int i)
{
int k0, k1, k2, count;
if(TreeEmpty_P(T)) //空树
return -1;
k0 = ChildCount_P(T, p); //k0标记孩子个数
if(i<0 || k0<0 || i>k0+1) //插入位置不正确
return -2;
k1 = Order_P(T, p);
k2 = k1 + 1;
if(i==0) //此时i为p最后一个结点的下一个位置
{
while(k2<T.n)
{
if(T.nodes[k2].parent>k1)
break;
k2++;
}
}
else
{
count = 0;
while(k2<T.n)
{
if(T.nodes[k2].parent>=k1)
{
count++;
if(count==i)
break;
}
k2++;
}
}
return k2;
}
Status InsertChild_P(PTree *T, TElemType_P p, int i, TElemType_P e)
{
int k0, start, end;
if(TreeEmpty_P((*T)) || !e) //空树或e为空字符
return ERROR;
k0 = 0; //k0标记p的位置
while(k0<(*T).n)
{
if((*T).nodes[k0].data==p)
break;
k0++;
}
if(k0==(*T).n) //p不存在
return ERROR;
start = ChildSeat_P(*T, p, i); //e结点的插入位置
if(start<=0) //插入位置不正确
return ERROR;
end = (*T).n;
while(end>start)
{
(*T).nodes[end].data = (*T).nodes[end-1].data;
if((*T).nodes[end-1].parent<start)
(*T).nodes[end].parent = (*T).nodes[end-1].parent;
else
(*T).nodes[end].parent = (*T).nodes[end-1].parent+1;
end--;
}
(*T).nodes[start].data = e;
(*T).nodes[start].parent = k0;
(*T).n++;
return OK;
}
Status InsertTree_P(PTree *T, TElemType_P p, int i, PTree t)
{
int k;
if(TreeEmpty_P((*T)) || TreeEmpty_P(t)) //空树
return ERROR;
for(k=0; k<t.n; k++)
{
if(k==0)
InsertChild_P(T, p, i, t.nodes[k].data);
else
InsertChild_P(T, t.nodes[t.nodes[k].parent].data, 0, t.nodes[k].data);
}
return OK;
}
Status DeleteTree_P(PTree *T, TElemType_P p, int i)
{
int k1; //k1标记p的位置
int k2 , count; //k2标记第i棵子树起点
int k3;
int stack[MAX_TREE_SIZE], m, n;
int k4, k5, order[MAX_TREE_SIZE] = {};
for(k1=0; k1<(*T).n; k1++)
{
if((*T).nodes[k1].data==p)
break;
if(k1==(*T).n-1)
return ERROR;
}
count = 0;
for(k2=k1+1; k2<(*T).n; k2++)
{
if((*T).nodes[k2].parent==k1)
{
count++;
if(count==i)
break;
}
if(k2==(*T).n-1)
return ERROR;
}
m = n = 0;
stack[n] = k2;
n++;
(*T).nodes[k2].data = '\0'; //抹掉此处的值
k3=k2+1;
while(k3<(*T).n && m<n)
{
if((*T).nodes[k3].parent<stack[m])
k3++;
else if((*T).nodes[k3].parent>stack[m])
m++;
else //(*T).nodes[k3].parent==stack[m]
{
(*T).nodes[k3].data = '\0'; //抹掉此处的值
stack[n] = k3;
n++;
k3++;
}
}
k5 = 0;
for(k4=0; k4<(*T).n; k4++) //遍历树，找出各结点现在的实际位置
{
if((*T).nodes[k4].data)
{
order[k4] = k5;
k5++;
if(k4) //不为头结点
(*T).nodes[k4].parent = order[(*T).nodes[k4].parent]; //当前结点双亲结点位置发生变化
}
}
k4 = -1;
k5 = 0;
while(k5<(*T).n) //遍历，去掉删除的结点
{
if((*T).nodes[k5].data)
{
k4++;
(*T).nodes[k4].data = (*T).nodes[k5].data;
(*T).nodes[k4].parent = (*T).nodes[k5].parent;
}
k5++;
}
(*T).n = k4+1;
return OK;
}
void LevelOrderTraverse_P(PTree T, void(Visit)(TElemType_P))
{
int i;
for(i=0; i<T.n; i++)
Visit(T.nodes[i].data);
}
void Print_P(PTree T)
{
int row[MAX_TREE_SIZE]; //各结点实际所处行
int col[MAX_TREE_SIZE]; //各结点在其兄弟中的次序
int i, j, tmp; //tmp存放当前结点的父结点位置
int x[MAX_TREE_SIZE], y[MAX_TREE_SIZE]; //存放各结点打印时所处行和列（从0开始计数）
int count;
int t[MAX_TREE_SIZE][MAX_TREE_SIZE]={}; //孩子链表存储结构
char a[MAX_TREE_SIZE][MAX_TREE_SIZE]={}; //按树的形状存放结点
SqStack S;
SElemType_Sq e;
if(T.n)
{
j = 1; //j统计某孩子次序
row[0] = 1;
col[0] = j;
tmp = T.nodes[0].parent;
for(i=1; i<T.n; i++)
{
if(T.nodes[i].parent!=tmp)
{
j = 1; //若与上一个结点不属于同一双亲结点，则重新开始计数
tmp = T.nodes[i].parent;
}
else
j++;
col[i] = j;
row[i] = row[T.nodes[i].parent]+1;
}
for(i=1; i<T.n; i++) //构造孩子链表
{
tmp = T.nodes[i].parent;
t[tmp][col[i]-1] = i;
}
count = 0; //追踪行
InitStack_Sq(&S);
Push_Sq(&S, 0);
while(!StackEmpty_Sq(S)) //确定每个结点在树中所在行
{
GetTop_Sq(S, &e);
if(col[e]!=1)
count++;
x[e] = count;
if(t[e][0])
Push_Sq(&S, t[e][0]);
else
{
while(!StackEmpty_Sq(S))
{
Pop_Sq(&S, &e);
if(t[T.nodes[e].parent][col[e]])
{
Push_Sq(&S, t[T.nodes[e].parent][col[e]]);
break;
}
}
}
}
for(i=0; i<T.n; i++) //确定每个结点在树中所在列
y[i] = row[i]-1;
for(i=0; i<T.n; i++) //将各结点放入a中适当位置
a[x[i]][2*y[i]] = T.nodes[i].data;
for(i=0; i<=count; i++)
{
for(j=0; j<=2*y[T.n-1]; j++)
{
if(a[i][j])
printf("%c", a[i][j]);
else
printf(".");
}
printf("\n");
}
}
else
printf("空树无法打印！！\n");
}
![[数据结构]-AVL树](https://ucc.alicdn.com/pic/developer-ecology/6v24jawhpy3hi_6852840861db4926b08602d40f80e75a.jpeg?x-oss-process=image/resize,h_160,m_lfit)