二叉树

Posted on | In
Words count in article: 2.2k | Reading time ≈ 9

二叉树

树的概念

树（Tree）是n（n≥0）个结点的有限集合，当n=0时，为空树；n>0时，为非空树。任意一棵非空树，满足：

1)有且仅有一个称之为根的结点；

2)除根结点以外的其余结点可分为m（m＞0）个互不相交的有限集$T_1,T_2,…T_m$, 其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

扇出：一个节点有多少个孩子

树的扇出：一棵树中扇出最大的节点

二叉树

二叉树（Binary Tree）是n（n≥0）个结点所构成的集合，它或为空树（n=0）；或为非空树。对于非空树T满足：

​ 1)有且仅有一个称为根的结点；

​ 2) 除根结点以外，其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身都是二叉树。

性质6：如果二叉树空格节点全部画出，那么对于二叉树来说，空格节点的个数始终比数值节点多1

满二叉树： 如果一棵二叉树的 深度为 k, 结点数 $2^{ k+1 }-1$, 每层结点数都最大 ，则此二叉树称作满二叉树。

完全二叉树：如果一棵二叉树至多只有最下面的两层结点度数可以小于2，其余各层结点度数都必须为2，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。即为，满二叉树去掉最下层最右边若干结点

完全二叉树孩子与父亲的关系:

结点i的

左子结点是$2i+1$

右子结点是$2i+2$

父结点是 $( i-1)/2 $

二叉树的存储

二叉树创建

二叉树的遍历

按照根的访问顺序不同，根在前面的称为先序遍历（DLR），根在中间称之为中序遍历（LDR），根在最后面称为后序遍历（LRD）

先序遍历

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

算法步骤:

如果二叉树为空，则空操作，否则

  1. 访问根节点
  2. 先序遍历左子树
  3. 先序遍历右子树

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

1
2
3
4
5
6
7
8
9
void preorder(Btree T)
{
	if(T)
	{
		cout<<T->data<<" ";
		preorder(T->lchild);
		preorder(T->rchild);
	}
}

比如说这棵树，先序遍历就是A-B-D-E-C-F-G

这棵树的先序遍历就是 A-B-C-D-E-F-G-H-J-I

中序遍历

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

算法步骤:

如果二叉树为空，则空操作，否则

  1. 中序遍历左子树
  2. 访问根节点
  3. 中序遍历右子树

中序遍历秘籍：中序遍历左子树，左子树为空或已全部遍历才可以访问根和中序遍历右子树

比如这棵树的中序遍历就是 DEBAFGC

比如这棵树的中序遍历就是 BCDAFEJHIG

后序遍历

后序遍历是指后序遍历左子树，再后序遍历右子树，最后访问根，即LRD

算法步骤:

如果二叉树为空，则空操作，否则

  1. 后序遍历左子树
  2. 后序遍历右子树
  3. 访问根节点

后序遍历秘籍：后序遍历左子树，后序遍历右子树，左子树，右子树为空或已经便利了才可以访问根

比如这棵树的后序遍历就是 DEBGFCA

比如这棵树的后序遍历就是DCBFJIHGEA

1
2
3
4
5
6
7
8
9
void pro_order(BiTree T)//后序递归遍历二叉树
{
    if(T)
    {
        pro_order(T->lchild);
        pro_order(T->rchild);
        cout<<T->data;
    }
}

二叉树的还原

我们要知道先序和后序是不可能创建或者还原一个二叉树的，所以我们要用先序序列、中序序列或者后序序列、中序序列画一棵二叉树

先序中序建立还原二叉树

算法步骤：

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

后序中序建立还原二叉树

算法步骤：

  1. 后序序列的最后一个字符为根
  2. 再中顺序序列中以根为中心划分左右子树
  3. 还原左右子树
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
#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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;
enum Error_code {success,fail};
vector<int> results;
template <class Entry>
struct Binary_node {
// data members:
    Entry data;
    Binary_node<Entry> *left; //指向左孩子的指针
    Binary_node<Entry> *right; //指向右孩子的指针
// constructors:
    Binary_node( ); //默认的不带参数的构造函数
    Binary_node(const Entry &x); //带有一个参数的构造函数
};
template <class Entry>
Binary_node<Entry> :: Binary_node(){
    left = NULL;
    right = NULL;
}

template <class Entry>
Binary_node<Entry> :: Binary_node(const Entry &x){
    data = x;
    left = NULL;
    right = NULL;
}
class BinaryTree
{
public:
    BinaryTree();
    void BuildTree_levelorder(Binary_node<char>*&node,string &s);
    bool is_Balanced(Binary_node<char>* node);
    int height(Binary_node<char>* node,bool &is_balance);
    Binary_node<char>* getParent(Binary_node<char>* node,char p,char q);

    Binary_node<char>*get_root()
    {
        return root;
    }
private:
    Binary_node<char>*root;
};

BinaryTree::BinaryTree() {
    root = new Binary_node<char>;
}

void BinaryTree::BuildTree_levelorder(Binary_node<char> *&root, string &s) {
    int index= 0;
    Binary_node<char>*tnode = NULL;
    queue<Binary_node<char>*>qTree;
    while(true)
    {
        if(index==s.size())break;
        if(index==0){
            root = new Binary_node<char>(s[index]);
            qTree.push(root);
            index++;
        }else{
            tnode = qTree.front();
            if(index==s.size())break;
            if(s[index]=='#')tnode->left = NULL;
            else{
                tnode->left = new Binary_node<char>(s[index]);
                qTree.push(tnode->left);
            }
            index++;
            if(index==s.size())break;
            if(s[index]=='#')tnode->right = NULL;
            else{
                tnode->right = new Binary_node<char>(s[index]);
                qTree.push(tnode->right);
            }
            index++;
            qTree.pop();
        }
    }
} 

int main()
{
 //...
}
-------------本文结束，感谢您的阅读-------------