ツリーの作成と関連アルゴリズム
9452 ワード
ツリーは非常に重要なデータ構造であり、ブランチ構造の基礎であり、今日はブログを書いて、関連するアルゴリズムとツリーの作成過程を説明します.
1:ツリーの作成:
主に先序、中序、後序、層序がいくつかの方式を作成し、そのうち前の3つは二叉木遍歴方式に基づいている.
(1):シーケンス作成
シーケンス作成とは、ルートノードを作成し、左サブツリーと右サブツリーを順に作成することです.ツリー自体が再帰アルゴリズムに基づいているため、再帰的な方法で実現できます.
(2):中および後に作成:
前の順序でツリーを作成する方法がわかり、中の順序と後続も類比できます.前の順序とは、ルートノードを作成する順序です.
(3):層順遍歴と作成:
:
以上の画像が反映する層順遍歴の過程で、層順遍歴はキューの基礎の上で創立して、まず1粒の二叉木が空でないならば、ルートノードを入隊させて、もしルートノードの左のサブツリーの後で右のサブツリーが空でないならば、ルートノードは出てそのデータドメインの値を印刷して、左の右のサブツリーは前後して入隊して(誰が空いていないで誰が入隊します)、それから1つの再帰的な過程です.
可視レイヤシーケンスループは、上から下へ、左から右へのループプロセスです.
したがって、ツリーを階層的に作成することもできます.まずルートノードを作成し、ルートノードの左の子と右の子のポインタが虚のノードを指していない場合は、左の子ツリーと右の子ツリーを作成し、再帰的に作成します.
ツリーコード:
関数ファイルc:
#include "Bittree.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
tree *Creat(tree* root, tree*(*ptree)(tree *root))
{
root = ptree(root);
return root;
}
tree *Tier_creat(tree* root) // root
{
tree *s = NULL;
datatype data = 0;
tree *Tree_arr[MAX] = { 0 }; //
int front = 1; //front
int rear = 0; //rear
printf(" ， -1 ，-2 ！
");
scanf("%d", &data);
while (data != -2)
{
s = NULL;
if (data != -1)
{
s =(tree*) malloc(sizeof(tree)* 1);
s->data = data;
s->Lchild = NULL;
s->Rchild = NULL;
}
rear++;
Tree_arr[rear] = s; //
if (rear == 1) root = s; // rear ，
else
{
if (Tree_arr[rear] && s) //
{
if (rear % 2 == 0) Tree_arr[front]->Lchild = s; //
if (rear % 2 == 1)
{
Tree_arr[front]->Rchild = s; //
front++; // rear ， ，
}
}
}
scanf("%d", &data);
}
return root;
}
tree *DLR_creat(tree* root) //
{
printf(" -1 ， -2
");
root = NULL;
int data = 0;
printf(" ：");
scanf("%d", &data);
if (data == -1)
return NULL;
root = (tree*)malloc(sizeof(tree)* 1);
if (root == NULL)
{
printf(" ！
");
exit(EXIT_FAILURE);
}
root->data = data;
root->Lchild=DLR_creat(root->Lchild);
root->Rchild = DLR_creat(root->Rchild);
return root;
}
tree *LDR_creat(tree* root) //
{
printf(" -1 ， -2
");
root = NULL;
int data = 0;
printf(" ：");
scanf("%d", &data);
if (data == -1)
return NULL;
root->Lchild = DLR_creat(root->Lchild);
root = (tree*)malloc(sizeof(tree)* 1);
if (root == NULL)
{
printf(" ！
");
exit(EXIT_FAILURE);
}
root->data = data;
root->Rchild = DLR_creat(root->Rchild);
return root;
}
tree *RLD_creat(tree* root) //
{
printf(" -1 ， -2
");
root = NULL;
int data = 0;
printf(" ：");
scanf("%d", &data);
if (data == -1)
return NULL;
root->Lchild = DLR_creat(root->Lchild);
root->Rchild = DLR_creat(root->Rchild);
root = (tree*)malloc(sizeof(tree)* 1);
if (root == NULL)
{
printf(" ！
");
exit(EXIT_FAILURE);
}
root->data = data;
return root;
}
void Print_Tree(tree *root, void(*ptree)(tree *root)) //
{
assert(root);
if (root == NULL)
{
printf(" ！
");
return;
}
else
{
ptree(root);
printf("
");
}
}
void DLR_Print(tree *root) //
{
if (root != NULL)
{
printf("%d ", root->data);
DLR_Print(root->Lchild);
DLR_Print(root->Rchild);
}
return;
}
void LDR_Print(tree *root) //
{
if (root != NULL)
{
DLR_Print(root->Lchild);
printf("%d ", root->data);
DLR_Print(root->Rchild);
}
return;
}
void RLD_Print(tree *root) //
{
if (root != NULL)
{
DLR_Print(root->Lchild);
DLR_Print(root->Rchild);
printf("%d ", root->data);
}
return;
}
void Tie_Print(tree *root) //
{
tree* arry[MAX] = { 0 };
int rear = 1;
int front = 0;
if (root == NULL)
{
printf(" ！
");
return;
}
else
{
arry[0] = root; // ， 。
while (front < rear) //
{
if (arry[front])
{
printf("%d ", arry[front]->data);
arry[rear++] = arry[front]->Lchild;
arry[rear++] = arry[front]->Rchild;
front++;
}
else
{
front++;
}
}
}
}
int Deep_tree(tree *root) //
{
assert(root);
int left = 0;
int right = 0;
int deep = 0;
if (root != NULL)
{
left=Deep_tree(root->Lchild); //
right = Deep_tree(root->Rchild); //
deep = left > right ? (left + 1) : (right + 1);
}
return deep;
}
int Node_du(tree *root) //
{
assert(root);
int ret = 0;
if (root == NULL)
return 0;
else
{
if (root->Lchild != NULL)
ret++;
if (root->Rchild != NULL)
ret++;
return ret;
}
}
int tree_Node(tree *root)
{
assert(root);
int ret = 0;
if (root == NULL)
return 0;
if (root->Lchild == NULL&&root->Rchild == NULL) //
return 1;
ret =1+ tree_Node(root->Lchild) + tree_Node(root->Rchild);
return ret;
}
tree* search_Node(tree *root, datatype data) // data
{
assert(root);
tree *p=NULL;
if (root == NULL)
{
printf(" ！
");
return NULL;
}
else
{
if (root->data == data)
return root;
if (root->Lchild != NULL)
{
p = search_Node(root->Lchild,data);
if (p != NULL)
return p;
}
if (root->Rchild != NULL)
{
p = search_Node(root->Rchild,data);
if (p != NULL)
return p;
}
return NULL; //
}
}
void Deal_tree(tree *root) //
{
assert(root);
if (root == NULL)
return;
Deal_tree(root->Lchild);
Deal_tree(root->Rchild);
free(root);
root = NULL;
}ヘッダファイルh
#ifndef __BITTREE_H__
#define __BITTREE_H__
#define _CRT_SECURE_NO_WARNINGS
#define MAX 100
typedef int datatype;
typedef struct Bittree
{
datatype data;
struct Bittree *Lchild;
struct Bittree *Rchild;
}tree;
typedef struct
{
datatype Elem_data[MAX];
int length;
}Tree_arry;
tree *Tier_creat(tree* root); // root
tree *DLR_creat(tree* root); //
tree *LDR_creat(tree* root); //
tree *RLD_creat(tree* root); //
tree *Creat(tree* root,tree*(*ptree)(tree *root)); //
void Print_Tree(tree *root, void(*ptree)(tree *root)); //
void DLR_Print(tree *root); //
void LDR_Print(tree *root); //
void RLD_Print(tree *root); //
void Tie_Print(tree *root); //
int Deep_tree(tree *root); //
int Node_du(tree *root); //
int tree_Node(tree *root); //
tree* search_Node(tree *root, datatype data); // data
void Deal_tree(tree *root); //
#endif __BITTREE_H__
テストファイルc:
#include "Bittree.h"
#include <stdio.h>
#include <stdlib.h>
void Init()
{
printf("1:
");
printf("2:
");
printf("3:
");
printf("4:
");
printf("5:
");
printf("0:
");
}
void Init_Print()
{
printf("0： .
");
printf("1： .
");
printf("2： .
");
printf("3： .
");
}
void Init_Creat()
{
printf("0： .
");
printf("1： .
");
printf("2： .
");
printf("3： .
");
}
void test()
{
int ret;
int key=0;
int choose;
datatype data=0;
tree *root = NULL;
tree *node = NULL;
tree* (*Tree_C[4])(tree *root) = { 0 }; //
void(*Tree_p[4])(tree *root) = { 0 }; //
Tree_C[0] = Tier_creat;
Tree_C[1] = DLR_creat;
Tree_C[2] = LDR_creat;
Tree_C[3] = RLD_creat;
Tree_p[0] = Tie_Print;
Tree_p[1] = DLR_Print;
Tree_p[2] = LDR_Print;
Tree_p[3] = DLR_Print;
while (1)
{
printf(" ：");
scanf("%d", &key);
switch (key)
{
case 0:
printf("Program Over!!
");
exit(EXIT_FAILURE);
break;
case 1:
Init_Creat();
do
{
printf(" ：");
scanf("%d", &choose);
} while (choose <= 0 && choose >= 3);
root = Creat(root, Tree_C[choose]);
break;
case 2:
Init_Print();
do
{
printf(" ：");
scanf("%d", &choose);
} while (choose <= 0 && choose >= 3);
Print_Tree(root, Tree_p[choose]);
break;
case 3:
ret = Deep_tree(root);
printf(" ：%d
", ret);
break;
case 4:
printf(" ：");
scanf("%d", &data);
node=search_Node(root, data);
if (node == NULL)
{
printf(" ！
");
exit(EXIT_FAILURE);
}
ret = Node_du(node);
printf(" %d ：%d
",data, ret);
break;
case 5:
Deal_tree(root);
printf(" ！
");
break;
}
}
}
int main()
{
Init();
test();
system("pause");
return 0;
}上記の記述に関連する問題があれば、ご指摘ください[email protected]