[Data structure binary tree] Pre-order level establishment, recursive non-recursive traversal, level-order traversal, tree height, mirror, symmetry, subtree, merge, target path, weighted path sum, etc.

Binary tree

Article directory

• Binary tree
• • 1. Creation of binary tree (recursive creation, structure pointer form)
  • • 1.1. Preorder establishment
    • 1.2. Establishment of layer sequence
  • 2. Recursive traversal (structure pointer)
  • • 2.1. Preorder traversal
    • 2.2. In-order traversal
    • 2.3. Postorder traversal
  • 3. Non-recursive traversal (structure pointer)
  • • 3.1. Level traversal
    • 3.2. Postorder traversal (non-recursive)
  • 4. Find the height of the tree
  • 5. Mid- and post-order traversal construction
  • 6. Binary tree mirror flipping
  • 7. Symmetric binary tree
  • 8. Output all target paths
  • 9. Determine whether it is a subtree
  • 10. Merge binary trees
  • 11. Weighted path sum

Preface: This blog requires you to have a general understanding of binary trees, and a certain understanding of recursion, and understand what the first-order, middle-order, and last-order levels are, etc., because I will not explain these concepts in this blog. I will only cut out the better and more concise code blocks that I have written, and will not explain it too much, so if you choose this blog, you should be prepared to understand it thoroughly!

1. Creation of binary tree (recursive creation, structure pointer form)

First let’s give the structure:

struct Node
{<!-- -->
char data;
Node* leftchild = nullptr;
Node* rightchild = nullptr;
};

1.1. Pre-order creation

#include<iostream>
#include<string>
using namespace std;
struct Node
{<!-- -->
char a;
Node* leftchild = nullptr;
Node* rightchild = nullptr;
};
class BuildTree
{<!-- -->
public:
Node*gen;
int i = 0;//Traverse arr
BuildTree() {<!-- --> gen = nullptr; }
void setTree(string arr)
{<!-- -->
gen = new Node;
CreateBiTree(gen, arr);
return;
}
    // core code
void CreateBiTree(Node* & amp; root, string strTree) //Construct binary tree through pre-order traversal
{<!-- -->
char ch;
ch = strTree[i + + ];
if (ch == '#')
{<!-- -->
root = NULL;
}
else
{<!-- -->
root = new Node();
root->a = ch;
CreateBiTree(root->leftchild, strTree);
CreateBiTree(root->rightchild, strTree);
}
return;
}
};
int main()
{<!-- -->
int n;
cin >> n;
while (n--)
{<!-- -->
BuildTree* bt = new BuildTree;
string arr;
cin >> arr;
bt->setTree(arr);
delete bt;
}
}
</code><img class="look-more-preCode contentImg-no-view" src="//i2.wp.com/csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreBlack.png" alt ="" title="">

1.2. Creation of layer sequence

#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct Node {<!-- -->
    char data;
    Node* leftchild;
    Node* rightchild;
};

void pre_view(Node* root)
{<!-- -->
    if (root != nullptr)
    {<!-- -->
        cout << root->data << ' ';
        pre_view(root->leftchild);
        pre_view(root->rightchild);
    }
    return;
}

// Create layer sequence
void CreateBiTree(Node* & amp; root, string strTree) {<!-- -->
    if (strTree.empty()) {<!-- -->
        root = nullptr;
        return;
    }

    queue<Node*> nodeQueue;
    int i = 0;
    root = new Node();
    root->data = strTree[i + + ];
    nodeQueue.push(root);

    while (!nodeQueue.empty()) {<!-- -->
        Node* current = nodeQueue.front();
        nodeQueue.pop();

        if (i < strTree.length() & amp; & amp; strTree[i] != '#') {<!-- -->
            current->leftchild = new Node();
            current->leftchild->data = strTree[i];
            nodeQueue.push(current->leftchild);
        }
        i + + ;

        if (i < strTree.length() & amp; & amp; strTree[i] != '#') {<!-- -->
            current->rightchild = new Node();
            current->rightchild->data = strTree[i];
            nodeQueue.push(current->rightchild);
        }
        i + + ;
    }
}

int main() {<!-- -->
    string strTree = "122#3#3";
    Node* root = nullptr;
    CreateBiTree(root, strTree);
    //Pre-order traversal to view results
    pre_view(root);
    return 0;
}
</code><img class="look-more-preCode contentImg-no-view" src="//i2.wp.com/csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreBlack.png" alt ="" title="">

