二叉树

树

什么是树？

树(Tree)是n(n≥)个节点的有限集合。当n=0时为空树，n>0时为非空树。

任意一棵非空树满足：

  1. 有且仅有一个称之为根的节点
  2. 除了根节点以外的节点可以分为m(m>0)个互不相交的有限集，每一个集合本身又是一棵树，并且成为根的子数(SubTree)。

image

另外，还有一些其它概念需要知道。

  • 结点

结点包含数据元素及若干指向子树的分支信息。

  • 结点的度

结点拥有的子树个数。图中A结点的度是3，结点D没有子树，也就是度为0，所以结点D也称之为叶子。

  • 树的度

树中结点的最大度数。

  • 终端结点

度为0的结点，也称为叶子。

  • 分支结点

度大于0的结点。除了叶子都是分支结点。

  • 内部结点

除了树根和叶子都是内部结点。

  • 结点的层次

从根到该结点的层数(“根结点为第1层”不同的书有不同说法)。

  • 树的深度高度

指所有结点中最大层数。图中树的深度为4。

  • 路径

树中两个结点之间的所经过的结点序列。

  • 路径长度

两节点之间路径上经过的边数。比如结点A到E，路径长度为2。

  • 双亲、孩子

结点的子树的根称为该结点的孩子。图中E、F是B的孩子。B、C、D是A的孩子。A就是BCD的双亲。

  • 兄弟

同一个双亲的都是兄弟。

  • 堂兄弟

双亲是亲兄弟的。

  • 祖先

从当前结点到根节点之间所有的结点都是该结点的祖先。图中A、B就是F的祖先。

  • 子孙

子树所有的结点。

  • 有序树

结点的各子树从左到右，不能互换位置。如果图中是一个有序树，那么B就是长子，C是次子。

  • 无序树

结点的各子树可以互换位置。

  • 森林

由m(≥)棵不相交的树组成的集合。

树的存储

采用顺序存储和链式存储两种方式。

顺序存储

双亲表示法

结点A是没有双亲的，所以parent为-1。结点B的双亲是A，存储A的下标0，即parent为0。以此类推即可。那么问题来了？我们直接记录结点数据不就行了吗？为什么记录下标呢？是因为结点数据可能太大。

下标 data parent
0 A -1
1 B 0
2 C 0
3 D 0
4 E 1
5 F 1
6 G 2
7 H 5
孩子表示法

树的度为3，孩子表示法每个结点就会开辟3个孩子域。A有三个孩子，记录下三个孩子的下标。B有两个孩子，剩下的一个孩子域就是-1。

可见，孩子表示法比较浪费空间。但它的好处是找孩子容易。
下标 |data | child| child| child
—|—|—|—|—
0 |A | 1|2|3
1 |B |4|5|-1
2 |C |6|-1|-1
3 |D |-1|-1|-1
4 |E |-1|-1|-1
5 |F |7|-1|-1
6 |G |-1|-1|-1
7 |H |-1|-1|-1

双亲孩子表示法
下标 data parent child child child
0 A -1 1 2 3
1 B 0 4 5 -1
2 C 0 6 -1 -1
3 D 0 -1 -1 -1
4 E 1 -1 -1 -1
5 F 1 7 -1 -1
6 G 2 -1 -1 -1
7 H 5 -1 -1 -1

链式存储

孩子兄弟表示法

左指针指向长子，右指针指向兄弟。兄弟关系在右斜线上。

普通的树不好存储，因为每个结点孩子数不固定。我们可以用孩子兄弟表示法，将树转为二叉树。那么森林转二叉树呢？我们需要把每棵树看作兄弟。将二叉树转为书或者森林呢？凡是右斜线的都是兄弟，都断开。

将上述树转为二叉树：
将上述树转为二叉树

二叉树

什么是二叉树？

二叉树(Binary Tree)是n(n≥)个结点的有限集合。当n=0时为空树，n>0时为非空树。

任意一棵非空树满足：

  1. 有且仅有一个称之为根的结点
  2. 除了根结点以外的结点可以分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身都是二叉树。
  • 什么是满二叉树？

