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