2. Recursive traversal (structure pointer)

2.1. Preorder traversal

void pre_send(Node* root)
{<!-- -->
    if (root != NULL)
    {<!-- -->
        cout << (root->data);
        pre_send(root->leftchild);
        pre_send(root->rightchild);
    }
    return;
}

2.2. In-order traversal

void in_sned(Node* root)
{<!-- -->
    if (root != NULL)
    {<!-- -->
        in_sned(root->leftchild);
        cout << (root->data);
        in_sned(root->rightchild);
    }
    return;
}

2.3. Postorder traversal

void post_send(Node* root)
{<!-- -->
    if (root != NULL)
    {<!-- -->
        post_send(root->leftchild);
        post_send(root->rightchild);
        cout << (root->data);
    }
    return;
}

3. Non-recursive traversal (structure pointer)

First give the structure:

struct Node
{<!-- -->
    int a;
    Node* Leftchild = nullptr;
    Node* Rightchild = nullptr;
}

3.1. Level traversal

void levelorder(Node* gen)
{<!-- -->
queue<Node*>q;
q.push(gen);
while (!q.empty())
{<!-- -->
Node* now = q.front();
q.pop();
if (now == nullptr)
continue;
cout << now->a;
if (now->Leftchild != nullptr)q.push(now->Leftchild);
if (now->Rightchild != nullptr)q.push(now->Rightchild);
}
}

3.2. Postorder traversal (non-recursive)

void postRead(Node* gen)
{<!-- -->
stack<Node*>s;
Node* root = gen, * check = nullptr;
while (root != nullptr || !s.empty())
{<!-- -->
if (root != nullptr)//Go all the way to the left
{<!-- -->
s.push(root);
root = root->Leftchild;
}
else
{<!-- -->
root = s.top();
//The right node exists and is not accessed
if (root->Rightchild != nullptr & amp; & amp; root->Rightchild != check)
{<!-- -->
root = root->Rightchild;
s.push(root);
root = root->Leftchild;
}
else
{<!-- -->
s.pop();
cout << root->a;
check = root;
root = nullptr;
}
}
}
}
</code><img class="look-more-preCode contentImg-no-view" src="//i2.wp.com/csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreBlack.png" alt ="" title="">

4. Find the height of the tree

int getHeight(Node* root)
{<!-- -->
if (root == nullptr)
return 0;
int leftdeep = getHeight(root->Leftchild);
int rightdeep = getHeight(root->Rightchild);
int deep = 1 + (leftdeep > rightdeep ? leftdeep : rightdeep);
return deep;
}

5. Mid-post order traversal construction

I saw this part when I was doing the questions. I feel that after understanding this part, I will have a better understanding of the front, middle and back order. This question is: know the rules of the back order! The name of the topic is: Construction of mid- and post-order traversal of binary trees and finding leaves. You can search for it yourself.

#include<iostream>
#include<cstring>
using namespace std;
classTree
{<!-- -->
public:
int* mid;
int* last;
int min = 10000000;
Tree(int t)
{<!-- -->
mid = new int[t + 5];
last = new int[t + 5];
for (int i = 0; i < t; i + + )
{<!-- -->
cin >> mid[i];
}
for (int i = 0; i < t; i + + )
{<!-- -->
cin >> last[i];
}
}

~Tree()
{<!-- -->
delete mid, last;
}
int get_min()
{<!-- -->
return min;
}
void BuildTree(int mid_l, int mid_r, int last_l, int last_r)
{<!-- -->
if (mid_l == mid_r)
{<!-- -->
if (mid[mid_l] <= min)
min = mid[mid_l];
return;
}
for (int i = mid_l; i <= mid_r; i + + )
{<!-- -->
if (mid[i] == last[last_r])
{<!-- -->
BuildTree(mid_l, i - 1, last_l, last_l + i - mid_l - 1);
BuildTree(i + 1, mid_r, last_l + i - mid_l, last_r - 1);
}
}
}
};
int main()
{<!-- -->
int n;
cin >> n;
while (n--)
{<!-- -->
int t;
cin >> t;
Tree* tree = new Tree(t);
tree->BuildTree(0, t - 1, 0, t - 1);
cout << tree->get_min() << endl;
delete tree;
}
return 0;
}

</code><img class="look-more-preCode contentImg-no-view" src="//i2.wp.com/csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreBlack.png" alt ="" title="">