一棵深度为k且有(2^k)-1个结点的二叉树。

  • 什么是完全二叉树？

除了最后一层外，每一层都是满的(达到最大结点数)，最后一层结点是从左向右出现的。

二叉树的性质

  1. 在二叉树的第i层上至多有2^i-1^个结点。
1
二叉树每个结点最多两个叉。第一层也就是根结点，只有一个(2^0)。第二层最多两个结点(2^1)。以此类推。
  1. 深度为k的二叉树至多有2^k^-1个结点
1
根据性质1可知，每一层至多结点数是等比数列。
  1. 对于任何一课二叉树，若叶子数为m，度为2的结点数为n，则m=n+1
1
2
3
4
5
在二叉树中，有三种结点：度为0的、度为1的、度为2的。
分别设为n1,n2,n3  总结点数n，即n=n1+n2+n3
已知结点数n=分支数B+1
而分支数B=2*n3+n1
推出n3+1=n2
  1. 具有n个结点的完全二叉树的深度必为log2n+1

设这个完全二叉树深度为h，那么最少2^h-1^-1+1个结点，至多2^h^-1个结点。所以2^h-1^≤n≤2^h^-1<2^h^ 同时取对数，h-1≤log2n<h，所以h-1=log2n，h=log2n+1

  1. 对于完全二叉树，若从上至下、从左到右编号，则编号为i的结点，其左孩子编号为2i，右孩子编号为2i+1，其双亲 编号为i/2

二叉树的存储

二叉树的存储我们可以用顺序存储。通过补0补成完全二叉树。但是这种存储有个缺点就是可能补0太多，就像我们上文中那个二叉树。所以除非这个树是完全二叉树，我们才用顺序存储，否则不用。

二叉树可以用链式存储。左指针指向长子，右指针指向兄弟。没有就空。

二叉树遍历

按照根的访问顺序不同，根在前面称为先序遍历(DLR),根在中间称为中序遍历(LDR),根在最后称为后序遍历(LRD)。

先序遍历

先序遍历是指先访问根，然后先序遍历左子树，再先序遍历右子树。如果二叉树为空，则空操作。

先序遍历秘籍：访问根，先序遍历左子树，左子树为空或已遍历才可以遍历右子树。

以上文中二叉树图为例，先序遍历为：ABEFHCGD

中序遍历

是指中序遍历左子树，然后访问根，再中序遍历右子树。

以上文中二叉树图为例，先序遍历为：EHFBGCDA

后序遍历

后序遍历是指后序遍历左子树，后序遍历右子树，再访问根。
所以后序遍历最后一个一定是根。

以上文中二叉树图为例，先序遍历为：HFEGDCBA

层次遍历

一层一层的遍历，每一层从左向右。可以用队列控制。

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <queue>//引入队列头文件
using namespace std;

typedef struct Bnode	/*定义二叉树存储结构*/
{ char data;
  struct Bnode *lchild,*rchild;
}Bnode,*Btree;

void Createtree(Btree &T)	/*创建二叉树函数*/
{
    //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
	char ch;
	cin >> ch;
	if(ch=='#')
        T=NULL;			//递归结束，建空树
	else{
		T=new Bnode;
		T->data=ch;					//生成根结点
		Createtree(T->lchild);	//递归创建左子树
		Createtree(T->rchild);	//递归创建右子树
	}
}

void preorder(Btree T)//先序遍历
{
    if(T)
    {
       cout<<T->data<<"  ";
       preorder(T->lchild);
       preorder(T->rchild);
    }
}

void inorder(Btree T)//中序遍历
{
    if(T)
    {
       inorder(T->lchild);
       cout<<T->data<<"  ";
       inorder(T->rchild);
    }
}

void posorder(Btree T)//后序遍历
{
    if(T)
    {
       posorder(T->lchild);
       posorder(T->rchild);
       cout<<T->data<<"  ";
    }
}

