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

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

递归建立二叉树

二叉树的结构体

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

总结

代码不是很长,每一个功能都对应一个函数,希望大家可以迅速掌握二叉链的基本使用,加油!

如果觉得写得好,记得点赞支持一下哦

到此这篇关于C++简单又轻松建立链式二叉树流程的文章就介绍到这了,更多相关C++链式二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现LeetCode(114.将二叉树展开成链表)

    [LeetCode] 114. Flatten Binary Tree to Linked List 将二叉树展开成链表 Given a binary tree, flatten it to a linked list in-place. For example, Given 1 / \ 2   5 / \   \ 3   4   6 The flattened tree should look like:    1 \ 2 \ 3 \ 4 \ 5 \ 6 click to show hints

  • 探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)

    如有不足之处,还望指正! 复制代码 代码如下: // BinaryTree.cpp : 定义控制台应用程序的入口点.//C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树#include "stdafx.h"#include<iostream>#include<string>#include <stack>using namespace std;template<class T>struct BiNode{ T data; 

  • C++将二叉树转为双向链表及判断两个链表是否相交

    把二叉查找树转变成排序的双向链表 例如: 转换成双向链表 4=6=8=10=12=14=16 struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; 首先阐述下二叉排序树: 它首先要是一棵二元树,在这基础上它或者是一棵空树:或者是具有下列性质的二元树: (1)若左子树不空

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

    目录 递归建立二叉树 二叉树的结构体 二叉树初始化 先序遍历 中序遍历 后序遍历 具体例题 输入的格式 全部源码 总结 递归建立二叉树 二叉树的结构体 typedef struct Node { int data; Node* lchild; Node* rchild; }BiNode,*BiTree; 二叉树顾名思义最多只有两个子结点和一个数据域,既然是链式那么子结点定义为结点指针类型,数据域就可以根据需要设置了,可以是整型也可以是字符型. 二叉树初始化 BiTree createBiTree

  • C语言详解实现链式二叉树的遍历与相关接口

    目录 前言 一.二叉树的链式结构 二.二叉树的遍历方式 1.1 遍历方式的规则 1.2 前序遍历 1.3 中序遍历 1.4 后序遍历 1.5 层序遍历 三.二叉树的相关接口实现 3.1 二叉树节点个数 3.2 二叉树叶子节点个数 3.3 二叉树第 k 层节点个数 3.4 二叉树的深度(高度) 3.5 二叉树查找值为 x 的节点 3.6 总结 & 注意 四.二叉树的创建和销毁 4.1 通过前序遍历的字符串来构建二叉树 4.2 二叉树销毁 4.3 判断二叉树是否是完全二叉树 前言 二叉树的顺序结构就

  • C++链式二叉树深入分析

    目录 二叉树的结构和概念 二叉树的操作 前序遍历 中序遍历和后序遍历 二叉树的节点个数 求二叉树叶子结点个数 求二叉树的深度 在二叉树查找为X的结点 之前我们的重点学习二叉树都是完全二叉树,接下来我们来说下普通二叉树,普通的二叉树如果我们使用数组存储,那么会浪费相当多的空间的,所以我们选择链表存储,我们先再来复习下二叉树的结构吧. 二叉树的结构和概念 二叉树概念是: 1. 空树 2. 非空:根节点,根节点的左子树.根节点的右子树组成的. 从概念中可以看出,二叉树定义是递归式的. 我们就手动创建一

  • C语言 链式二叉树结构详解原理

    目录 前言 二叉树节点声明 二叉树的遍历 构建二叉树 1.前序遍历 2.中序遍历 3.后序遍历 二叉树节点的个数 二叉树叶子节点的个数 二叉树第K层节点个数 二叉树的高度/深度 二叉树查找值为x的节点 整体代码 前言 二叉树不同于顺序表,一颗普通的二叉树是没有增删改查的意义.普通的二叉树用来存储数据是不方便的.但是二叉树的一些基本实现结构,例如前序遍历,中序遍历...等等都是对我们学习更深层次的二叉树打下夯实的基础. 二叉树节点声明 typedef char BTDataType; typede

  • C语言实现二叉树链式结构的示例详解

    目录 前言 1. 链式二叉树结构 2. 二叉树的遍历 2.1 前序遍历 2.2 中序遍历 2.3 后序遍历 2.4 层序遍历 3. 常见功能 3.1 二叉树结点个数 3.2 二叉树叶子结点个数 3.3 第K层结点的个数 3.4 二叉树的深度 3.5 判断是不是树是不是完全二叉树 3.6 在二叉树中查找值为x的结点 3.7 拿到每一层的数据 4. 二叉树的创建和销毁 4.1 二叉树的创建 4.2 二叉树的销毁 前言 前面我们已经对堆进行学习,堆就是一个顺序结构的二叉树,把数组看成二叉树,下面一起学

  • java链式创建json对象的实现

    目录 1.假设我们要创建一个json对象格式如下: 2.往常创建JSON语法: 3.解决方案——链式创建JSON: 4.实现多级JSON 5.YtJSONObject类源码 我们主要介绍一下:java中如何通过最简单的方式实现链式创建json对象,解决创建json代码臃肿的问题. 1.假设我们要创建一个json对象格式如下: { "code": 0, "msg": "SUCCESS" } 2.往常创建JSON语法: java中传统的创建json一

  • C语言 二叉树的链式存储实例

    二叉树的链式存储 实现二叉树的基本操作:建立.遍历.计算深度.结点数.叶子数等. 输入C,先序创建二叉树,#表示空节点: 输入H:计算二叉树的高度: 输入L:计算二叉树的叶子个数: 输入N:计算二叉树节点总个数: 输入1:先序遍历二叉树: 输入2:中序遍历二叉树: 输入3:后续遍历二叉树: 输入F:查找值=x的节点的个数: 输入P:以缩格文本形式输出所有节点. 很简单就不需要多解释了,代码贴上 #include <stdio.h> #include <stdlib.h> #incl

  • JAVA 实现二叉树(链式存储结构)

    二叉树的分类(按存储结构) 树的分类(按存储结构) 顺序存储(用数组表示(静态二叉树))   链式存储 一些特别的二叉根: 完全二叉树,平衡二叉树(AVL),线索二叉树,三叉的(带父亲的指针)    二叉搜索树或者叫二叉 查找树(BST)  所用二叉树如下图所示: 二叉树的Java实现(链式存储结构) class TreeNode { private int key = 0; private String data = null; private boolean isVisted = false

  • 原生js实现简单的链式操作

    在jQuery中,一个jq对象能一直连续调用各种方法,因为jQuery把这些方法挂载他自定义的一个对象中,但是使用原生的js获取的DOM对象,只能使用一次addEventLisenter方法添加事件,如果要接着添加事件,还得再调用addEventLisenter. var area = document.querySelector('.area'); area.addEventListener('mouseenter', function(){ console.log( 'mouse enter

随机推荐