二叉树基本性质和操作

树—Tree

定义

树（Tree）是n（n≥0）个结点的有限集；n=0时称为空树；在任意一棵非空树中：

(1) 有且仅有一个特定的称为根（Root）的结点

(2) 当n>1时，其余结点可分为m（m>0）个互不相交的有限集$T_1、T_2、......、T_m$，其中每一个集合本身又是一棵树，并且称为根的子树

树的基本术语

(１) 结点——树的结点包含一个数据元素及若干指向其子树的分支

(２) 结点的度——结点所拥有的分支数目或后继结点个数称为该结点的度

(３) 树的度——树中各结点度的最大值称为该树的度

(４) 叶结点 (终端结点) ——度为零的结点称为叶结点

(５) 分支结点 (非终端结点) ——度不为零的结点称为分支结点

(６) 孩子、双亲结点——一个结点的子树的根称为该结点的孩子，该结点称为孩子的双亲

( 7 ) 兄弟结点——同一双亲结点下的孩子结点互称为兄弟结点

( 8 ) 堂兄弟——双亲互为兄弟的两个结点互称为堂兄

( 9 ) 子孙结点——一个结点的所有子树中的结点称之为该结点的子孙结点

(10) 祖先结点——从树根结点到达一个结点的路径上的所有结点称为该结点的祖先结点

(11) 结点的层次——树的根结点的层次为１，其余结点的层次等于它双亲结点的层次加１（某结点在第L层，它的子树的根就在L+1层）

(12) 树的深度——树中结点的最大层次称为树的深度 (或高度)

(13) 有序树和无序树——如果一棵树中的结点的各子树从左到右是有次序的， 即若交换了某结点各子树的相对位置， 则构成了不同的

树， 称这样的树为有序树，反之，则为无序树

(14) 森林——ｍ (ｍ≥０) 棵互不相交树的集合称为森林

树的基本性质

1、结点数 = 总度数 + 1

2、

3、度为m的树第i层最多有$m^{i-1}$个结点

4、高度为h的m叉树最多有$\frac{m^h-1}{m-1}$个结点

5、高度为h的m叉树至少有h个结点，高度为h、度为m的树至少有$h+m-1$个结点

6、具有n个结点的m叉树的最小高度为$[lo{g}_m(n(m-1)+1)]$

二叉树

定义

二叉树（Binary Tree）是有n（n≥0）个结点的有限集合；该集合或者为空集（称为空二叉树），或者由一个根结点和两颗互不相交的、

分别称为根结点的左子树和右子树的二叉树组成

二叉树的特点

1、每个结点最多有两棵子树，二叉树中结点的度不大于2

2、左子树和右子树是有顺序的，次序不能任意颠倒

3、即使树中某结点只有一颗子树，也要区分它是左子树还是右子树

二叉树的性质

● 在二叉树的第i层上至多有（i≥0）$2^{i-1}$个结点

● 深度为k的二叉树至多有（k≥1）$2^k-1$个结点

● 对任意一棵二叉树T， 如果其叶子结点数为m，度为２的结点数为n，则有$m=n+1$

● 具有N个结点的完全二叉树的深度为([x]为不大于x的最大整数)：$[lo{g}_{2}N]+1$

● 如果一棵有ｎ个结点的完全二叉树的结点按层次编号，每层从左到右) 则对任一结点ｉ(1≤ｉ≤ｎ) 有:

➀ 如果 $i＝1$， 结点ｉ是根结点， 无双亲； 如果ｉ>1， 则其双亲结点是结点$\frac{i}{2}$

➁ 如果 $2i>ｎ$， 则结点ｉ无左孩子， 该结点为叶子结点， 否则其左孩子是结点$2i$

➂ 如果 $2i+1>ｎ$， 则结点ｉ无右孩子， 该结点为叶子结点， 否则其右孩子是结点 $2i＋1$

​

特殊二叉树

斜树

定义

所有的结点都是只有左子树的二叉树叫做左斜树，所有的结点都是只有右子树的二叉树叫做右斜树；这两者统称为斜树

特点

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

如图：

满二叉树

定义

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树

特点

满二叉树很符合强迫症患者，其特点有：

1、叶子只能出现在最下一层，出现在其它层就不可能达成平衡

2、非叶子结点的度一定是2

3、在同样的深度的二叉树中，满二叉树的结点个数最多，叶子数最多

如图：

完全二叉树

定义

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

同，则这课二叉树称为完全二叉树

特点

1、叶子结点只能出现在最下两层

2、最下面的叶子一定集中在左部连续位置

3、倒数二层，若有叶子结点，一定都在右部连续位置

4、如果结点度为1，则该结点只有左孩子，即不存在只有右孩子的情况

5、同样结点数的二叉树，完全二叉树的深度最小

如图：

判断某二叉树是否为完全二叉树：给每个结点按照满二叉树的结构逐层顺序编号，如果编号出现空档，就说明不是完全二叉树，否则就是