bool Leveltraverse(Btree T)
{
    Btree p;
    if(!T)
        return false;
    queue<Btree>Q; //创建一个普通队列(先进先出)，里面存放指针类型
    Q.push(T); //根指针入队
    while(!Q.empty()) //如果队列不空
    {
        p=Q.front();//取出队头元素作为当前扩展结点livenode
        Q.pop(); //队头元素出队
        cout<<p->data<<"  ";
        if(p->lchild)
            Q.push(p->lchild); //左孩子指针入队
        if(p->rchild)
            Q.push(p->rchild); //右孩子指针入队
    }
    return true;
}

int main()
{
    Btree mytree;
    cout<<"按先序次序输入二叉树中结点的值（孩子为空时输入#），创建一棵二叉树"<<endl;
    Createtree(mytree);//创建二叉树
    cout<<endl;
    cout<<"二叉树的先序遍历结果："<<endl;
    preorder(mytree);//先序遍历二叉树
    cout<<endl;
    cout<<"二叉树的中序遍历结果："<<endl;
    inorder(mytree);//中序遍历二叉树
    cout<<endl;
    cout<<"二叉树的后序遍历结果："<<endl;
    posorder(mytree);//后序遍历二叉树
    cout<<endl;
    cout<<"二叉树的层次遍历结果："<<endl;
    Leveltraverse(mytree);//层次遍历二叉树
    return 0;
}

二叉树创建

补空法是指如果左子树或者右子树为空时，则用特殊符号补空，如“#”。然后按照先序遍历的顺利，得到先序遍历序列，根据该序列递归创建二叉树。

算法步骤：

  1. 输入补空后的二叉树先序遍历序列。
  2. 如果ch==“#”，T=NULL；否则创建一个新结点T，令T->data=ch；递归创建T的左子树；递归创建T的右子树。

二叉树还原

注意：只知道先序和后序序列，是没办法还原一个二叉树的。

例如：已知一棵二叉树的先序序列ABDECFG和中序序列DBEAFGC，画出这棵二叉树。

算法步骤：

  1. 先序序列第一个字符为根。
  2. 在中序序列中，以根为中心划分左右子树。
  3. 还原左右子树。

image

例如：已知一棵二叉树的后序序列为DEBGFCA和中序序列DBEAFGC，画出这棵二叉树。答案也是上图。

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
using namespace std;
typedef struct node
{
    char data;
    struct node *lchild,*rchild;
}BiTNode,*BiTree;

BiTree pre_mid_createBiTree(char *pre,char *mid,int len) //前序中序还原建立二叉树
{
    if(len==0)
        return NULL;
    char ch=pre[0];  //找到先序中的第一个结点
    int index=0;
    while(mid[index]!=ch)//在中序中找到的根结点的左边为该结点的左子树，右边为右子树
    {
        index++;
    }
    BiTree T=new BiTNode;//创建根结点
    T->data=ch;
    T->lchild=pre_mid_createBiTree(pre+1,mid,index);//建立左子树
    T->rchild=pre_mid_createBiTree(pre+index+1,mid+index+1,len-index-1);//建立右子树
    return T;
}

BiTree pro_mid_createBiTree(char *last,char *mid,int len)//后序中序还原建立二叉树
{
    if(len==0)
       return NULL;
    char ch=last[len-1]; //取得后序遍历顺序中最后一个结点
    int index=0;//在中序序列中找根结点，并用index记录长度
    while(mid[index]!=ch)//在中序中找到根结点，左边为该结点的左子树，右边为右子树
       index++;
    BiTree T=new BiTNode;//创建根结点
    T->data=ch;
    T->lchild=pro_mid_createBiTree(last,mid,index);//建立左子树
    T->rchild=pro_mid_createBiTree(last+index,mid+index+1,len-index-1);//建立右子树
    return T;
}

void pre_order(BiTree T)//前序递归遍历二叉树
{
    if(T)
    {
        cout<<T->data;
        pre_order(T->lchild);
        pre_order(T->rchild);
    }
}

