【數據結構】------C語言實現二叉樹

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 作者主頁：作者主頁

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 數據結構專欄：數據結構

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?創作時間：2024年5月20日

一、二叉樹的定義

二叉樹(Binary Tree) 是由n個結點構成的有限集(n≥0)，n=0時為空樹，n>0時為非空樹。

對于非空樹：

有且僅有一個根節點
除根結點外其他可分為兩個不相交的子集Tl和Tr，分別稱為T TT的左子樹和右子樹，從定義也可以看出二叉樹與一般樹的區別主要是兩點，一是每個結點的度最多為2；二是結點的子樹有左右之分，不能隨意調換，調換后又是一棵新的二叉樹。

二、二叉樹的形態

五種基本形態：

三種特殊形態：

三、二叉樹的性質

任意二叉樹第 i ii 層最大結點數為2^(i-1)。（i>=1）
深度為 k ?的二叉樹最大結點總數為2^k-1個（滿二叉樹）
對于任意二叉樹：

四、二叉樹的存儲

存的目的是為了取，而取的關鍵在于如何通過父結點拿到它的左右子結點，不同存儲方式圍繞的核心也就是這。

順序存儲：

使用一組地址連續的存儲單元存儲，例如數組。為了在存儲結構中能得到父子結點之間的映射關系，二叉樹中的結點必須按層次遍歷的順序存放。具體是：

對于完全二叉樹，只需要自根結點起從上往下、從左往右依次存儲。
對于非完全二叉樹，首先將它變換為完全二叉樹，空缺位置用某個特殊字符代替（比如#），然后仍按完全二叉樹的存儲方式存儲。

假設將一棵二叉樹按此方式存儲到數組后，左子結點下標=2倍的父結點下標+1，右子節點下標=2倍的父結點下標+2（這里父子結點間的關系是基于根結點從0開始計算的）。若數組某個位置處值為#，代表此處對應的結點為空。

可以看出順序存儲非常適合存儲接近完全二叉樹類型的二叉樹，對于一般二叉樹有很大的空間浪費，所以對于一般二叉樹，一般用下面這種鏈式存儲。

鏈式存儲：

對每個結點，除數據域外再多增加左右兩個指針域，分別指向該結點的左孩子和右孩子結點，再用一個頭指針指向根結點。對應的存儲結構：

二叉樹代碼的實現：

首先我們要得到相應的自定義函數，然后再去一一實現他們

typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;}BTNode;//創建一顆樹
BTNode* creatBT();//創建一個新節點
BTNode* BuyNode(int x);//前序遍歷
void PrevOrder(BTNode* root);//計算節點個數
int TreeSize(BTNode* root);

由于我們接下來的前序、中序、后序遍歷都需要一個二叉樹，所以我們這里要先創建一顆二叉樹才可以。

創建一個簡易二叉樹：

//創建一個新節點
BTNode* BuyNode(int x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc failed");exit(0);}newnode->data = x;newnode->left = newnode->right =NULL;return newnode;
}BTNode* creatBT()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}

前序遍歷：

//前序遍歷
void PrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);//輸出當前數值PrevOrder(root->left);//然后遞歸進行PrevOrder(root->right);
}

中序遍歷：

//中序遍歷
void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);//先遞歸，等到最后一個之后再進行輸出printf("%d ", root->data);InOrder(root->right);
}

后序遍歷：

//后序遍歷
void BackOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}BackOrder(root->left);BackOrder(root->right);printf("%d ", root->data);
}

節點個數：

//節點個數
int treesize(BTNode* root)
{if (root == NULL)return 0;else return treesize(root->left) + treesize(root->right) + 1 ;
}

另一種方式：

int TreeSize(BTNode* root)
{static int size = 0;//用局部靜態變量，只初始化一次。if (root == NULL){return 0;}else{++size;}TreeSize(root->left);TreeSize(root->right);return size;
}

求葉子節點個數：

//求葉子節點個數
int TreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

樹的高度：

int TreeHeigh(BTNode* root)
{if (root == NULL){return 0;}int leftheight = TreeHeigh(root->left);int rightheight = TreeHeigh(root->right);return leftheight > rightheight ?leftheight + 1 : rightheight + 1;
}

總代碼：

Tree.h:

#pragma once
#include<iostream>
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;}BTNode;//創建一顆樹
BTNode* creatBT();//創建一個新節點
BTNode* BuyNode(int x);//前序遍歷
void PrevOrder(BTNode* root);//計算節點個數
int TreeSize(BTNode* root);

test.c:

#include"Tree.h"//創建一個新節點
BTNode* BuyNode(int x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc failed");exit(0);}newnode->data = x;newnode->left = newnode->right =NULL;return newnode;
}BTNode* creatBT()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}//前序遍歷
void PrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);//輸出當前數值PrevOrder(root->left);//然后遞歸進行PrevOrder(root->right);
}//中序遍歷
void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);//先遞歸，等到最后一個之后再進行輸出printf("%d ", root->data);InOrder(root->right);
}//后序遍歷
void BackOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}BackOrder(root->left);BackOrder(root->right);printf("%d ", root->data);
}//節點個數
int treesize(BTNode* root)
{if (root == NULL)return 0;else return treesize(root->left) + treesize(root->right) + 1 ;
}int TreeSize(BTNode* root)
{static int size = 0;//用局部靜態變量，只初始化一次。if (root == NULL){return 0;}else{++size;}TreeSize(root->left);TreeSize(root->right);return size;
}//求葉子節點個數
int TreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}int TreeHeigh(BTNode* root)
{if (root == NULL){return 0;}int leftheight = TreeHeigh(root->left);int rightheight = TreeHeigh(root->right);return leftheight > rightheight ?leftheight + 1 : rightheight + 1;
}int main()
{BTNode* root = creatBT();InOrder(root);printf("\n");int ret = TreeSize(root);std::cout << "TreeSize:" << ret << std::endl;ret = treesize(root);std::cout << "TreeSize:" << ret << std::endl;ret = TreeLeafSize(root);std::cout << "TreeLeafSize:" << ret << std::endl;int heigh = TreeHeigh(root);std::cout << "TreeHeigh:" << heigh << std::endl;return 0;
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/bicheng/16173.shtml
繁體地址，請注明出處：http://hk.pswp.cn/bicheng/16173.shtml
英文地址，請注明出處：http://en.pswp.cn/bicheng/16173.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！