二叉树操作

结构体

struct Tree { 
    char data; Tree *lchild, *rchild; }; 

创建二叉树

//先序创建二叉树 void CreateTree(Tree *&T) { 
    char c; cin >> c; if (c == '#') { 
    T = NULL; } else { 
    T = new Tree; T->data = c; CreateTree(T->lchild); CreateTree(T->rchild); } } 

遍历

先序遍历-DLR

1、访问根结点

2、先序遍历根结点的左子树

3、先序遍历根结点的右子树

//先序遍历 void PreOrder(Tree *T) { 
    if (T) { 
    cout << T->data; PreOrder(T->lchild); PreOrder(T->rchild); } } 

中序遍历-LDR

1、中序遍历根结点的左子树

2、访问根结点

3、中序遍历根结点的右子树

//中序遍历 void InOrder(Tree *T) { 
    if (T) { 
    InOrder(T->lchild); cout << T->data; InOrder(T->rchild); } } 

后序遍历-LRD

1、后序遍历根结点的左子树

2、后序遍历根结点的右子树

3、访问根结点

//后序遍历 void PostOrder(Tree *T) { 
    if (T) { 
    PostOrder(T->lchild); PostOrder(T->rchild); cout << T->data; } } 

层序遍历

层序遍历可以使用队列实现，方法如下：

首先判断队列是否为空：

1、若队列为空，则直接 return

2、队列不为空：

① 若队头有左子树，左孩子入队

② 若队头有右子树，右孩子入队

③ 队头出队

//层序遍历 void LevelOrder(Tree *T){ 
    queue<Tree*> q; if(T){ 
    q.push(T); } while(!q.empty()){ 
    cout<<q.front()->data; if(q.front()->lchild){ 
    q.push(q.front()->lchild); } if(q.front()->rchild){ 
    q.push(q.front()->rchild); } q.pop(); } return; } 

双序遍历

1、访问这个结点

2、按双序遍历左子树

3、再访问这个结点

4、按双序遍历右子树

//双序遍历 void DoubleOrder(Tree *T) { 
    if (T) { 
    cout << T->data; DoubleOrder(T->lchild); cout << T->data; DoubleOrder(T->rchild); } } 

树的深度

树的深度用到递归算法，递归计算左子树和右子树的树深度，每次返回的是左子树和右子树中深度的最大值+1

//树的深度 int Depth(Tree *T) { 
    if (!T) { 
    return 0; } else { 
    int l = Depth(T->lchild); int r = Depth(T->rchild); return l > r ? l + 1 : r + 1; } } 

结点个数

结点个数也是用的递归，递归计算左子树和右子树的结点数，相加起来再+1

//结点个数 int NodeCount(Tree *T) { 
    if (!T) { 
    return 0; } else { 
    int l = NodeCount(T->lchild); int r = NodeCount(T->rchild); return l + r + 1; } } 

叶子结点个数

叶子结点个数有3种情况：

1、树空，返回0

2、左子树和右子树都为空，根结点即为叶子结点，返回1

3、左子树和右子树存在，递归计算左子树和右子树的叶子结点数，再相加

//叶子结点个数 int LeafCount(Tree *T) { 
    if (!T) { 
    return 0; } else if (!T->lchild && !T->rchild) { 
    return 1; } else { 
    int l = LeafCount(T->lchild); int r = LeafCount(T->rchild); return l + r; } } 

叶子结点到根结点的路径

使用字符数组存放数据，步骤如下：

1、若树不为空：

① 若左子树和右子树都为空，即该结点为叶子结点，打印数组

② 若存在左子树或右子树，递归左子树或右子树，结束递归条件即为”叶子结点”

//叶子结点到根结点的路径 void LeafPath(Tree *T, char path[], int len) { 
    if (T) { 
    path[len++] = T->data; if (!T->lchild && !T->rchild) { 
    for (int i = len - 1; i >= 0; i--) { 
    cout << path[i] << " "; } cout << endl; } else { 
    LeafPath(T->lchild, path, len); LeafPath(T->rchild, path, len); } } } 

左右结点互换

左右结点互换分为两步：

1、根结点的左孩子和右孩子互换

2、递归左子树，递归右子树

//二叉树左右结点互换 void NodeSwap(Tree *&T) { 
    Tree *t; if (T) { 
    t = T->lchild; T->lchild = T->rchild; T->rchild = t; NodeSwap(T->lchild); NodeSwap(T->rchild); } } 

完整程序