void pro_order(BiTree T)//后序递归遍历二叉树
{
    if(T)
    {
        pro_order(T->lchild);
        pro_order(T->rchild);
        cout<<T->data;
    }
}
int main()
{
    BiTree T;
    int n;
    char pre[100],mid[100],last[100];
    cout<<"1. 前序中序还原二叉树\n";
	cout<<"2. 后序中序还原二叉树\n";
	cout<<"0. 退出\n";
	int choose=-1;
	while(choose!=0)
	{
	    cout<<"请选择:";
		cin>>choose;

		switch (choose)
		{
		    case 1://前序中序还原二叉树
		        cout<<"请输入结点的个数:"<<endl;
		        cin>>n;
		        cout<<"请输入前序序列:"<<endl;
		        for(int i=0;i<n;i++)
                    cin>>pre[i];
                cout<<"请输入中序序列:"<<endl;
                for(int i=0;i<n;i++)
                    cin>>mid[i];
                T=pre_mid_createBiTree(pre,mid,n);
                cout<<endl;
                cout<<"二叉树还原成功，输出其后序序列:"<<endl;
                pro_order(T);
                cout<<endl<<endl;
                break;
            case 2://后序中序还原二叉树
                cout<<"请输入结点的个数:"<<endl;
		        cin>>n;
                cout<<"请输入后序序列:"<<endl;
                for(int i=0 ;i<n;i++)
                    cin>>last[i];
                cout<<"请输入中序序列:"<<endl;
                for(int i=0 ;i<n;i++)
                    cin>>mid[i];
                T=pro_mid_createBiTree(last,mid,n);
                cout<<endl;
                cout<<"二叉树还原成功，输出其先序序列:"<<endl;
                pre_order(T);
                cout<<endl<<endl;
                break;
		}
	}
    return 0;
}

求叶子和结点数：

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
using namespace std;

typedef struct Bnode	/*定义二叉树存储结构*/
{ char data;
  struct Bnode *lchild,*rchild;
}Bnode,*Btree;

void Createtree(Btree &T)	/*创建二叉树函数*/
{
    //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
	char ch;
	cin >> ch;
	if(ch=='#')
        T=NULL;			//递归结束，建空树
	else{
		T=new Bnode;
		T->data=ch;					//生成根结点
		Createtree(T->lchild);	//递归创建左子树
		Createtree(T->rchild);	//递归创建右子树
	}
}

int LeafCount(Btree T)//求二叉树的叶子数
{
    if(T==NULL)//如果为空树，深度为0
        return 0;
    else
        if(T->lchild==NULL&&T->rchild==NULL)//左右子树均为空，则叶子数为1
           return 1;
        else
           return LeafCount(T->lchild)+LeafCount(T->rchild);//递归计算左子树和右子树的叶子数之和
}

int NodeCount(Btree T)//求二叉树的结点数
{
    if(T==NULL)//如果为空树，深度为0
        return 0;
    else
        return NodeCount(T->lchild)+NodeCount(T->rchild)+1;//递归计算左子树和右子树的结点数之和加1
}

int Depth(Btree T)//求二叉树的深度
{
    int m,n;
    if(T==NULL)//如果为空树，深度为0
        return 0;
    else
    {
       m=Depth(T->lchild);//递归计算左子树深度
       n=Depth(T->rchild);//递归计算左子树深度
       if(m>n)
          return m+1;//返回左右子树最大值加1
       else
          return n+1;
    }
}

int main()
{
    Btree mytree;
    cout<<"按先序次序输入二叉树中结点的值（孩子为空时输入#），创建一棵二叉树"<<endl;
    //ABD##E##CF#G###
    Createtree(mytree);//创建二叉树
    cout<<endl;
    cout<<"二叉树的结点数为："<<NodeCount(mytree)<<endl;
    cout<<"二叉树的叶子数为："<<LeafCount(mytree)<<endl;
    return 0;
}
赏

谢谢你给的糖果

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

<br>搭建本站的初衷是为了记录生活和工作的点滴，在这个浮躁的社会，希望我们少一些功利主义的追求，多一些不为什么的坚持。<br><br>在北京混日子的程序员一枚，时而无聊时而有趣，时而开心时而抑郁。喜欢旅游和美食。<br><br>喜欢的东西很贵<br>想去的地方很远<br>深爱的人很优秀