二叉树的遍历

二叉树的遍历

先序遍历

先遇见哪个就先输出哪个

:red_circle:对二叉树结点从1开始连续编号:树中任一结点,其编号等于的左子树上的最小编号减一,而的右子树的最小编号等于v的左子树上的最大编号加一,说明该二叉树是按照先序遍历

中序遍历

找不到左子树或者从左子树回来,就输出该节点或者按压,将二维的树向下按压

后序遍历

:red_circle:最后一次遇见才想着去输出,(为了孩子 奉献自己)适合链表的删除(),因为都已经无依无靠了,删除也不影响其他

:red_circle:对二叉树的结点从1开始连续编号,要求每个结点的编号大于其左右孩子的编号,同一结点的左右孩子中,其左孩子编号小于其右孩子编号,可以用 后序遍历来实现编号()

层次遍历

利用队列来进行层次遍历

总结遍历的规律

  1. 在二叉树的前序,中序,后序序列中,所有叶子节点的先后顺序是完全相同的()

获取树高

1
2
3
4
5
6
7
// 如果相要获取树高的话 也可使用递归完成
// 有种动态规划的感觉 实际就是调用子状态
int getHight(TreeNode *root)
{
    if(root == NULL) return 0;
    return max(getHight(root->left),getHight(root->right)) + 1;
}

三种遍历以及非递归遍历同时前序加中序构建二叉树

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include <bits/stdc++.h>
using namespace std;

//根据前序和中序构建出后序的遍历
//构建出来树

struct TreeNode{
    char val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(char x): val(x),left(NULL),right(NULL){}
};

// 递归构建 给定一个根节点和前序中序序列
// 递归关注自身 不需要想这么多
// 根据前序和中序返回一个当前根节点
TreeNode* tree(string pre,string mid)
{
    // 里面还有元素
    if(mid.size()!=0)
    {
        char fot = pre[0];//代表分割点 第一个元素
        TreeNode* root = new TreeNode(fot);
        // cout << fot;
        // 当前根节点的位置
        int t = mid.find(fot);
        // cout << "分割结点" << fot << "\n";
        // cout << "左子树结点" << pre.substr(1,t) << " " << mid.substr(0,t)<<"\n";
        // cout << "右子树结点" << pre.substr(1+t) <<" " << mid.substr(1+t) <<"\n";
        
        root->left = tree(pre.substr(1,t),mid.substr(0,t));
        root->right = tree(pre.substr(1+t),mid.substr(1+t));

        return root;
    }
    
    return NULL;
}

// 三种递归实现法 注意复制的时候 各自递归的是自己的方法
void posOrder(TreeNode *root)
{
    if(root==NULL)return;
   
    posOrder(root -> left);
    posOrder(root -> right);
    cout << root -> val;
}

void preOrder(TreeNode *root)
{
    if(root==NULL)return;
    cout << root -> val;
    preOrder(root -> left);
    preOrder(root -> right);
    
}

void inOrder(TreeNode *root)
{
    if(root==NULL)return;
    inOrder(root -> left);
    cout << root -> val;
    inOrder(root -> right);
}

// 实现前序非递归实现
/*
前序的顺序是NLR 
根节点优先 其次是左节点和右节点
*/
void preOrder2(TreeNode *root)
{
    // 存放递归结点的栈
    string ans = "";// 结果字符串
    stack <TreeNode*> st;
    st.push(root);// 放入根节点
    while(!st.empty())
    {
        TreeNode* top = st.top();
        st.pop();// 出栈的同时 访问
        ans += top->val;
        // 先放右边 便于出栈先出左边的
        if(top->right!=NULL) st.push(top->right);
        if(top->left!=NULL) st.push(top->left);
    }
    
    cout<< ans <<"\n";
}

/*
利用非递归实现中序遍历
中序思想是LNR
根结点的访问在左子树之后 右子树之前
所以如果有左子树就一路走到底 走到黑
走到最后之后 就访问该结点 同时之后把右子树放进栈中
同时对右子树的规则也要将其左子树全部放进去
递归这一类的思想就有一种简洁粗暴美
cur作为当前结点当左子树访问完毕 直接输出该结点值
然后只需要将其右节点当作下一个的根节点的处理就好
也就是直接将cur设置为cur->right 也无需判断他是否存在右子树
而且在第二个while循环里面要记得当前的那个结点也需要加入
*/
void inOrder2(TreeNode *root)
{
    string ans = "";
    stack <TreeNode*> st;
    TreeNode* cur = root;// 表示当前结点
    while(cur || !st.empty())
    {
        // 先对当前结点的左子树全部放进去
        while(cur)
        {
            st.push(cur);
            cur = cur -> left;
        }
        // 当前cur无左子树了 该输出了
        cur = st.top();
        st.pop();
        ans += cur->val;
        cur = cur -> right;

    }
    cout << ans << "\n";
    
}

//非递归实现后续遍历
/*
后续遍历的思想是 LRN 
访问根节点之前 左右子树均已经访问完毕 这是核心思想
两种输出可能 一是无左无右 二是左右遍历完成
有左放左 无右或者右归输出当前结点
*/
void posOrder2(TreeNode *root)
{
    string ans = "";
    stack <TreeNode *> st;
    TreeNode *cur = root;
    TreeNode *pre = NULL;//代表上一个访问的 判断右子树回归的
    while(cur || !st.empty())
    {
        // 全部左子树放进去
        while(cur)
        {
            st.push(cur);
            cur = cur -> left;
        }
        
        cur = st.top();
        // 是上一个结点返回的
        // 以该结点的树右子树为空 输出
        if(cur->right == NULL || cur->right == pre)
        {
            st.pop();
            ans += cur->val;
            pre = cur;// 代表刚输出的是次结点
            cur = NULL;
        }else{
            cur = cur -> right;
        }
        
        
    }
    cout << ans <<"\n";
}

