数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中使用数组实现二叉树
二叉树是一种特殊的树，其中树的每个节点最多可以有两个子节点。这些子节点称为右子节点和左子节点。
一个简单的二叉树如下所示：
表示树有两种方法：
- 使用链表的动态节点表示
- 使用数组的顺序表示。
在这里，我们将讨论二叉树的数组表示。为此，我们需要对二叉树的节点进行编号。此编号可以从 0 到 (n-1) 或从 1 到 n 开始。
让我们推导出节点及其父节点和子节点在数组中的位置。
当我们使用**基于 0 的索引排序**时，
假设父节点的索引为 p。
则左子节点位于索引 (2*p)+ 1 处。
右子节点位于索引 (2*p) + 2 处。
根节点位于索引 0 处。
左子节点位于索引 1 处。
右子节点位于索引 2 处。
当我们使用**基于 1 的索引排序**时，
假设父节点位于**索引 p**处，
右子节点位于**索引 (2*p)**处。
左子节点位于**索引 (2*p)+1**处。
根节点位于索引 1 处。
左子节点位于索引 2 处。
右子节点位于索引 3 处。
示例
#include<bits/stdc++.h>
using namespace std;
char tree[10];
int rootnode(char key){
if(tree[0] != '\0')
cout<<"Tree already had root";
else
tree[0] = key;
return 0;
}
int leftchild(char key, int parent){
if(tree[parent] == '\0')
cout <<"\nCan't set child at"<<(parent * 2) + 1<<" , no parent found";
else
tree[(parent * 2) + 1] = key;
return 0;
}
int rightchild(char key, int parent){
if(tree[parent] == '\0')
cout<<"\nCan't set child at"<<(parent * 2) + 2<<" , no parent found";
else
tree[(parent * 2) + 2] = key;
return 0;
}
int traversetree(){
cout << "\n";
for(int i = 0; i < 10; i++){
if(tree[i] != '\0')
cout<<tree[i];
else
cout<<"-";
}
return 0;
}
int main(){
rootnode('A');
rightchild('C', 2);
leftchild('D', 0);
rightchild('E', 1);
rightchild('F', 2);
traversetree();
return 0;
}输出
Can't set child at6 , no parent found Can't set child at6 , no parent found AD--E-----
更新于: 2020-01-03
4K+ 次查看
广告