資料結構
網路
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+ 次檢視
廣告