6. Binary tree mirror flip

void Mirror_inversion(Node* p)
{<!-- -->
if (p != NULL)
{<!-- -->
Mirror_inversion(p->Leftchild);
Mirror_inversion(p->Rightchild);
swap(p->Leftchild, p->Rightchild);
}
}

7. Symmetric binary tree

bool judge(Node* root_1, Node* root_2)
{<!-- -->
if (root_1 == nullptr & amp; & amp; root_2 == nullptr)
{<!-- -->
return true;
}
else if (root_1 == nullptr || root_2 == nullptr)
{<!-- -->
return false;
}
else if (root_1->data != root_2->data)
{<!-- -->
return false;
}
return judge(root_1->leftchild, root_2->rightchild) & amp; & amp; judge(root_1->rightchild, root_2->leftchild);
}

bool isSymmetric(Node* root)
{<!-- -->
return judge(root->leftchild, root->rightchild);
}
</code><img class="look-more-preCode contentImg-no-view" src="//i2.wp.com/csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreBlack.png" alt ="" title="">

8. Output all target paths

void DFS_target(Node* node, int targetSum, vector<int> & amp; path, vector<vector<int>> & amp; result) {<!-- -->
if (node == nullptr) {<!-- -->
return;
}

path.push_back(node->data);

if (node->leftchild == nullptr & amp; & amp; node->rightchild == nullptr) {<!-- -->
if (targetSum == node->data) {<!-- -->
result.push_back(path);
}
}
else {<!-- -->
DFS_target(node->leftchild, targetSum - node->data, path, result);
DFS_target(node->rightchild, targetSum - node->data, path, result);
}

path.pop_back();
return;
}
</code><img class="look-more-preCode contentImg-no-view" src="//i2.wp.com/csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreBlack.png" alt ="" title="">

9. Determine whether it is a subtree

bool isSameTree(Node* t1, Node* t2) {<!-- -->
// Taking into account the left and right nodes of the subsequent cotyledon node, True will be returned if both are empty.
if (!t1 & amp; & amp; !t2) {<!-- -->
return true;
}
// If one node has left and right nodes, but the other node does not, it will return false. If both nodes are not entered, it will return True.
if (!t1 || !t2) {<!-- -->
return false;
}
return (t1->data == t2->data) & amp; & amp; isSameTree(t1->leftchild, t2->leftchild) & amp; & amp; isSameTree(t1->rightchild, t2->rightchild);
}

// Determine whether tree1 contains a subtree of tree2
bool isSubtree(Node* tree1, Node* tree2) {<!-- -->
if (!tree1) {<!-- -->
return false;
}
//Start considering when tree1 is not empty
if (isSameTree(tree1, tree2)) {<!-- -->
return true;
}
// Consider each node downwards, and return True if one is consistent.
return isSubtree(tree1->leftchild, tree2) || isSubtree(tree1->rightchild, tree2);
}

</code><img class="look-more-preCode contentImg-no-view" src="//i2.wp.com/csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreBlack.png" alt ="" title="">

10. Merge binary trees

void addWith(Node* & amp; root_1, Node* root_2)
{<!-- -->
if (root_1 == nullptr & amp; & amp; root_2 != nullptr)
{<!-- -->
root_1 = new Node;
root_1->data = root_2->data;
root_1->leftchild = root_2->leftchild; // Handle left child
root_1->rightchild = root_2->rightchild; // Handle right child
return;
}
if (root_2 == nullptr)
{<!-- -->
return;
}

root_1->data + = root_2->data;

addWith(root_1->leftchild, root_2->leftchild);
addWith(root_1->rightchild, root_2->rightchild);
}
</code><img class="look-more-preCode contentImg-no-view" src="//i2.wp.com/csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreBlack.png" alt ="" title="">

11. Weighted path sum

void findDeepTree(Node* root, int* data, int dis)
{<!-- -->
if (root == nullptr || index == n)
{<!-- -->
return;
}
if (root->leftchild == nullptr & amp; & amp; root->rightchild == nullptr)
{<!-- -->
result = result + dis * data[index + + ];
return;
}

if (root->leftchild != nullptr)
findDeepTree(root->leftchild, data, dis + 1);
if (root->rightchild != nullptr)
findDeepTree(root->rightchild, data, dis + 1);
return;
}
</code><img class="look-more-preCode contentImg-no-view" src="//i2.wp.com/csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreBlack.png" alt ="" title="">