#include 
     using namespace std; struct Tree { 
    char data; Tree *lchild, *rchild; }; //先序创建二叉树 void CreateTree(Tree *&T) { 
    char c; cin >> c; if (c == '#') { 
    T = NULL; } else { 
    T = new Tree; T->data = c; CreateTree(T->lchild); CreateTree(T->rchild); } } //先序遍历 void PreOrder(Tree *T) { 
    if (T) { 
    cout << T->data; PreOrder(T->lchild); PreOrder(T->rchild); } } //中序遍历 void InOrder(Tree *T) { 
    if (T) { 
    InOrder(T->lchild); cout << T->data; InOrder(T->rchild); } } //后序遍历 void PostOrder(Tree *T) { 
    if (T) { 
    PostOrder(T->lchild); PostOrder(T->rchild); cout << T->data; } } //层序遍历 void LevelOrder(Tree *T) { 
    queue<Tree*> q; if(T) { 
    q.push(T); } while(!q.empty()) { 
    cout<<q.front()->data; if(q.front()->lchild) { 
    q.push(q.front()->lchild); } if(q.front()->rchild) { 
    q.push(q.front()->rchild); } q.pop(); } return; } //双序遍历 void DoubleOrder(Tree *T) { 
    if (T) { 
    cout << T->data; DoubleOrder(T->lchild); cout << T->data; DoubleOrder(T->rchild); } } //树的深度 int Depth(Tree *T) { 
    if (!T) { 
    return 0; } else { 
    int l = Depth(T->lchild); int r = Depth(T->rchild); return l > r ? l + 1 : r + 1; } } //结点个数 int NodeCount(Tree *T) { 
    if (!T) { 
    return 0; } else { 
    int l = NodeCount(T->lchild); int r = NodeCount(T->rchild); return l + r + 1; } } //叶子结点个数 int LeafCount(Tree *T) { 
    if (!T) { 
    return 0; } else if (!T->lchild && !T->rchild) { 
    return 1; } else { 
    int l = LeafCount(T->lchild); int r = LeafCount(T->rchild); return l + r; } } //叶子结点到根结点的路径 void LeafPath(Tree *T, char path[], int len) { 
    if (T) { 
    path[len++] = T->data; if (!T->lchild && !T->rchild) { 
    for (int i = len - 1; i >= 0; i--) { 
    cout << path[i] << " "; } cout << endl; } else { 
    LeafPath(T->lchild, path, len); LeafPath(T->rchild, path, len); } } } //二叉树左右结点互换 void NodeSwap(Tree *&T) { 
    Tree *t; if (T) { 
    t = T->lchild; T->lchild = T->rchild; T->rchild = t; NodeSwap(T->lchild); NodeSwap(T->rchild); } } int main() { 
    Tree *T = new Tree; CreateTree(T); //AB#CDEF#GH cout << "先序遍历："; PreOrder(T); cout << endl; cout << "中序遍历："; InOrder(T); cout << endl; cout << "后序遍历："; PostOrder(T); cout << endl; cout << "层序遍历："; LevelOrder(T); cout << endl; cout << "双序遍历："; DoubleOrder(T); cout << endl; cout << "树的深度：" << Depth(T) << endl; cout << "树的结点个数：" << NodeCount(T) << endl; cout << "叶子结点个数：" << LeafCount(T) << endl; cout << "叶子结点到跟结点的路径：" << endl; char path[100]; int len = 0; LeafPath(T, path, len); Tree *T2 = T; NodeSwap(T2); cout<<"交换后的先序遍历："; PreOrder(T2); cout << endl; } 

树、森林与二叉树的转换

树转换为二叉树

1、加线：在所有兄弟结点之间加一条线

2、去线：对树中的每个结点，只保留它与第一个孩子结点之间的连线，删除它与其他孩子结点之间的连线

3、旋转：以树的根节点为轴心，将整棵树顺时针旋转45°，使之成为二叉树

如图所示：

森林转换为二叉树

森林是由若干棵树组成的，所以完全可以理解为，森林中的每一棵树都是兄弟，可以按照兄弟的处理办法来操作，方法如下：

1、把每棵树转换成二叉树

2、第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵树的根结点的右孩子，用线连接起来，当所有的

二叉树连接起来后就得到了由森林转换来的二叉树

如图所示：

二叉树还原为树

二叉树还原为树就是树转换为二叉树的逆过程

方法如下：

1、加线：若某结点的左孩子结点存在，则将这个左孩子的右孩子结点，右孩子的右孩子结点，右孩子的右孩子的右孩子结点…，就是左

孩子的n个右孩子结点都作为结点的孩子，将该结点与这些右孩子结点用线连接起来

2、去线：删除原二叉树中所有结点与其右孩子结点的连线

3、旋转：旋转得到树

如图所示：

二叉树还原为森林

判断一棵二叉树能够转换成树还是森林，只要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树，如果是森林

方法如下：

1、从根结点开始，若右孩子存在，则把它与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除…，直到所有

右孩子连线都删除为止，得到分离的二叉树

2、再将每棵分离后的二叉树转换为树即可

如图所示：

在所有兄弟结点之间加一条线

2、去线：对树中的每个结点，只保留它与第一个孩子结点之间的连线，删除它与其他孩子结点之间的连线

3、旋转：以树的根节点为轴心，将整棵树顺时针旋转45°，使之成为二叉树

如图所示：

结语