【数据结构】树和二叉树（Tree）

文章目录

• 基本概念
• 二叉树的基本概念和性质
• • 基本概念
  • 性质
  • • 性质1：一个非空二叉树的第i层上最多有2^i-1^ (i>=1) 个结点.
    • 性质2：深度为k的二叉树最多有2^k-1^ (k>=1)个结点。
    • 性质3：任何一颗二叉树中，若叶结点个数为n~0~,度为2的结点个数为n~2~，则n~0~=n~2~+1.
    • 性质4：具有n个结点的完全二叉树的深度为[log(n+1)]（向上取整）
    • 性质5：对一颗有n个结点的完全二叉树按层次自上而下（每层自左向右）对结点从1到n进行编号，则对任意一个结点i（1<=i<=n）有：
• 二叉树的存储结构
• • 顺序存储结构
  • 链式存储结构
• 二叉树的遍历运算
• • 深度优先遍历
  • • 前序遍历
    • 中序遍历
    • 后序遍历
  • 广度优先遍历
  • 遍历规律
• 二叉树其他基本运算
• • 按带外部结点的前序序列建立二叉树
  • 求结点总数
  • 求二叉树的高度
  • 求叶结点个数
  • 清空函数
• 树和森林
• • 树的存储结构
  • • 双亲表示法
    • 双亲孩子表示法
    • 孩子兄弟表示法
• 树、森林和二叉树的相互转换
• 树和森林的遍历
• 408真题
• 参考资料

基本概念

定义：n(n>=0)个结点的有限集合，n=0，空树
结点：表示树中的元素
根结点：第一个元素
叶结点：度为0，即没有子树
分支结点：除叶结点外的其他结点
双亲结点：结点的直接前驱
孩子结点：结点的直接后继
兄弟结点：同一双亲结点的孩子
结点的度：结点的子树个数
结点的层次：根节点层次为1，依次向下加一
树的度：树中所有结点度的最大值
树的高度：树中所有结点层次的最大值
森林:m(m>=0)棵互不相交树的集合

二叉树的基本概念和性质

基本概念

二叉树：每个结点最多可以有两个孩子，且左右子树不能颠倒。

度为2的有序树并不是二叉树。

满二叉树：一颗二叉树中任意一层的结点个数都达到了最大值。
完全二叉树：一颗二叉树只有最下面两层结点的度可以小于2，且最下面一层的结点都集中在该层最左边的连续位置上。

完全二叉树的特征：
（1）叶节点只可能出现在层次最大的两层上。
（2）若某个结点没有左子树，则没有右子树。
（3）满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。

正则二叉树（严格二叉树）：不存在度为1的结点，所有分支结点的度都为2
扩充二叉树：在二叉树里出现空子树的位置增加空的叶结点

扩充二叉树是严格二叉树。

性质

性质1：一个非空二叉树的第i层上最多有2^i-1 (i>=1) 个结点.

推论：一颗满二叉树的第i层的结点数为2^i-1。

性质2：深度为k的二叉树最多有2^k-1 (k>=1)个结点。

推论：深度为k且具有2^k-1 (k>=1)个结点的二叉树一定是满二叉树。

性质3：任何一颗二叉树中，若叶结点个数为n₀,度为2的结点个数为n₂，则n₀=n₂+1.

证明:
结点个数n=n₀+n₁+n₂
边数=n-1
边数=n₁+2*n₂
n₀+n₁+n₂-1=2n₂

性质4：具有n个结点的完全二叉树的深度为[log(n+1)]（向上取整）

性质5：对一颗有n个结点的完全二叉树按层次自上而下（每层自左向右）对结点从1到n进行编号，则对任意一个结点i（1<=i<=n）有：

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

二叉树的存储结构

顺序存储结构

一组地址连续的存储单元依次自上而下，自左向右地存储二叉树中的结点。
对于普通的二叉树，为了体现双亲、孩子等逻辑关系，需要把二叉树填充空结点成为完全二叉树，但这样造成了存储空间的极大浪费。
故，顺序存储结构只用于静态的完全二叉树或接近完全二叉树的二叉树。

