陣列
陣串列示二叉樹：
- root
- left：root*2+1
- right：root*2+2
比如 0號節點的左孩子是1 右孩子是2
1號節點的左孩子是3 右孩子是4
2號節點的左孩子是5 右孩子是6
1、定義結構體
int tree[1000]={0}; //存放值的陣列
const int NUL=0;//定義0為空
2、找樹的最小值和最大值的節點位置
int findMin(int root) //找最小的 往左邊找
{
if(tree[root*2+1]==NUL)
return root;
return findMin(root*2+1);
}
int findMax(int root) //找最小的 往左邊找
{
if(tree[root*2+2]==NUL)
return root;
return findMin(root*2+2);
}
3、插入節點
void Insert(int root,int v)
{
if(tree[root]==NUL)
{
tree[root]=v;
return ;
}
else if(tree[root]>v)
{
Insert(root*2+1,v); //插入到左樹
}
else
{
Insert(root*2+2,v); //插入到右樹
}
}
4、判斷節點是否存在
bool isExist(int root,int val) //是否存在數 二分 用回圈代替遞回
{
while(tree[root]!=NUL)
{
if(tree[root]==val)
return true;
if(tree[root]>val) //小的都在左邊 大的都在右邊
root=root*2+1;
else
root=root*2+2;
}
return false;
}
5、中序遍歷：中序遍歷都是順序是有序的 降序
void PrintAll(int root)//中序遍歷
{
if(tree[root]==NUL)
return;
else
{
//左中右 剛好有序
PrintAll(root*2+1);
cout<<tree[root]<<endl;
PrintAll(root*2+2);
}
}
6、洗掉節點
洗掉節點比較麻煩，但是主要有三種情況
待刪的節點沒有孩子：直接洗掉
待刪的節點有右孩子：
將右子樹的最小的和根節點替換，這樣才能保持二叉樹還符合排序樹的規則，再洗掉替換后的節點（注意這里要遞回洗掉，因為可能右子樹最小的值有左孩子）
待洗掉的節點沒有右孩子，但是有左孩子：
將左邊子樹最大值和根節點換，類似2步遞回洗掉
代碼如下：
void Delete(int root,int x)
{
if(tree[root]>x)
{
Delete(root*2+1,x); //在左邊
}
else if(tree[root]<x)
Delete(root*2+2,x); //在右邊
else
{
if (tree[root*2+1]==NUL && tree[root*2+2]==NUL){ //左右孩子都為空 直接洗掉即可
tree[root] = NUL;
}
else if(tree[root*2+2]!=NUL){ //右邊孩子不為空 將右邊最小的和根換 然后遞回洗掉 因為最小的那個節點可能還有右孩子
int right_small = findMin(root*2+2);
swap(tree[root],tree[right_small]);
Delete(right_small,x);
}
else{ //右邊空左邊不空 則將左邊最大的和根節點換 然后遞回洗掉 因為可能左邊節點有左孩子
int left_max = findMax(root*2+1);
swap(tree[root],tree[left_max]);
Delete(left_max,x);
}
}
}
7、測驗代碼
int main()
{
int root = 0;
Insert(root,10);
Insert(root,4);
Insert(root,8);
Insert(root,20);
Insert(root,3);
Insert(root,1);
PrintAll(root);
cout<<"-----------------"<<endl;
Delete(root,4);
Delete(root,10);
PrintAll(root);
}
1 3 4 8 10
20
1 3 8 20
[https://github.com/biningo/Algorithm](https://github.com/biningo/Algorithm). ---
鏈式結構
差不多，這里貼一下代碼，由于c指標比較麻煩，所以講洗掉的節點值設定為0代表洗掉
#include<iostream>
#include<cstdlib>
using namespace std;
#define NULL 0
struct Node {
int val;
Node* left=NULL;
Node* right=NULL;
Node* pre=NULL;
};
Node* FindMin(Node* root) { //尋找最小的節點 也就是尋找最左邊的節點
if (root->left==NULL)
return root;
return FindMin(root->left);
}
Node* FindMax(Node* root) {
if(root->right==NULL)
return root;
return FindMax(root->right);
}
//-------------------插入--------------------------
void Insert(Node** root,int val) {
if(*root==NULL){
*root = (Node*)malloc(sizeof(Node));
(*root)->left = NULL;
(*root)->right= NULL;
(*root)->val = val;
return;
}
if(val>(*root)->val) //大于根 則插入到右邊
Insert(&(*root)->right,val);
else if(val<(*root)->val) //小于根則插入到左邊
Insert(&(*root)->left,val);
else
cout<<"節點已經存在"<<endl;
return;
}
//---------------------節點是否存在 ---------------
bool IsExist(Node* root,int val) {
if(root->val==val)
return true;
else if(val>root->val)
return IsExist(root->right,val);
else
return IsExist(root->left,val);
}
//---------------------中序遍歷,有序列印------------
void PrintAll(Node* root) {
if(root==NULL)
return;
PrintAll(root->left); //遍歷左子樹
if(root->val!=0){
cout<<root->val<<endl; //左中右
}
PrintAll(root->right);//遍歷右子樹
}
//-------------------洗掉節點 遞回版 洗掉的值為0-----------------------
void Delete(Node*root,int val) {
if(val>root->val)
Delete(root->right,val);
else if(val<root->val)
Delete(root->left,val);
else { //找到節點了
if(root->left==NULL && root->right==NULL){ //沒有孩子 直接free
root->val=0;
}
else if(root->right!=NULL) { //有右孩子 則找右邊最小的孩子替換根節點 讓樹仍然保持有序
Node* right_min = FindMin(root->right);
swap(root->val,right_min->val); //交換值
Delete(right_min,val); //遞回洗掉 因為可能右邊最小的節點還有右孩子
}
else { //只有左孩子 則找左邊最大的和根節點互換
Node* left_max = FindMax(root->left);
swap(root->val,left_max->val);
Delete(left_max,val); //同理
}
}
}
int main(){
Node* root=NULL;
Insert(&root,10);
Insert(&root,4);
Insert(&root,8);
Insert(&root,20);
Insert(&root,3);
Insert(&root,1);
PrintAll(root);
//
cout<<"-----------------"<<endl;
Delete(root,4);
Delete(root,10);
//
//
PrintAll(root);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/73560.html
標籤：其他