溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“C語言鏈式二叉樹結構原理是什么”，在日常操作中，相信很多人在C語言鏈式二叉樹結構原理是什么問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C語言鏈式二叉樹結構原理是什么”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;二叉樹的遍歷，是學習二叉樹結構的重要部分。二叉樹的遍歷主要分為三種：1.前序遍歷 2.中序遍歷 3.后序遍歷。首先我們要知道一顆二叉樹分為根，左子樹，右子樹。而三種遍歷方式也是圍繞著根來實現的。
我們按上圖來構建一顆二叉樹
BTNode* CreatTreeNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTDataType));
node->data = x;
node->right = NULL;
node->left = NULL;
return node;
}
int main()
{
BTNode* A = CreatTreeNode('A');
BTNode* B = CreatTreeNode('B');
BTNode* C = CreatTreeNode('C');
BTNode* D = CreatTreeNode('D');
BTNode* E = CreatTreeNode('E');
BTNode* F = CreatTreeNode('F');
A->left = B;
A->right = C;
B->left = D;
C->left = E;
C->right = F;
}前序遍歷的順序為 根 左子樹 右子樹 顧名思義就是先訪問根節點再訪問左節點最后訪問右節點。
按照前序遍歷，則上圖的遍歷順序為：A B D NULL NULL NULL C E NULL NULL F NULL NULL
// 二叉樹前序遍歷
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL) //等于NULL就直接返回
{
printf("NULL ");
return;
}
printf("%c ", root->data);// 打印節點
BinaryTreePrevOrder(root->left);//遞歸到左子樹
BinaryTreePrevOrder(root->right);//遞歸到右子樹
}中序遍歷的順序為 左子樹 根 右 顧名思義就是先訪問左節點再訪問根節點最后訪問右節點。
按照中序遍歷，則上圖的遍歷順序為：NULL D NULL B NULL A NULL E NULL C NULL F NULL
// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL) //等于NULL就直接返回
{
printf("NULL ");
return;
}
BinaryTreePrevOrder(root->left);//遞歸到左子樹
printf("%c ", root->data);//打印節點
BinaryTreePrevOrder(root->right);//遞歸到右子樹
}后序遍歷的順序為 左子樹 右子樹 根 顧名思義就是先訪問左節點，再訪問右節點，最后訪問根。
按照后序遍歷，則上圖的遍歷順序為：NULL NULL D NULL B NULL NULL E NULL NULL F C A
// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)//等于NULL直接返回
{
printf("NULL ");
return;
}
BinaryTreePostOrder(root->left);//遞歸到左子樹
BinaryTreePostOrder(root->right);//遞歸到右子樹
printf("%c ", root->data);//打印節點
}求二叉樹節點的個數與上述遍歷類似，都是通過遞歸函數來實現。一顆二叉樹的節點個數主要以三個部分構成：根節點+左子樹的節點個數+右子樹的節點個數。知道這個公式我們就可以實現代碼
// 二叉樹節點個數
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)//如果為空返回零
{
return 0;
}
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}葉子節點的左右子樹都為空，知道這個，我們只需稍微改動上述代碼即可
// 二叉樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if ((root->left == NULL) && (root->right == NULL))
{
return 1;
}
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}如果指定一顆二叉樹，求它第K層節點個數，也可以采用遞歸的思想，當給定的K為零的時候此時就是求根節點的個數，顯而易見就是返回1；而K不為零時，我們可以求root左右子樹K-1層的節點數之和。
// 二叉樹第k層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}二叉樹的高度就是指二叉樹節點層次的最大值，也就是左右子樹最大高度+1.
//二叉樹深度/高度
int BinaryTreeDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int leftDepth = BinaryTreeDepth(root->left);
int rightDepth = BinaryTreeDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}// 二叉樹查找值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL) //根為空，直接返回NULL
{
return NULL;
}
if (root->data == x)//找到了 直接返回節點
{
return root;
}
BTNode* leftRet = BinaryTreeFind(root->left, x);
if (leftRet)
{
return leftRet; //如果再左子樹找到，直接返回，無需遞歸到右子樹
}
BTNode* rightRet = BinaryTreeFind(root->right, x);
if (rightRet)
{
return rightRet;
}
return NULL; //如果都沒找到，就直接返回NULL
}#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
BTNode* CreatTreeNode(BTDataType x);
// 二叉樹節點個數
int BinaryTreeSize(BTNode* root);
// 二叉樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root);
// 二叉樹第k層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉樹查找值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉樹前序遍歷
void BinaryTreePrevOrder(BTNode* root);
// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root);
// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root);
//二叉樹深度/高度
int BinaryTreeDepth(BTNode* root);
#include"BinarryTree.h"
BTNode* CreatTreeNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTDataType));
assert(node);
node->data = x;
node->right = NULL;
node->left = NULL;
return node;
}
// 二叉樹前序遍歷
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return ;
}
printf("%c ", root->data);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}
// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return ;
}
BinaryTreePrevOrder(root->left);
printf("%c ", root->data);
BinaryTreePrevOrder(root->right);
}
// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return ;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%c ", root->data);
}
// 二叉樹節點個數
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
// 二叉樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if ((root->left == NULL) && (root->right == NULL))
{
return 1;
}
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// 二叉樹第k層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
// 二叉樹查找值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode* leftRet = BinaryTreeFind(root->left, x);
if (leftRet)
{
return leftRet;
}
BTNode* rightRet = BinaryTreeFind(root->right, x);
if (rightRet)
{
return rightRet;
}
return NULL;
}
// 二叉樹銷毀
void BinaryTreeDestory(BTNode** root)
{
if (*root)
{
BinaryTreeDestory(&(*root)->left);
BinaryTreeDestory(&(*root)->right);
free(*root);
*root = NULL;
}
}
//二叉樹深度/高度
int BinaryTreeDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int leftDepth = BinaryTreeDepth(root->left);
int rightDepth = BinaryTreeDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
#include"BinarryTree.h"
int main()
{
BTNode* A = CreatTreeNode('A');
BTNode* B = CreatTreeNode('B');
BTNode* C = CreatTreeNode('C');
BTNode* D = CreatTreeNode('D');
BTNode* E = CreatTreeNode('E');
BTNode* F = CreatTreeNode('F');
A->left = B;
A->right = C;
B->left = D;
C->left = E;
C->right = F;
return 0;
}到此，關于“C語言鏈式二叉樹結構原理是什么”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
