二叉树--

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);
}