C++ 中带有数组的二叉树实现
c++server side programmingprogramming
二叉树是一种特殊类型的树，其中树的每个节点最多可以有两个子节点。这些子节点称为右子节点和左子节点。
一个简单的二叉树是 −
表示树有两种方式，
- 使用链接列表的动态节点表示
- 使用数组的顺序表示。
在这里，我们将讨论二叉树的数组表示。为此，我们需要对 BT 的节点进行编号。此编号可以从 0 开始到 (n-1) 或从 1 开始到 n。
让我们导出节点及其父节点和子节点在数组中的位置。
当我们使用 基于 0 索引的排序时，
假设父节点的索引为 p。
然后，left_child 节点位于索引 (2*p)+ 1。
right_child 节点位于索引 (2*p) + 2。
根节点位于索引 0。
left_child 位于索引 1。
Right_child 位于索引 2。
当我们使用 基于 1 索引的排序时，
假设父节点位于 索引 p，
Right_node 位于 索引(2*p)。
Left_node 位于 索引 (2*p)+1。
根节点位于索引 1。
left_child 位于索引 2。
Right_child 位于索引 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-----