int main()
{
    
    string pre,mid;
    while(cin >> pre >> mid)
    {
        // cout << pre<<" " << mid<<"\n";
        TreeNode * root = tree(pre,mid);
        cout <<"前序:\n";
        preOrder2(root);
        preOrder(root);
        
        cout<<"\n中序:\n";
        inOrder2(root);
        inOrder(root);
        cout<<"\n后序:\n";
        posOrder2(root);
        posOrder(root);
        cout <<"\n";
    }
    return 0;
}

层序遍历普遍实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
实现层次遍历 队列BFS思想 每次访问结点的同时 加入左右孩子
*/
void levelOrder(TreeNode *root)
{
    queue<TreeNode*> q;
    string ans = "";
    q.push(root);
    while(!q.empty())
    {
        TreeNode *top = q.front();
        q.pop();
        ans += top->val;
        if(top->left != NULL) q.push(top->left);
        if(top->right != NULL) q.push (top->right);
    }
    cout << ans << "\n";
}

层序遍历的应用

实现树的高度 每层的具体结点 最宽的一层

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
/*
可以利用层次遍历来实现
树高 层宽 每层结点的个数
还可以用来判断是否为完全二叉树
规则为叶子节点后续都为叶子节点
假如左子树为空 右子树必为空
*/
void levelOrder2(TreeNode *root)
{
    queue<TreeNode*> q;
    map<int,string> ms;// 表示该层数详细的序列
    
    q.push(root);
    int height = 1;
    while(!q.empty())
    {
        
        int limit = q.size();
        // 这表示当前层次的节点数 
        // 需要全部释放出去 一层一层的pop
        string temp = "";
        while(limit--)
        {
            TreeNode *top = q.front();
            temp += top->val;
            q.pop();
            if(top->left != NULL) q.push(top->left);
            if(top->right != NULL) q.push (top->right);
        }
        ms[height++] = temp;
        // 里面剩余的元素都是新的下一层
    }
    printf("层数:%d\n",ms.size());
    // cout << ans << "\n";
    for(auto i = ms.begin();i!=ms.end();i++)
    {
       cout << "第"<< i->first << "层:" << i->second <<"\n";
    }
}



后序遍历的应用

实现祖先序列

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
//  这个代码问题还是很大的 这实际上是无法找到所有的祖先的
// 寻找给定结点所有祖先 递归实现
int f = 0;
// 这里需要将f设置为全局变量 要不然递归return 传不了参数
// 在后序遍历遇到查询结点的时候 接下来输出的所有内容都是其祖先
string parent = "";
void findParent(TreeNode* root, char x)
{
    if(root==NULL) return;

    findParent(root->left,x);
    findParent(root->right,x);
    // cout << root->val <<"后续\n";
    // 这里应该是访问的操作 如果找到这个元素 就不需要进行递归了
    if(root->val == x)
    {
        f = 1;// 状态置1 不需要进行递归
        cout << "已经找到结点";
    }
    if(f==1)
    {
        // cout <<" "<< root->val;
        parent += root->val;
    }
}

上面是用递归来实现的,问题还是蛮大的,关键在于假如在后序的位置找到了目标结点,应该做的操作是终止后面所有递归,并且将剩余的元素输出,而且将f设置为全局变量,和parent数组作为全局的,每次使用都需要初始化,也不太方便,

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
//  这个代码问题还是很大的 这实际上是无法找到所有的祖先的
// 寻找给定结点所有祖先 递归实现
int f = 0;
// 这里需要将f设置为全局变量 要不然递归return 传不了参数
// 在后序遍历遇到查询结点的时候 接下来输出的所有内容都是其祖先
string parent = "";
void findParent(TreeNode* root, char x)
{
    if(root==NULL) return;
    // 为1的话 没必要进行新的递归了
    if(f==1) return;
    
    findParent(root->left,x);
    findParent(root->right,x);
    // cout << root->val <<"后续\n";
    // 这里应该是访问的操作 如果找到这个元素 就不需要进行递归了
    if(root->val == x)
    {
        f = 1;// 状态置1 不需要进行递归
        cout << "已经找到结点";
    }
    if(f==1)
    {
        // cout <<" "<< root->val;
        parent += root->val;
    }
}

在11行加入,假如遇到不需要更新递归的情况就直接return掉,也就是记录仍在递归栈中的数据就好,这样修改完就是正确的了.

实现寻找公共祖先

根据上述的思想,实现的寻找公共祖先序列,然后进行比较,注意上面得到的序列是从孩子指向祖先的,所以比较需要倒序.但是也不简洁,需要频繁初始化.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/*
找到xy的公共祖先 先利用上面的获取各自的所有祖先序列 然后进行比较
*/
char findCommon(TreeNode* root, char x,char y)
{
    parent.clear();
    f = 0;
    findParent(root,x);
    string a = parent;
    f = 0;
    parent.clear();
    findParent(root,y);
    string b = parent;
    cout <<"各自祖先序列"<< a <<"\n" << b <<"\n";
    for(int i = 0;i<a.size() && i<b.size();i++)
    {
        // 第一个相同的就是公共祖先
        if(a[i]==b[i]) return a[i];
        
    }
    cout << "不存在公共祖先\n";
    return NULL;
}

打印路径

专业课 > 数据结构 > 树与二叉树
#数据结构 #树 #二叉树 #二叉树的遍历
二叉树的遍历
https://rain_dew.gitee.io/2024/04/16/专业课/数据结构/5.树与二叉树/5.3二叉树的遍历/
Author
Wang yulu
Posted on
April 16, 2024
Licensed under