二叉树--

1.建立并遍历二叉树

遍历顺序：

先序遍历，中序遍历，后序遍历

先序：先根后左右

中序：先左然后根最后右

后序：先左右后根

例如：

先序：ABCDEFGH

中序：BDCEAFHG

后序：DECBHGFA

#include <iostream>

using namespace std;

struct binarynode
{
    char ch;
    binarynode* lson;
    binarynode* rson;
};

void recurion(binarynode* root) {
    if (root == NULL)
        return;

    cout << root->ch;
    recurion(root->lson);
    recurion(root->rson);
    return;
}

int main()
{

    //创建结点
    binarynode node1 = { 'A',NULL,NULL };
    binarynode node2 = { 'B',NULL,NULL };
    binarynode node3 = { 'C',NULL,NULL };
    binarynode node4 = { 'D',NULL,NULL };
    binarynode node5 = { 'E',NULL,NULL };
    binarynode node6 = { 'F',NULL,NULL };
    binarynode node7 = { 'G',NULL,NULL };
    binarynode node8 = { 'H',NULL,NULL };

    //设置结点关系
    node1.lson = &node2;
    node1.rson = &node6;
    node2.rson = &node3;
    node3.lson = &node4;
    node3.rson = &node5;
    node6.rson = &node7;
    node7.lson = &node8;

    //递归遍历二叉树
    recurion(&node1);
}

2.计算二叉树叶子结点

#include <iostream>

using namespace std;

struct binarynode
{
    char ch;
    binarynode* lson;
    binarynode* rson;
};

void get_leaf_num(binarynode* node,int & num)
{
    if (node == NULL)
        return;

    //只是在遍历基础上加上了对根结点的判断
    if (node->lson == NULL && node->rson == NULL)
        num++;

    get_leaf_num(node->lson,num);
    get_leaf_num(node->rson,num);
    return;
}

int main()
{

    //创建结点
    binarynode node1 = { 'A',NULL,NULL };
    binarynode node2 = { 'B',NULL,NULL };
    binarynode node3 = { 'C',NULL,NULL };
    binarynode node4 = { 'D',NULL,NULL };
    binarynode node5 = { 'E',NULL,NULL };
    binarynode node6 = { 'F',NULL,NULL };
    binarynode node7 = { 'G',NULL,NULL };
    binarynode node8 = { 'H',NULL,NULL };

    //设置结点关系
    node1.lson = &node2;
    node1.rson = &node6;
    node2.rson = &node3;
    node3.lson = &node4;
    node3.rson = &node5;
    node6.rson = &node7;
    node7.lson = &node8;

    int num = 0;
    get_leaf_num(&node1, num);
    cout << "该二叉树的叶子结点数为" << num << endl;
}

3.计算二叉树高度

#include <iostream>

using namespace std;

struct binarynode
{
    char ch;
    binarynode* lson;
    binarynode* rson;
};


// 从树叶一级一级加过来的，小化大，先看一小枝
int  get_tree_depth(binarynode* node)
{
    if (node == NULL)
        return 0;

    int depth = 0;
    int left_depth = get_tree_depth(node->lson);
    int right_depth = get_tree_depth(node->rson);
    
    depth = left_depth > right_depth ? left_depth + 1 : right_depth + 1;

    return depth;
}

int main()
{

    //创建结点
    binarynode node1 = { 'A',NULL,NULL };
    binarynode node2 = { 'B',NULL,NULL };
    binarynode node3 = { 'C',NULL,NULL };
    binarynode node4 = { 'D',NULL,NULL };
    binarynode node5 = { 'E',NULL,NULL };
    binarynode node6 = { 'F',NULL,NULL };
    binarynode node7 = { 'G',NULL,NULL };
    binarynode node8 = { 'H',NULL,NULL };

    //设置结点关系
    node1.lson = &node2;
    node1.rson = &node6;
    node2.rson = &node3;
    node3.lson = &node4;
    node3.rson = &node5;
    node6.rson = &node7;
    node7.lson = &node8;

    int depth = get_tree_depth(&node1);
    cout << "该二叉树的高度为" << depth << endl;
}

4.拷贝二叉树

#include <iostream>

using namespace std;

struct binarynode
{
    char ch;
    binarynode* lson;
    binarynode* rson;
};

binarynode* copy_tree(binarynode* node)
{
    if (node==NULL)
    {
        return NULL;
    }
    binarynode* left_son = copy_tree(node->lson);
    binarynode* right_son = copy_tree(node->rson);
    binarynode* newnode = new binarynode;
    *newnode = { node->ch,left_son,right_son };
    return newnode;
}

void recurion(binarynode* node)
{
    if (node==NULL)
    {
        return;
    }

    cout << node->ch;
    recurion(node->lson);
    recurion(node->rson);
    return;
}


int main()
{

    //创建结点
    binarynode node1 = { 'A',NULL,NULL };
    binarynode node2 = { 'B',NULL,NULL };
    binarynode node3 = { 'C',NULL,NULL };
    binarynode node4 = { 'D',NULL,NULL };
    binarynode node5 = { 'E',NULL,NULL };
    binarynode node6 = { 'F',NULL,NULL };
    binarynode node7 = { 'G',NULL,NULL };
    binarynode node8 = { 'H',NULL,NULL };

    //设置结点关系
    node1.lson = &node2;
    node1.rson = &node6;
    node2.rson = &node3;
    node3.lson = &node4;
    node3.rson = &node5;
    node6.rson = &node7;
    node7.lson = &node8;

    binarynode* copyment = copy_tree(&node1);
    recurion(copyment);
}