C語言 鏈式二叉樹結(jié)構(gòu)詳解原理
前言
二叉樹不同于順序表,一顆普通的二叉樹是沒有增刪改查的意義。普通的二叉樹用來存儲數(shù)據(jù)是不方便的。但是二叉樹的一些基本實現(xiàn)結(jié)構(gòu),例如前序遍歷,中序遍歷。。。等等都是對我們學習更深層次的二叉樹打下夯實的基礎(chǔ)。
二叉樹節(jié)點聲明
typedef char BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode;
二叉樹的遍歷
二叉樹的遍歷,是學習二叉樹結(jié)構(gòu)的重要部分。二叉樹的遍歷主要分為三種:1.前序遍歷 2.中序遍歷 3.后序遍歷。首先我們要知道一顆二叉樹分為根,左子樹,右子樹。而三種遍歷方式也是圍繞著根來實現(xiàn)的。
構(gòu)建二叉樹
我們按上圖來構(gòu)建一顆二叉樹
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; }
1.前序遍歷
前序遍歷的順序為 根 左子樹 右子樹 顧名思義就是先訪問根節(jié)點再訪問左節(jié)點最后訪問右節(jié)點。
按照前序遍歷,則上圖的遍歷順序為: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);// 打印節(jié)點 BinaryTreePrevOrder(root->left);//遞歸到左子樹 BinaryTreePrevOrder(root->right);//遞歸到右子樹 }
2.中序遍歷
中序遍歷的順序為 左子樹 根 右 顧名思義就是先訪問左節(jié)點再訪問根節(jié)點最后訪問右節(jié)點。
按照中序遍歷,則上圖的遍歷順序為: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);//打印節(jié)點 BinaryTreePrevOrder(root->right);//遞歸到右子樹 }
3.后序遍歷
后序遍歷的順序為 左子樹 右子樹 根 顧名思義就是先訪問左節(jié)點,再訪問右節(jié)點,最后訪問根。
按照后序遍歷,則上圖的遍歷順序為: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);//打印節(jié)點 }
二叉樹節(jié)點的個數(shù)
求二叉樹節(jié)點的個數(shù)與上述遍歷類似,都是通過遞歸函數(shù)來實現(xiàn)。一顆二叉樹的節(jié)點個數(shù)主要以三個部分構(gòu)成:根節(jié)點+左子樹的節(jié)點個數(shù)+右子樹的節(jié)點個數(shù)。知道這個公式我們就可以實現(xiàn)代碼
// 二叉樹節(jié)點個數(shù) int BinaryTreeSize(BTNode* root) { if (root == NULL)//如果為空返回零 { return 0; } return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1; }
二叉樹葉子節(jié)點的個數(shù)
葉子節(jié)點的左右子樹都為空,知道這個,我們只需稍微改動上述代碼即可
// 二叉樹葉子節(jié)點個數(shù) 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層節(jié)點個數(shù)
如果指定一顆二叉樹,求它第K層節(jié)點個數(shù),也可以采用遞歸的思想,當給定的K為零的時候此時就是求根節(jié)點的個數(shù),顯而易見就是返回1;而K不為零時,我們可以求root左右子樹K-1層的節(jié)點數(shù)之和。
// 二叉樹第k層節(jié)點個數(shù) 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); }
二叉樹的高度/深度
二叉樹的高度就是指二叉樹節(jié)點層次的最大值,也就是左右子樹最大高度+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的節(jié)點
// 二叉樹查找值為x的節(jié)點 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) //根為空,直接返回NULL { return NULL; } if (root->data == x)//找到了 直接返回節(jié)點 { 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); // 二叉樹節(jié)點個數(shù) int BinaryTreeSize(BTNode* root); // 二叉樹葉子節(jié)點個數(shù) int BinaryTreeLeafSize(BTNode* root); // 二叉樹第k層節(jié)點個數(shù) int BinaryTreeLevelKSize(BTNode* root, int k); // 二叉樹查找值為x的節(jié)點 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); } // 二叉樹節(jié)點個數(shù) int BinaryTreeSize(BTNode* root) { if (root == NULL) { return 0; } return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1; } // 二叉樹葉子節(jié)點個數(shù) 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層節(jié)點個數(shù) 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的節(jié)點 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; }
到此這篇關(guān)于C語言 鏈式二叉樹結(jié)構(gòu)詳解原理的文章就介紹到這了,更多相關(guān)C語言 鏈式二叉樹結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
- 為了更好的應(yīng)對《算法設(shè)計與分析》這門課程,我把書上以及老師講過的案例都詳細的做一個重現(xiàn)及解剖,讓你熟記每一個潛在的考點,希望能給大家?guī)椭?/div> 2022-05-05
C++流程控制中用于跳轉(zhuǎn)的return和goto語句學習教程
這篇文章主要介紹了C++流程控制中用于跳轉(zhuǎn)的return和goto語句學習教程,是C++入門學習中的基礎(chǔ)知識,需要的朋友可以參考下2016-01-01最新評論