Fork me on GitHub

树(二)--二叉树

二叉树的定义:二叉树是n(n >= 0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

基本概念

特点:

  • 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点。
  • 左右子树是有顺序的,次序不能任意颠倒。
  • 即使树中某结点只有一棵子树,也要区分它是左子树还是右子树。

三个结点的树有两种形态,三个结点的二叉树有五种形态

五种基本形态:

  • 空二叉树
  • 只有一个根结点
  • 根结点只有左子树
  • 根结点只有右子树
  • 根结点既有左子树又有右子树

特殊二叉树

斜树

所有结点都只有左子树的树叫做左斜树,所有结点都只有右子树的树叫做右斜树,两者统称斜树。

每一层只有一个结点,结点的个数与二叉树深度相同。

满二叉树

所有分支结点都存在左右子树,且所有叶子结点都在同一层上的二叉树。

特点:

  • 叶子只能出现在最下层
  • 非叶子结点的度一定为2
  • 在同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多

完全二叉树

对一棵具有n个结点的二叉树按层序编号,如果编号为i(1 <= i <= n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同,则这棵二叉树称为完全二叉树。

mark

满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。

特点:

  • 叶子结点只能出现在最下两层
  • 最下层的叶子一定集中在左部连续位置
  • 倒数第二层若有叶子结点,则一定都在右部连续位置
  • 如果结点度为1,则该结点只有左孩子,即不存在只有右子树的情况
  • 同样结点数的二叉树,完全二叉树深度最小

二叉树的性质

  • 在二叉树的第i层上至多有2^(i-1)个结点(i >= 1)

  • 深度为k的二叉树至多有2^k - 1 个结点(k >= 1)

  • 对任意一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0 = n2 + 1

    原因:分支总数 = 结点总数 - 1

    ​ n1 + 2*n2 = n0 + n1 + n2 -1

    ​ 故n0 = n2 + 1

  • 具有n个结点的完全二叉树的深度为[log₂n]+1([x]表示不大于x的最大整数)

  • 如果对一棵有n个结点的完全二叉树(其深度为[log₂n]+1)的结点按层序编号,对任一结点i (i <= i <= n)有:

    • 如果i = 1,则结点i是二叉树的根,无双亲;如果i > 1,则其双亲是结点[i/2]
    • 如果2i > n,则i无左孩子(结点i为叶子结点);否则其左孩子是结点2i
    • 如果2i+1 > n,则i无右孩子;否则其右孩子是结点2i+1

若一个偶数结点下一位奇数结点存在,则该奇数结点为该偶数结点的右兄弟

二叉树的存储结构

顺序存储结构

对于一般二叉树,尽管层次编号不能反映逻辑关系,但可以将其按完全二叉树编号,把不存在的结点设置为”^”,依次存入数组中。

极端情况下,右斜树将造成存储空间极大浪费。(k个结点要分配2^k - 1个存储单元空间)

顺序存储结构一般只用于完全二叉树

二叉链表

二叉树每个结点设计为一个数据域和两个指针域。

结构代码:

1
2
3
4
5
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;

也可以增加一个指向双亲的指针构成三叉链表。

求二叉树高度

1
2
3
4
5
6
7
8
9
10
11
12
13
int PostOrderGetHeight(BiTree T)
{
int HL,HR,MaxH;
if(T)
{
HL = PostOrderGetHeight(BT->Left);//求左子树的深度
HR = PostOrderGetHeight(BT->Right);//求右子树的深度
MaxH =(HL > HR)? HL : HR;//取左右子树较大的深度

return (MaxH+1);//返回树的深度
}
else return 0;//空树深度为0
}

​ ~~via文盲

遍历二叉树

二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。(从根结点出发并不意味着先访问根结点)

前序遍历(先访问根结点)

若二叉树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树,再前序遍历右子树。ABDGHCEIF

mark

结构代码:

1
2
3
4
5
6
7
8
void PreOrderTraverse (BiTree T)
{
if (T == NULL)
return;
printf("%c",T->data);//可以改为其他对结点的操作
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}

中序遍历(中间访问根结点)

若树为空,则空操作返回,否则从根结点开始,中序遍历根结点的左子树,然后访问根结点,最后中序遍历右子树。GDHBAEICF

mark

结构代码:

1
2
3
4
5
6
7
8
void InOrderTraverse (BiTree T)
{
if (T == NULL)
return;
InOrderTraverse(T->lchild);
printf("%c",T->data);//可以改为其他对结点的操作
InOrderTraverse(T->rchild);
}

后序遍历(最后访问根结点)

若树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右子树,最后访问根结点。GHDBIEFCA

mark

结构代码:

1
2
3
4
5
6
7
8
void PostOrderTraverse (BiTree T)
{
if (T == NULL)
return;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c",T->data);//可以改为其他对结点的操作
}

非递归表示法(使用堆栈) – 树的深度优先遍历(中序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void InOrderTraverse (BiTree T)
{
Stack S = CreatStack(MaxSize);//创建并初始化堆栈
while (T || !IsEmpty(S))
{
while (T)
{
Push(S,T);//压栈
T = T->Left;//从树左边开始
}
if (!IsEmpty(S))
{
T = Pop(S);//结点弹出堆栈
printf("%c",T->Data);//输出结点
T = T->Right;//转向右子树
}
}
}

层序遍历(使用队列) – 树的广度优先遍历

若树为空,则空操作返回,否则从树的第一层,也就是根结点开始访问,从上而下逐层遍历,在同一层中,按从左到右的顺序对结点逐个访问。ABCDEFGHI

mark

使用队列实现~~via文盲:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void LevelOrderTraverse(BiTree T)
{
Queue Q;//创建队列
if(!T)
return;//是空树则直接返回
Add(Q,T);
while(!IsEmpty(Q))
{//循环,直至队列为空
T = Delate(Q);
printf("%d\n",T->Data);//访问取出队列的结点
if(T->Left)
Add(Q,T->Left);
if(T->Right)
Add(Q,T->Right);
}
}

二元运算表达树及其遍历

三种遍历得到不同的访问结果:

  • 先序遍历得到前缀表达式。

  • 中序遍历得到中缀表达式:但是中缀表达式可能由于优先级不同,出现问题。

    —- 如何解决?输出左子树之前加左括号,输出右子树之后加右括号。

  • 后序遍历得到后缀表达式。

​ ~~via文盲

计算机只会处理线性序列,这些遍历方法其实都是在把树中的结点变成某种有意义的线性序列,给程序的实现带来好处。

已知前序遍历序列和中序遍历序列,可以唯一确定一棵二叉树

已知后序遍历序列和中序遍历序列,可以唯一确定一棵二叉树。

已知前序遍历序列和后序遍历序列,不能确定一棵二叉树。

二叉树的建立

扩展二叉树:将二叉树每个结点的空指针引出一个虚结点,其值为一个特定值(如#),这种处理后的二叉树为原二叉树的扩展二叉树。

扩展二叉树可以做到一个遍历序列确定一棵二叉树。(确定某一个结点有几个孩子,是否为叶子结点等)

mark

假设用前序遍历生成一个结点均为字符的二叉树:

用键盘输入:AB#D##C##

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//按前序输入二叉树中结点的值(一个字符)
//#表示空树,构造二叉链表表示二叉树T
void CreateBiTree (BiTree *T)
{
TElemType ch;
scanf("%c",&ch);
if (ch == '#')
*T = NULL;//空结点
else
{
*T = (BiTree)malloc(sizeof(BiTNode));
if (!*T)
exit(OVERFLOW);//内存已炸
else
{
*T->data = ch;//生成根结点
CreateBiTree (&(*T)->rchild);//构造左子树
CreateBiTree (&(*T)->lchild);//构造右子树
}
}
}
-------------本文结束感谢您的阅读-------------
undefined