一、概念
二叉樹（Binary tree）是樹形結構的一個重要型別，許多實際問題抽象出來的資料結構往往是二叉樹形式，即使是一般的樹也能簡單地轉換為二叉樹，而且二叉樹的存盤結構及其演算法都較為簡單，因此二叉樹顯得特別重要，二叉樹特點是每個節點最多只能有兩棵子樹，且有左右之分 [1] ， 二叉樹是n個有限元素的集合，該集合或者為空、或者由一個稱為根（root）的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成，是有序樹，當集合為空時，稱該二叉樹為空二叉樹，在二叉樹中，一個元素也稱作一個節點 [1]二、完整代碼
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
/*宣告結點*/
typedef struct Node {
int val;
struct Node* lchild, * rchild;
}Node;
/*宣告樹*/
typedef struct Tree {
int* root;
int n;
}Tree;
/*初始化新結點*/
Node* getNewNode(int val) {
Node* node = (Node*)malloc(sizeof(Node));
node->val = val;
node->lchild = node->rchild = NULL;
return node;
}
/*初始化新樹*/
Tree *getNewTree() {
Tree* tree = (Tree*)malloc(sizeof(Tree));
tree->n = 0;
tree->root = NULL;
return tree;
}
/*二叉排序樹 插值法 （插入成功：ret = 1,否則：ret=0） [遞回] */
Node *insertNode(Node *root,int val,int *ret) {
if (root == NULL) {
*ret = 1;
/*初始化一個新結點，將結點插入樹*/
return getNewNode(val);
}
/*如果值相等，回傳原樹*/
if (root->val == val)return root;
/*左小右大*/
if (root->val > val) {
root->lchild = insertNode(root->lchild, val,ret);
}
else {
root->rchild = insertNode(root->rchild, val,ret);
}
/*左小右大插完后，回傳樹結點(易遺漏)*/
return root;
}
void insert(Tree* tree,int val) {
if (tree == NULL)return;
/*flag判斷是否插入成功(0:失敗，1:成功)*/
int flag = 0;
/*注意：插入節點后接識訓傳的樹節點*/
tree->root = insertNode(tree->root,val,&flag);//
/*節點數+1*/
tree->n += flag;
return;
}
/*遞回輸出結點值 【廣義表輸出】*/
void outputNode(Node *root) {
if (root == NULL)return;
/*先輸出根節點的數值*/
printf("%d", root->val);
/*判斷并遞回到左右子樹，輸出值*/
if (root->lchild == NULL && root->rchild == NULL)return;
printf("(");
outputNode(root->lchild);
printf(",");
outputNode(root->rchild);
printf(")");
}
/*輸出樹(呼叫輸出結點)*/
void outputTree(Tree *tree) {
if (tree == NULL)return;
printf("tree(%d):", tree->n);
outputNode(tree->root);
printf("\n");
}
/*清除樹結點*/
void clearNode(Node* node) {
if (node == NULL)return;
free(node->lchild);
free(node->rchild);
free(node);
return;
}
/*清除樹*/
void clearTree(Tree* tree) {
if (tree == NULL)return;
clearNode(tree->root);
free(tree);
return;
}
int main()
{
srand(time(0));
/*先宣告一個樹*/
Tree* tree = getNewTree();
for (int i = 0; i < 10; i++) {
int val = rand() % 100;
insert(tree,val);
/*每插入一個值，列印一次*/
outputTree(tree);
}
return 0;
}三、分塊理解
引入頭檔案，定義結點和數的資料型別#include<stdio.h>
#include<stdlib.h>
#include<time.h>
/*宣告結點*/
typedef struct Node {
int val;
struct Node* lchild, * rchild;
}Node;
/*宣告樹*/
typedef struct Tree {
int* root;
int n;
}Tree;
初始化新結點和樹（結點包含 值 和 左右子樹，數則存放 根節點 及 節點數量）
/*初始化新結點*/
Node* getNewNode(int val) {
Node* node = (Node*)malloc(sizeof(Node));
node->val = val;
node->lchild = node->rchild = NULL;
return node;
}
/*初始化新樹*/
Tree *getNewTree() {
Tree* tree = (Tree*)malloc(sizeof(Tree));
tree->n = 0;
tree->root = NULL;
return tree;
}
定義插入二叉樹的方法（向二叉樹內插入數值，采用 左小右大 的 插入方法 [二叉搜索樹]）這里需要用到遞回，務必認真
/*二叉排序樹 插值法 （插入成功：ret = 1,否則：ret=0） [遞回] */
Node *insertNode(Node *root,int val,int *ret) {
if (root == NULL) {
*ret = 1;
/*初始化一個新結點，將結點插入樹*/
return getNewNode(val);
}
/*如果值相等，回傳原樹*/
if (root->val == val)return root;
/*左小右大*/
if (root->val > val) {
root->lchild = insertNode(root->lchild, val,ret);
}
else {
root->rchild = insertNode(root->rchild, val,ret);
}
/*左小右大插完后，回傳樹結點(易遺漏)*/
return root;
}
void insert(Tree* tree,int val) {
if (tree == NULL)return;
/*flag判斷是否插入成功(0:失敗，1:成功)*/
int flag = 0;
/*注意：插入節點后接識訓傳的樹節點*/
tree->root = insertNode(tree->root,val,&flag);//
/*節點數+1*/
tree->n += flag;
return;
}通過遞回將樹列印出，同樣需要細心
/*遞回輸出結點值 【廣義表輸出】*/
void outputNode(Node *root) {
if (root == NULL)return;
/*先輸出根節點的數值*/
printf("%d", root->val);
/*判斷并遞回到左右子樹，輸出值*/
if (root->lchild == NULL && root->rchild == NULL)return;
printf("(");
outputNode(root->lchild);
printf(",");
outputNode(root->rchild);
printf(")");
}
/*輸出樹(呼叫輸出結點)*/
void outputTree(Tree *tree) {
if (tree == NULL)return;
printf("tree(%d):", tree->n);
outputNode(tree->root);
printf("\n");
}定義清除樹的方法
/*清除樹結點*/
void clearNode(Node* node) {
if (node == NULL)return;
free(node->lchild);
free(node->rchild);
free(node);
return;
}
/*清除樹*/
void clearTree(Tree* tree) {
if (tree == NULL)return;
clearNode(tree->root);
free(tree);
return;
}主函式：隨機對樹進行10次插值操作
int main()
{
srand(time(0));
/*先宣告一個樹*/
Tree* tree = getNewTree();
for (int i = 0; i < 10; i++) {
int val = rand() % 100;
insert(tree,val);
/*每插入一個值，列印一次*/
outputTree(tree);
}
return 0;
}Love for Ever Day
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/458218.html
標籤：其他
上一篇：BIM自動識別三維地圖-Revit模型自動識別三維地圖-IFC模型自動識別三維地圖制作
下一篇：java 5種IO模型