#define _CRT_SECURE_NO_WARNINGS 1
//樹：非線性的數據結構，由有限個節點組成一個具有層次關係的集合。像是一顆倒掛的樹，所以叫樹。
//樹的相關概念：
//1、節點的度：一個節點含有的子樹的個數成為節點的度
//2、葉節點（終端節點）：度為0的節點稱為終端節點，（子節點為空的節點）
//3、非終端節點（分支節點）：度不為0的節點，即（子節點不為空的節點）
//4、雙親節點（父節點）：若一個節點含有子節點，稱該節點為子節點的父節點
//5、孩子節點（子節點）：一個節點含有的子樹的根節點稱為該節點的子節點
//6、兄弟節點：具有相同父節點的節點稱為兄弟節點
//7、樹的度：一棵樹中，最大的節點的度稱為樹的度
//8、節點的層次：從根開始定義起，根為第一層，根的子節點為第二層，以此類推
//9、樹的高度或深度:樹中節點的最大層次
//10、堂兄弟節點：雙親在同一層的節點互為堂兄弟節點
//11、節點的祖先：從根到該節點所經分支上的所有節點
//12、子孫：以某節點為根的子樹中的任一節點，都稱為該節點的子孫
//13、森林:多棵不想交的樹的集合稱為森林
//
//
//樹的每個節點又有子節點。沒有父節點的節點稱為根節點。每個非根節點有且只有一個父節點，每個子節點可以分成多個不相交的子樹。
//
//樹的存儲方式有多種，如雙親表示法、孩子表示法、孩子兄弟表示法。
//1、雙親表示法：用連續的空間存儲每個節點，每個節點中有一個指向雙親節點地址的指針。容易找到雙親節點，不易找到孩子節點。
//2、孩子表示法：將每個節點的孩子節點用鏈表鏈接起來，容易找到孩子節點，但是不容易找到雙親節點。
//3、孩子兄弟表示法：在每個節點中，保存一個指向自己第一個孩子節點的指針，還保存一個指針自己下一個兄弟節點的指針。
//
//樹的應場景：人工智能中的決策樹、MYSQL數據庫索引、文件系統的目錄結構等。
//
//二叉樹：有限個節點集合，該集合為空，或者是由一個根節點加一棵左子樹和一棵右子樹組成的兩個分支的樹結構。
//二叉樹的特點：每個節點最多有兩棵子樹，二叉樹的兩個子樹分別稱為左右子樹，次序不能顛倒。
//五種基本形式：一個空節點、 只有一個非空節點、 根節點有一棵左子樹、 根節點有一棵右子樹、 根節點有左右子樹
//
//滿二叉樹：每一層節點數都達到最大值的二叉樹。（除了最後一層葉子節點，其它每個節點都有左右棵子樹），層數為 K ，節點數為 （2^k-1）。
//完全二叉樹：深度為 K ,有 n 個節點的二叉樹，當且僅當其每一個節點都與深度為 K 的滿二叉樹中編號從1到 n 的節點一一對應。
// （相同高度的完全二叉樹葉子節點這一層，從最右邊一個右往左依次缺失部分子樹。）
// （滿二叉樹是一種特殊的完全二叉樹）
//二者的區別: 滿二叉樹的每一層，節點個數都達到最大值，也就是除了葉子節點那一層，每一層的父節點都有不為空的左右子樹.
// 完全二叉樹的最後一層的節點個數可能沒有達到最大值。
//
//二叉樹的順序存與鏈式存儲
//順序存儲：使用數組來存儲，一般只適合用來表示完全二叉樹，因為不是完全二叉樹會有空節點造成空間浪費，現實中只有堆才會用數組存儲。
// 二叉樹順序存儲在物理上是數組，在邏輯上是二叉樹。
//
//鏈式存儲：用鏈表來表示二叉樹，用鏈來指示元素的邏輯關係。通常的方法是鏈表中每個節點由數據域和左右指針域三部分組成。
// 數據域保存值，左右指針保存左右孩子節點的地址。
//
//二叉樹有三種遍歷方式：前序遍歷、中序遍歷、後序遍歷
//
//實現二叉樹以下操作。
// 1. 創建二叉樹
//BTNode* CreateBinTree(BTDataType* array, int size);
//
// 銷燬二叉樹
//void DestroyTree(BTNode** pRoot);
//
// 二叉樹的三種遍歷方式
//void PreOrder(BTNode* pRoot);
//void InOrder(BTNode* pRoot);
//void PostOrderNor(BTNode* pRoot);
//
//void LevelOrder(BTNode* pRoot);
//
// 獲取二叉樹中節點的個數
//int GetNodeCount(BTNode* pRoot);
//
// 求二叉樹的高度
//int Height(BTNode* pRoot);
//
// 獲取二叉數中葉子節點的個數
//int GetLeafNodeCount(BTNode* pRoot);
//
// 獲取二叉樹第K層節點的個數
//int GetKLevelNodeCount(BTNode* pRoot, int K);
//
// 獲取二叉樹中某個節點的雙親節點
//BTNode* GetNodeParent(BTNode* pRoot, BTNode* pNode);
#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
typedef struct Node {
int value;
struct Node *left; // 指向左孩子節點
struct Node *right; // 指向右孩子節點
} Node;
// 前序遍歷
void preOrderTraversal(Node *root)
{
if (root == NULL)
{
return;
}
printf("%d ", root->value);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
// 中序遍歷
void inOrderTraversal(Node *root)
{
if (root == NULL)
{
return;
}
inOrderTraversal(root->left);
printf("%d ", root->value);
inOrderTraversal(root->right);
}
//後序遍歷
void postOrderTraversal(Node *root)
{
if (root == NULL)
{
return;
}
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->value);
}
//通過中序遍歷來實現節點個數統計
int count = 0;
void getNodeCount(Node *root)
{
if (root == NULL)
{
return;
}
getNodeCount(root->left);
count++;
getNodeCount(root->right);
}
//通過後序遍歷來實現節點個數統計
int getNodeCount2(Node *root)
{
if (root == NULL)
{
return 0;
}
int left = getNodeCount2(root->left);
int right = getNodeCount2(root->right);
return left + 1 + right;
}
int myMax(int a, int b)
{
return a >= b ? a : b;
}
//獲取二叉樹的高度
int getHeight(Node *root)
{
if (root == NULL)
{
return 0;
}
//分別對獲取左右子樹的高度，然後返回最大的值
int left = getHeight(root->left);
int right = getHeight(root->right);
return left >= right ? left : right;
//返回值封裝成函數
return myMax(left, right) + 1;
}
//統計葉子節點的個數
int getLeafCount(Node *root)
{
if (root == NULL)
{
return 0;
}
//每找到一個節點，它的左右子樹都是空節點時返回一個1
else if (root->left == NULL && root->right == NULL)
{
return 1;
}
else
{
//遞歸分別對左子樹和右子樹的葉子節點進行統計
return getLeafCount(root->left) + getLeafCount(root->right);
}
}
//k層節點個數
int getKLevelCount(Node *root, int k)
{
assert(k >= 1);
if (root == NULL)
{
return 0;
}
else if (k == 1)
{
return 1;
}
else
{
return getKLevelCount(root->left, k - 1)
+ getKLevelCount(root->right, k - 1);
}
}
//二叉樹中查找指定值
Node * find(Node *root, int v)
{
if (root == NULL)
{
return NULL; // 沒有找到
}
if (root->value == v)
{
return root;
}
Node * left = find(root->left, v);
if (left != NULL)
{
return left;
}
Node * right = find(root->right, v);
if (right != NULL)
{
return right;
}
else
{
return NULL;
}
}
//銷燬二叉樹
void DestroyTree(Node *node)
{
Node *head = NULL;
Node *prev = NULL;
node->left = prev;
if (prev == NULL)
{
head = node;
}
else
{
prev->right = node;
}
prev = node;
}
//創建樹
Node * createTree(int *arr, int size)
{
//將數組中的值放到節點中
Node *n1 = (Node *)malloc(sizeof(Node));
n1->value = arr[0];
Node *n2 = (Node *)malloc(sizeof(Node));
n2->value = arr[1];
Node *n3 = (Node *)malloc(sizeof(Node));
n3->value = arr[2];
Node *n4 = (Node *)malloc(sizeof(Node));
n4->value = arr[3];
Node *n5 = (Node *)malloc(sizeof(Node));
n5->value = arr[4];
Node *n6 = (Node *)malloc(sizeof(Node));
n6->value = arr[5];
Node *n7 = (Node *)malloc(sizeof(Node));
n7->value = arr[6];
Node *n8 = (Node *)malloc(sizeof(Node));
n8->value = arr[7];
//將節點鏈接成樹
n1->left = n2; n1->right = n3;
n2->left = n4; n2->right = n5;
n3->left = n6; n3->right = n7;
n4->left = NULL; n4->right = NULL;
n5->left = NULL; n5->right = n8;
n6->left = NULL; n6->right = NULL;
n7->left = NULL; n7->right = NULL;
return n1;
}
int main()
{
int arr[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
int size = sizeof(arr) / sizeof(arr[0]);
//創建樹
Node* n1=createTree(arr, size);
// 1 2 3 4 5 6 7 8
// a b c d e f g h
//遞歸方式實現三種遍歷。通過打印值來看遍歷的順序
preOrderTraversal(n1); printf("\n"); //1 2 4 5 8 3 6 7
inOrderTraversal(n1); printf("\n"); //4 2 5 8 1 6 3 7
postOrderTraversal(n1); printf("\n");//4 8 5 2 6 7 3 1
system("pause");
return 0;
}
本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。
