C++简单又轻松建立链式二叉树流程

2024-04-02 19:04:59 898人浏览泡泡鱼

摘要

目录递归建立二叉树二叉树的结构体二叉树初始化先序遍历中序遍历后序遍历具体例题输入的格式全部源码总结递归建立二叉树二叉树的结构体 typedef struct node { int

递归建立二叉树

二叉树的结构体

typedef struct node
{
	int data;
	Node* lchild;
	Node* rchild;
}BiNode,*BiTree;

二叉树顾名思义最多只有两个子结点和一个数据域，既然是链式那么子结点定义为结点指针类型，数据域就可以根据需要设置了，可以是整型也可以是字符型。

二叉树初始化

BiTree createBiTree(BiTree &T)
{
	int d;
	cin >> d;
	if (d == 0)
	    T = NULL;
	else
	{
		T = (BiTree)malloc(sizeof(BiNode));
		T->data = d;
		T->lchild = createBiTree(T->lchild);
		T->rchild = createBiTree(T->rchild);
	}
	return T;
}

这个初始化函数的返回值为BiTree是一个结构体指针类型，用来返回初始化后的 T 二叉树；整型数据d是用来给二叉树的结点赋值的，当输入0的时候，该结点为空结点；当结点的数据域不为零，给该结点动态分配内存空间，并把d赋值给T->data；然后就是对左右子树的递归初始化了。

先序遍历

void PreOrder(BiTree T)//先序
{
	if (T)
	{
		cout << T->data<<" ";
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

先序遍历就是先访问根结点，在访问左子树，最后访问右子树，这里也写成递归形式；先访问当前结点的数据，再对左右子树进行访问。

中序遍历

void InOrder(BiTree T)//中序
{
	if (T != NULL)
	{
		PreOrder(T->lchild);
		cout << T->data << " ";
		PreOrder(T->rchild);
	}
}

中序遍历就是先访问左子树，在访问根结点，最后访问右子树，这里也写成递归形式；先访问当前结点的左子树的数据，再对该结点的数据进行访问，最后对右子树进行访问。

后序遍历

void PostOrder(BiTree T)//后序
{
	if (T)
	{
		PreOrder(T->lchild);
		PreOrder(T->rchild);
		cout << T->data << " ";
	}
}

后序遍历就是先访问左子树，在访问右子树，最后访问根结点，这里也写成递归形式；先访问当前结点的左子树的数据，再对右子树进行访问，最后访问根结点。

具体例题

参考上面的结构体，设计一个函数，要求能够同时求出二叉树中所有结点的的个数和二叉树中数据为奇数的和；

我的思考：该函数传入m和n两个全局变量，使用引用传递；当树不为空时，m++,n等于n加该结点数据域的值，接下来进行左右子树的递归调用：

void countT(BiTree T, int &m, int &n)
{
	if (T == NULL) return ;
	if (T->data % 2 != 0) n += T->data;
	m++;
	countT(T->lchild, m, n);
	countT(T->rchild, m, n);
}

从主函数中这样调用：

int m = 0,n = 0;

BiTree T=NULL;

countT(T, m, n);

最后输出m和n的值即可

效果截图：

注意输出的格式，必须是树的形式，下面解析一下

输入的格式

注意：输入的格式必须是树的先序遍历形式，因为在这个程序中初始化二叉树就是用的先序的方式

在这个二叉树先序输入数据：3 4 6 0 8 0 0 0 11 13 0 0 0

全部源码

粘贴到c++编译器就能使用

#include<iOStream>
using namespace std;
typedef struct Node
{
	int data;
	Node* lchild;
	Node* rchild;
}BiNode,*BiTree;
BiTree createBiTree(BiTree &T)
{
	int d;
	cin >> d;
	if (d == 0)
	    T = NULL;
	else
	{
		T = (BiTree)malloc(sizeof(BiNode));
		T->data = d;
		T->lchild = createBiTree(T->lchild);
		T->rchild = createBiTree(T->rchild);
	}
	return T;
}
void PreOrder(BiTree T)//先序
{
	if (T)
	{
		cout << T->data<<" ";
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}
void InOrder(BiTree T)//中序
{
	if (T)
	{
		InOrder(T->lchild);
		cout << T->data << " ";
		InOrder(T->rchild);
	}
}
void PostOrder(BiTree T)//后序
{
	if (T)
	{
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		cout << T->data << " ";
	}
}
void countT(BiTree T, int &m, int &n)
{
	if (T == NULL) return ;
	if (T->data % 2 != 0) n += T->data;
	m++;
	countT(T->lchild, m, n);
	countT(T->rchild, m, n);
}
int main()
{
	int m = 0,n = 0;
	BiTree T=NULL;
	cout << "输入先序遍历结点，建立二叉树" << endl;
	T = createBiTree(T);
	cout << "先序遍历结果" << endl;
	PreOrder(T);
	cout << endl;
	cout << "中序遍历结果" << endl;
	InOrder(T);
	cout << endl;
	cout << "后序遍历结果" << endl;
	PostOrder(T);
	cout << endl;
	countT(T, m, n);
	cout << "结点个数为：" << m << endl;
	cout << "数据为：" << n << endl;
}