链式存储结构

二叉链表结点：链表结点除了要存储元素本身的信息外，还要设置指示结点间逻辑关系的指针。因为二叉树的每个结点最多有两个指针，可以设置两个指针left和right，分别指向左孩子和右孩子。当某个孩子为空时，相应的指针置空。

若二叉树中经常的操作是寻找结点的双亲，每个结点可增加一个指向双亲的指针域parent，这种称为三叉链表结点。

但一般只使用二叉链表结点。

下面给出二叉树的二叉链表表示和实现

#ifndef _BINARY_LINKLIST_H_
#define _BINARY_LINKLIST_H_
#include"BinaryTree.h"

template <class elemType> 
class BinaryLinkList:public binaryTree<elemType>{
private:
    struct Node {  				//二叉链表结点
        Node  *left , *right ;              // 指向左、右孩子的指针
        elemType data;                  // 结点的数据域
        Node() : left(NULL), right(NULL) { }        // 无参构造函数
        Node(elemType value, Node *l = NULL, Node * r =NULL ){
            data=value; left=l; right=r; 
        }
        ~Node() {} 
    };
  
    Node * root;                    // 指向二叉树的根结点
    void clear( Node *t );              
    int size( Node *t ) const;		//二叉树的结点总数
    int height( Node *t ) const;		//二叉树的高度
    int leafNum(Node *t )const;		//二叉树的叶结点个数
    
    void preOrder( Node *t ) const;            // 递归前序遍历
    void inOrder( Node *t ) const;            // 递归中序遍历
    void postOrder( Node *t ) const;            // 递归后序遍历
    void preOrderCreate(elemType flag,Node* & t);      // 创建二叉树，注意t为引用 
    
public: 
    BinaryLinkList() : root( NULL) {}            // 构造空二叉树
    ~BinaryLinkList(){ clear(); }     
       
    bool empty () const{ return root == NULL; }        // 判空
    void clear() {if (root) clear(root); root = NULL;}// 清空
    int size() const { return size(root);}          // 二叉树的结点总数
    int height() const { return height(root); }        // 二叉树的高度
    int leafNum()const{ return leafNum(root); }        // 二叉树的叶子数
    
    void preOrderTraverse() const{ if(root) preOrder(root); }  // 前序遍历 
    void inOrderTraverse() const { if(root) inOrder(root); }  // 中序遍历
    void postOrderTraverse() const{ if(root) postOrder(root); }// 后序遍历
    void levelOrderTraverse() const;            // 层次遍历
    
    void preOrderWithStack()const;			//非递归前序遍历
    void inOrderWithStack()const;			//非递归中序遍历
    void postOrderWithStack()const;			//非递归后序遍历
    
    void preOrderCreate(elemType flag){     // 利用带外部结点的前序序列创建二叉树
        preOrderCreate(flag,root);
    } 

};
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

将Node类型和root指针置为私有的好处是，有利于数据的封装和隐藏。

Node类的设计：
（1）存储和处理树上每一个结点
（2）数据成员：结点的数据及左右孩子的指针
（3）结点的操作：构造和析构
（4）树类的私有内嵌类

递归函数：将用户需要的函数原型作为公有的成员函数。每个成员函数对应一个私有的、带递归参数的成员函数。公有函数调用私有函数完成相应的功能。

二叉树的遍历运算

遍历二叉树，是指一定的规则和顺序访问二叉树的所有结点，使每个结点都被访问一次，且只能一次。
由于二叉树是非线性的，二叉树的遍历实质上是将二叉树的各个结点排列成为一个线性序列。

遍历包括：输出、读取、修改

无论是递归遍历还是非递归，因为都要访问每个结点，故时间复杂度为O（n）

深度优先遍历

用L表示遍历左子树，用R表示遍历右子树，用D表示遍历根结点。
则遍历可分为DLR（前序遍历）,LDR（中序遍历）,LRD（后序遍历）

