北京网站设计多少钱,php做商品网站,wordpress社区,做装修哪个网站推广好目录
树结构及其算法-用数组来实现二叉树
C代码 树结构及其算法-用数组来实现二叉树
使用有序的一维数组来表示二叉树#xff0c;首先可将此二叉树假想成一棵满二叉树#xff0c;而且第层具有个节点#xff0c;按序存放在一维数组中。首先来看看使用一维数组建立二叉树的…目录
树结构及其算法-用数组来实现二叉树
C代码 树结构及其算法-用数组来实现二叉树
使用有序的一维数组来表示二叉树首先可将此二叉树假想成一棵满二叉树而且第层具有个节点按序存放在一维数组中。首先来看看使用一维数组建立二叉树的表示方法以及数组索引值的设置。 可以看出此一维数组中的索引值有以下关系
左子树的索引值是父节点的索引值乘2。右子树的索引值是父节点的索引值乘2加1。
接着来看如何以一维数组建立二叉树的实例实际上就是建立一棵二叉查找树。这是一种很好的排序应用模式因为在建立二叉树的同时数据就经过了初步的比较判断并按照二叉树的建立规则来存放数据。二叉查找树具有以下特点
可以是空集合若不是空集合则节点上一定要有一个键值。每一个数根的值需大于左子树的值。每一个树根的值需小于右子树的值。左右子树也是二叉查找树。树的每个节点值都不相同。
C代码
#includeiostream
using namespace std;class Tree {
private:int* treeNode;int size;int level;
public:Tree(int size) {treeNode new int[size] {0};this-size size;level 0;}void SetTree(int* tempData, int tempSize) {for (int i 0; i tempSize; i) {for (level 1; treeNode[level] ! 0;) {if (tempData[i] treeNode[level])level level * 2 1;elselevel level * 2;}treeNode[level] tempData[i];}}void PrintTree() {for (int i 1; i size; i)cout treeNode[i] ;cout endl;}
};int main() {int data[]{ 6, 3, 5, 9, 7, 8, 4, 2 };cout 原始数据 endl;for (int i 0; i 8; i)cout data[i] ;cout endl;Tree tree(16);tree.SetTree(data, 8);cout 二叉树数据 endl;tree.PrintTree();return 0;
}
输出结果
