数据结构--二叉树

发表于2022-10-13更新于2022-11-02

二叉树

什么是树

  • 树是有n(n≥0)个结点的有限集合。
  • 如果 n=0，称为空树。
  • 如果 n>0,称为非空树,对于非空树,有且仅有一个特 定的称为根(Root)的节点(无直接前驱)
  • 如果 n>1，则除根以外的其它结点划分为 m (m>0)个 互不相交的有限集 T1, T2 ,…, Tm，其中每个集合 本身又是一棵树，并且称为根的子树(SubTree)。
  • 每个结点都有唯一的直接前驱，但可能有多个后继

二叉树的种类

满二叉树

如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

这棵二叉树为满二叉树，也可以说深度为k，有2^k-1个节点的二叉树。

完全二叉树

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

二叉搜索树

二叉搜索树是一个有序树。

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉排序树

平衡二叉搜索树

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉树的存储

二叉树的存储分链式存储和线性存储

线性存储利用数组

对于下标为i的节点来说，左节点的下标为i*1+1，右节点的下标为i*2+2

链式存储利用链表

1
2
3
4
5
6
struct Node{
    int delta;
	Node* r;
	Node* l;
    Node(int x) : delta(x), r(nullptr), l(nullptr) {}
}

建立二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Create(Node * &T)
{
	char ch;
	cin >> ch;
	if(data == '0' ){
		T == NULL;
	}
	else{
		T = new Node *;
		T->data = ch;
		Create(T->left);
		Create(T->right);
	}
}

二叉树的遍历

深度优先搜索

递归

深度优先搜索一般使用递归实现

1
2
3
4
5
6
7
8
9
10
11
12
void travel(Node * root, vector<int> vec){
    if(root == nullptr) return ;
    //前序遍历
    vec.push(root->delta);
    travel(root->l, vec);
    //中序遍历
    //vec.push(root->delta);
    travel(root->r, vec);
    //后序遍历
    //vec.push(root->delta);
    return ;
}
迭代实现

迭代实现二叉树的话利用到栈这个数据，本质还是在模拟递归的执行

前序/后序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> preorderTraversal(TreeNode* root) {
        vector<int> rec;
        stack<TreeNode*> st;
        if(root == nullptr) return rec;
        st.push(root);
        while(!st.empty()){
            TreeNode* tmp = st.top();
            st.pop();
            rec.push_back(tmp->val);
            //前序遍历
            if(tmp->right) st.push(tmp->right);
            if(tmp->left) st.push(tmp->left);
            //后序遍历
            if(tmp->left) st.push(tmp->left)
            if(tmp->right) st.push(tmp->right); 
        }
    	//后序遍历
    	reverse(rec.begin(), rec.end());
        return rec;
    }

中序遍历：

中序遍历除了栈之外还得额外引入一个指针来帮助找到二叉树的底层，在用栈来处理节点上的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> rec;
    stack<TreeNode*> st;
    TreeNode* tmp = root;
    while(tmp != nullptr || !st.empty()){
        if(tmp != nullptr){
            st.push(tmp);
            tmp = tmp->left;
        }
        else{
            tmp = st.top();
            rec.push_back(tmp->val);
            st.pop();
            tmp = tmp->right;
        }
    }
    return rec;
}

统一迭代法：

迭代法的问题是，栈这种数据结构无法解决访问节点和遍历节点不一致的情况，于是可以通过加入一个空指针来进行标记。

在每个处理的节点后面加入空结点，访问节点则之间入栈。使得处理节点要当空节点出栈后才会出栈。

广度优先搜索

广度优先搜索在二叉树中又叫做层序搜索，自顶向下，自左到右一层一层遍历

利用队列先进先出的特点，可以轻松的实现层序搜索

非递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> rec;
    queue<TreeNode*> que;
    if(root != nullptr) que.push(root);
    while(!que.empty()){
        vector<int> tmp;
        int size = que.size();
        for(int i = 0; i < size; i++){
            TreeNode* x = que.front();
            que.pop();
            tmp.push_back(x->val);
            if(x->left) que.push(x->left);
            if(x->right) que.push(x->right);
        }
        rec.push_back(tmp);
    } 
    return rec;
}
递归
1