若一颗二叉树的前序和后序的序列相反，则一定为单支树

前序遍历

（1）前序递归遍历

template <class elemType> 
void BinaryLinkList<elemType>:: preOrder(Node *t) const
{ 
    if (t) {
        cout << t->data << ' ';
        preOrder(t->left);
        preOrder(t->right);
    }
}
1
2
3
4
5
6
7
8
9

(2)非递归前序遍历
算法思想：每遇到一个结点，先访问该结点，并把该结点压入栈中，然后去遍历它的左子树。遍历完左子树后，从栈顶弹出这个结点，并按照它的right域再去遍历右子树。

template <class elemType>
void BinaryLinkList<elemType>::preOrderWithStack()const{
	stack<Node*> s;		//STL中的栈
	Node* p=root;		//工作指针
	
	while(!s.empty()||p){
		if(p){
			cout<<p->data<<' ';
			s.push(p);		//指针入栈
			p = p->left;		//工作指针指向左子树
		}
		else{
			p=s.top();		//获取栈元素
			s.pop();		//退栈
			p=p->right;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

中序遍历

（1）中序递归遍历

template <class elemType> 
void BinaryLinkList<elemType>:: inOrder(Node *t) const
{ 
    if (t) {
        inOrder(t->left);
        cout << t->data << ' ';
        inOrder(t->right);
    }
}
1
2
3
4
5
6
7
8
9

(2)非递归中序遍历
算法思想：每遇到一个结点，先压入栈中，遍历左子树，再从栈中弹出这个结点并访问这个结点，然后按照right域再去遍历该结点的右子树。

template <class elemType>
void BinaryLinkList<elemType>::inOrderWithStack()const{
	stack<Node*> s;		//STL中的栈
	Node* p=root;		//工作指针
	
	while(!s.empty()||p){
		if(p){
			s.push(p);		//指针入栈
			p = p->left;		//工作指针指向左子树
		}
		else{
			p=s.top();		//获取栈元素
			s.pop();		//退栈
			cout<<p->data<<' ';
			p=p->right;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

后序遍历

（1）后序递归遍历

template <class elemType> 
void BinaryLinkList<elemType>::postOrder(Node *t) const
{ 
    if (t) {
        postOrder(t->left);
        postOrder(t->right);
        cout << t->data << ' ';
    }
}
1
2
3
4
5
6
7
8
9

(2)非递归后序遍历
算法思想：每遇到一个结点就压入栈，先遍历它的左子树，再按照它的right域遍历右子树，最后再栈顶弹出该结点并访问它。
在非递归后序遍历中，需要给栈中的每个元素加上一个特征位，来区分是从栈顶的左子树回来的，还是从右子树回来的。

Left表示已访问完该节点的左子树，从左边回来，要继续访问它的右子树。
Right表示已访问完该节点的右子树，从右边回来，要继续访问结点。

template <class elemType>
void BinaryLinkList<elemType>::postOrderWithStack()const{
	enum ChildType{Left,Right};		//特征位定义
	struct StackElem{				//栈中元素的类型
		Node* pointer;
		ChildType flag;
	};
	StackElem elem;
	stack<StackElem> S;		//STL中的栈
	Node* p=root;		//工作指针
	
	while(!S.empty()||p){
		while(p!=NULL){
			elem.pointer=p;
			elem.flag=Left;
			S.push(elem);
			p = p->left;		//沿左子树方向向下周游
		}
		elem=S.top();
		S.top();		//取栈顶元素
		p=elem.pointer;
		if(elem.flag=Left){		//从左边回来，已经遍历完左子树
			elem.flag=Right;
			S.push(elem);
			p=p->right;
		}
		else{		//从右边回来，已经遍历完右子树
			cout<<p->data<<' ';
			p=NULL;
		}
	}
}
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

广度优先遍历

又叫宽度优先遍历，或层次遍历。

是指沿着二叉树的宽度，自上而下，自左向右的遍历二叉树。
由于是一层一层的访问，可以借助队列实现算法。

算法思想：
（1）初始化一个队列，把根结点入队。
（2）若队列非空，重复（3）~（5），否则遍历结束。
（3）出队一个结点，并访问该结点。
（4）若该结点的左子树非空，则将它的左子树入队。
（5）若该结点的右子树非空，则将它的右子树入队。

template <class elemType> 
void BinaryLinkList<elemType>::levelOrderTraverse() const{
  	queue<Node*> que;              // 使用STL中的队列
 	 Node* p = root;

    if (p) 
    	que.push(p);		//根结点入队
    	
    while (!que.empty()) {
        p = que.front();		//取队列首元素
        que.pop();			//出队
        cout << p->data << ' ';
        if (p->left != NULL) 
        	que.push(p->left);
        if (p->right != NULL) 
        	que.push(p->right);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

遍历规律

已知二叉树的前序序列和中序序列，可以唯一确定一颗二叉树。
已知二叉树的后序序列和中序序列，可以唯一确定一颗二叉树。
已知二叉树的前序序列和后序序列，不能唯一确定一颗二叉树。
已知二叉树的层次序列和中序序列，可以唯一确定一颗二叉树。

二叉树其他基本运算

按带外部结点的前序序列建立二叉树

算法思想：递归创建二叉树，先创建根结点再创建左、右子树。
用带外结点的前序序列是可以唯一确定一颗二叉树的，外部结点标识来空子树。

template <class elemType> 
void BinaryLinkList<elemType>::preOrderCreate(elemType flag,Node * & t)  
{ //按带外部结点的前序序列构造二叉链表表示的二叉树
  elemType value;
  cin>>value;
  cout<<value;
  if(value!=flag)            // 递归出口value==flag
  {
        t = new Node(value);
        preOrderCreate(flag, t->left);
        preOrderCreate(flag, t->right);
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

求结点总数

算法思想：若为空子树，则为0；若子树非空，则该子树的结点总数=1（当前结点）+左子树的结点个数+右子树的结点个数

template <class elemType> 
int BinaryLinkList<elemType>::size(Node *t) const
{ 
    if (t == NULL) return 0;
    return 1 + size(t->left) + size(t->right);
} 
1
2
3
4
5
6

求二叉树的高度

算法思想：若为空子树，则为0；若子树非空，则该子树的高度=左、右子树高度大者+1

template <class elemType> 
int BinaryLinkList<elemType>::height(Node *t) const
{ 
    if (t ==NULL) return 0;
    else{
        int lh = height(t->left);
        int rh = height(t->right);

        return 1 + ( (lh > rh) ? lh : rh);
    }
}
1
2
3
4
5
6
7
8
9
10
11

求叶结点个数

算法思想：递归前序遍历二叉树：
（1）空子树，则该子树的叶结点个数为0；
（2）当前结点没有左、右孩子，那么该结点是叶结点，当前子树的叶结点个数+1；
（3）若当前结点为分支结点，则当前子树的叶结点个数=左子树的叶结点个数+右子树的叶结点个数

template <class elemType> 
int BinaryLinkList<elemType>::leafNum(Node* t)const
{
    if (t==NULL) return 0;	//空结点
    else if ( (t->left == NULL) && (t->right == NULL) ) 	//叶结点
        return 1;
    else 					//求左右子树的叶结点个数之和
        return leafNum(t->left) + leafNum(t->right);
}
1
2
3
4
5
6
7
8
9

清空函数

算法思想：删除其左右子树后再删除根节点本身。

template <class elemType> 
void BinaryLinkList<elemType>::clear(Node *t) 
{ 
    if (t->left) clear(t->left);
    if (t->right) clear(t->right);
    delete t;
}
1
2
3
4
5
6
7

树和森林

树的存储结构

双亲表示法

用一位数组存储树的各个结点，结点信息包括数据域data和结点双亲在数据中的下标parent

双亲孩子表示法

把结点放在数组中，数组包含三个域：数据域data，存放父结点位序parent，指向孩子链first。

孩子兄弟表示法

又称二叉树表示法。
链表中结点的两个指针域：firstChild和nextSibling，分别指向该结点的第一个孩子和下一个兄弟。

对于一般的树或者森林，若用孩子兄弟表示法存储，就变成了二叉树的形态
二叉树是一种结构最简单、运算最简便的树形结构。

树、森林和二叉树的相互转换

1.树转换为二叉树

树转换为二义树的规则:每个结点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称“左孩子右兄弟”。由于根结点没有兄弟，所以对应的二叉树没有右子树。

树转换成二叉树的画法:
（1）在兄弟结点之间加一连线;
（2）对每个结点，只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉;
（3）以树根为轴心，顺时针旋转45°。

2.森林转化为二叉树

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

森林转换成二叉树的画法:
（1）将森林中的每棵树转换成相应的二叉树;
（2）每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线;
（3）以第一棵树的根为轴心顺时针旋转45°.

3.二叉树转换为树或者二叉树转换为森林是上面步骤的逆过程。

树和森林的遍历

树的前序遍历与其对应的二叉树的前序序列相同。
树的后序遍历与其对应的二叉树的中序序列相同。

森林的前序遍历与其对应的二叉树的前序序列相同。
森林的后序遍历与其对应的二叉树的中序序列相同。

408真题

1.一颗完全二叉树的第6层（设根是第1层）有8个叶结点，求该完全二叉树最多的结点个数。
根据完全二叉树的定义：只有最下两层的结点的度可以小于2；
由于需要的是结点数最多，故结点数最多的二叉树有7层，其中第6层有8个叶结点。

第六层的结点数：2^6-1=32，其中度为1的结点数为8，那么度为2的结点数为（32-8）=24
第七层的结点数：24*2=48
结点总数：2⁶-1 + 48=111

2.若一颗完全二叉树有768个结点，求该二叉树中叶结点的个数
n₀+n₁+n₂=768;
因n₀=n₂+1,故 2n₀+n₁=769;
根据完全二叉树的定义：结点度为1（即n₁）的个数为0个或者1个。
当n₁=0时，n₀不存在；
当n₁=1时，n₀=384；

3.求有n个结点，且高度为n的二叉树的数目
问题相当于二叉树上第n层最多有多少个结点。结点数、高度、层次均为n的二叉树的叶子结点有2^n-1个不同位置，形成2^n-1个不同的二叉树。

4.求先序序列为a,b,c,d的不同二叉树的个数
求解n个结点能组成的不同的二叉树的个数 或
求解n个不同的结点出栈后得到的出栈序列的个数
公式：Cn=(2n)!/(n+1)! * n!

本题为：(2*4)！/ (4+1)！*4！=14

5.在一颗度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，求树T的叶结点的个数
在一颗度为k的树中，n₀=(k-1)n_k+(k-2)n_n-k-1+…+1*n₂+1
在本题，n₀=3n₄+2n₃+1n₂+1
解得n₀=82

6.若森林F有15条边，25个结点，求F包含的树的个数
在树中：结点数=分支数+1；
在森林中：结点数=分支数+m（m为树的个数）

7.若用一维数组表示一个深度为5、结点个数为10的二叉树，求数组的最短长度
用一维数组存储二叉树要按完全二叉树的格式存储。一般二叉树要“虚结点”，使之成为完全二叉树的形状。
5层至少16个结点，与给的结点数10无关。

8.对任意一棵树，设它有n个结点，求这n个结点的度之和
n-1

9.一颗有n个结点的满二叉树有（）个度为1的结点，有（）个分支结点和（）个叶结点。
0 ； (n-1) /2 ; (n+1) /2

10.设F是由T1，T2，T3三棵树组成的森林，与F对应的二叉树为B，已知T1，T2，T3的结点数分别为n₁,n₂,n₃，求二叉树B的左子树有（）个结点，右子树有（）个结点。
n₁ - 1 ; n₂+n₃

11.给定一颗树，可以找到唯一的一颗二叉树与之对应（√）

参考资料

1.数据结构：树(Tree)【详解】