數據結構 樹

定義

  • 樹是節點的優先集合

  • 度：孩子的數量，度為0 就是終端節點，不為零就是根節點
  • 有序樹：有順序，不可以替換
  • 無序樹：無順序，可以替換

  • 深度 和 樹的深度相反，第一層深度為1?
  • 樹的深度為 3

二叉樹

?

  • 滿二叉樹每一層的節點達到最大
  • 完全二叉樹? 從頭部開始，從左往右依次讀數，存在的數據和滿二叉樹的位置一一對應就是完全二叉樹
  • 滿二叉樹是完全二叉樹
  • 完全二叉樹不是滿二叉樹

二叉樹的存儲結構

順序存儲

鏈式存儲

代碼

數組二叉樹


/************************************************************************/
/*  樹課程要求：完成樹的基本操作1. 樹的創建和銷毀2. 樹中節點的搜索3. 樹中節點的添加與刪除4. 樹中節點的遍歷BOOL CreateTree(Tree **pTree, Node *pRoot);                           //創建樹void DestroyTree(Tree *pTree);                                        //銷毀樹Node *SearchNode(Tree *pTree, int nodeIndex);                         //根據索引尋找節點BOOL AddNode(Tree *pTree, int nodeIndex, int direction, Node *pNode); //添加節點BOOL DeleteNode(Tree *pTree, int nodeIndex, Node *pNode);             //刪除節點void PreorderTraversal(Tree *pTree);                                  //前(先)序遍歷演示void InorderTraversal(Tree *pTree);                                   //中序遍歷演示void PostorderTraversal(Tree *pTree);                                 //后序遍歷演示void TreeTraverse(Tree *pTree);                                       //遍歷七日成蝶-叩開數據結構之門（鏈表）關于數組與樹之間的算法轉換int    3 5 8 2 6 9 7        父親結點下標*2+1  該結點左  父親結點下標*2+2  該結點右3(0)5(1)            8(2)2(3)      6(4)   9(5)       7(6)
*/
/************************************************************************/#include <stdio.h>
#include <stdlib.h>#define MAX_NODE 20
#define LEFT  1
#define RIGHT 2
#define FALSE 0
#define TRUE  1
#define BOOL inttypedef struct tag_node
{int data;
}Node;typedef struct tag_tree
{Node *root;
}Tree;BOOL CreateTree(Tree **pTree, Node *pRoot)
{*pTree = (Tree *)malloc(sizeof(Tree));if(*pTree == NULL){return FALSE;}(*pTree)->root = (Node *)malloc(sizeof(Node) * MAX_NODE);if((*pTree)->root == NULL){free(*pTree);return FALSE;}for(int i = 0; i < MAX_NODE; i++){(*pTree)->root[i].data = 0;}(*pTree)->root[0] = *pRoot;  //(*pTree)->root[0].data = pRoot->data;return TRUE;
}void DestroyTree(Tree *pTree)
{free(pTree->root);pTree->root = NULL;free(pTree);pTree = NULL;
}Node *SearchNode(Tree *pTree, int nodeIndex)
{if(nodeIndex < 0 || nodeIndex >= MAX_NODE){return NULL;}if(pTree->root[nodeIndex].data == 0){return NULL;}else{return &(pTree->root[nodeIndex]);}
}//BOOL SearchNode(Tree *pTree, int nodeIndex, Node *node)
//{
//	if(nodeIndex < 0 || nodeIndex >= MAX_NODE)
//	{
//		return FALSE;
//	}
//
//	if(pTree->root[nodeIndex].data == 0)
//	{
//		return FALSE;
//	}
//	else
//	{
//		node->data = pTree->root[nodeIndex].data;  //*node = pTree->root[nodeIndex];
//
//		
//		return TRUE;
//	}
//}BOOL AddNode(Tree *pTree, int nodeIndex, int direction, Node *pNode)
{if(nodeIndex < 0 || nodeIndex >= MAX_NODE){return FALSE;}if(pTree->root[nodeIndex].data == 0){return FALSE;}pTree->root[nodeIndex * 2 + direction].data = pNode->data; //pTree->root[nodeIndex * 2 + direction] = *pNode;return TRUE;
}BOOL DeleteNode(Tree *pTree, int nodeIndex, Node *pNode)
{if(nodeIndex < 0 || nodeIndex >= MAX_NODE){return FALSE;}if(pTree->root[nodeIndex].data == 0){return FALSE;}*pNode = pTree->root[nodeIndex];pTree->root[nodeIndex].data = 0;return TRUE;
}void TreeTraverse(Tree *pTree)
{for(int i = 0; i < MAX_NODE; i++){printf("%d ", pTree->root[i].data);}
}int main(void)
{Tree *pTree = NULL;Node node = {3};Node node1 = {5};Node node2 = {8};Node node3 = {2};Node node4 = {6};Node node5 = {9};Node node6 = {7};CreateTree(&pTree, &node);AddNode(pTree, 0, LEFT, &node1);AddNode(pTree, 0, RIGHT, &node2);AddNode(pTree, 1, LEFT, &node3);AddNode(pTree, 1, RIGHT, &node4);AddNode(pTree, 2, LEFT, &node5);AddNode(pTree, 2, RIGHT, &node6);TreeTraverse(pTree);DestroyTree(pTree);system("pause");return 0;
}

鏈表 二叉樹


/************************************************************************/
/*  樹課程要求：完成樹的基本操作1. 樹的創建和銷毀2. 樹中節點的搜索3. 樹中節點的添加與刪除4. 樹中節點的遍歷BOOL CreateTree(Tree **pTree, Node *pRoot);                           //創建樹void DestroyTree(Tree *pTree);                                        //銷毀樹Node *SearchNode(Tree *pTree, int nodeIndex);                         //根據索引尋找節點BOOL AddNode(Tree *pTree, int nodeIndex, int direction, Node *pNode); //添加節點BOOL DeleteNode(Tree *pTree, int nodeIndex, Node *pNode);             //刪除節點void PreorderTraversal(Tree *pTree);                                  //前(先)序遍歷演示void InorderTraversal(Tree *pTree);                                   //中序遍歷演示void PostorderTraversal(Tree *pTree);                                 //后序遍歷演示七日成蝶-叩開數據結構之門（鏈表）七日成蝶-C語言編程基礎3 5 8 2 6 9 7        前序遍歷：3 5 2 6 8 9 7  中序遍歷：2 5 6 3 9 8 7后序遍歷：2 6 5 9 7 8 33(0)5(1)            8(2)2(3)      6(4)   9(5)       7(6)
*/
/************************************************************************/#include <stdio.h>
#include <stdlib.h>//#define MAX_NODE 20
#define LEFT  1
#define RIGHT 2
#define FALSE 0
#define TRUE  1
#define BOOL inttypedef struct tag_node
{int index;int data;struct tag_node *pLChild;struct tag_node *pRChild;struct tag_node *pParent;
}Node;typedef struct tag_tree
{Node *root;
}Tree;BOOL CreateTree(Tree **pTree, Node *pRoot);
void DestroyTree(Tree *pTree);
void DeleteNodeEx(Node *pNode, int direction);
Node *SearchNode(Tree *pTree, int nodeIndex);
Node *SearchNodeEx(Node *pNode, int nodeIndex);
BOOL AddNode(Tree *pTree, int nodeIndex, int direction, Node *pNode);
BOOL DeleteNode(Tree *pTree, int nodeIndex, Node *pNode);
void PreorderTraversal(Tree *pTree);
void PreorderTraversalNode(Node *pNode);
void InorderTraversal(Tree *pTree);
void InorderTraversalNode(Node *pNode);
void PostorderTraversal(Tree *pTree);
void PostorderTraversalNode(Node *pNode);BOOL CreateTree(Tree **pTree, Node *pRoot)
{*pTree = (Tree *)malloc(sizeof(Tree));if(*pTree == NULL){return FALSE;}(*pTree)->root = (Node *)malloc(sizeof(Node));if((*pTree)->root == NULL){free(*pTree);return FALSE;}*((*pTree)->root) = *pRoot; /*(*pTree)->root->data = pRoot->data;(*pTree)->root->index = pRoot->index;(*pTree)->root->pLChild = NULL;(*pTree)->root->pRChild = NULL;(*pTree)->root->pParent = NULL;*/return TRUE;
}void DestroyTree(Tree *pTree)
{DeleteNodeEx(pTree->root->pLChild, LEFT);DeleteNodeEx(pTree->root->pRChild, RIGHT);free(pTree->root);pTree->root = NULL;free(pTree);pTree = NULL;
}void DeleteNodeEx(Node *pNode, int direction)
{if(pNode != NULL){DeleteNodeEx(pNode->pLChild, LEFT);DeleteNodeEx(pNode->pRChild, RIGHT);if(direction == LEFT){pNode->pParent->pLChild = NULL;}if(direction == RIGHT){pNode->pParent->pRChild = NULL;}free(pNode);pNode = NULL;}}Node *SearchNode(Tree *pTree, int nodeIndex)
{return SearchNodeEx(pTree->root, nodeIndex);
}Node *SearchNodeEx(Node *pNode, int nodeIndex)
{if(pNode == NULL){return NULL;}if(pNode->index == nodeIndex){return pNode;}else{Node *temp = NULL;temp = SearchNodeEx(pNode->pLChild, nodeIndex);if(temp != NULL){return temp;}temp = SearchNodeEx(pNode->pRChild, nodeIndex);return temp;}
}//BOOL SearchNode(Tree *pTree, int nodeIndex, Node *node)
//{
//	if(nodeIndex < 0 || nodeIndex >= MAX_NODE)
//	{
//		return FALSE;
//	}
//
//	if(pTree->root[nodeIndex].data == 0)
//	{
//		return FALSE;
//	}
//	else
//	{
//		node->data = pTree->root[nodeIndex].data;  //*node = pTree->root[nodeIndex];
//
//		
//		return TRUE;
//	}
//}BOOL AddNode(Tree *pTree, int nodeIndex, int direction, Node *pNode)
{Node *temp = SearchNode(pTree, nodeIndex);Node *newNode = NULL;if(temp == NULL){return FALSE;}if(direction == LEFT){if(temp->pLChild == NULL){newNode = (Node *)malloc(sizeof(Node));if(newNode == NULL){return FALSE;}*newNode = *pNode;temp->pLChild = newNode;newNode->pParent = temp;}else{return FALSE;}}else{if(temp->pRChild == NULL){newNode = (Node *)malloc(sizeof(Node));if(newNode == NULL){return FALSE;}*newNode = *pNode;temp->pRChild = newNode;newNode->pParent = temp;}else{return FALSE;}}return TRUE;
}BOOL DeleteNode(Tree *pTree, int nodeIndex, Node *pNode)
{Node *temp = SearchNode(pTree, nodeIndex);if(temp == NULL){return FALSE;}*pNode = *temp;DeleteNodeEx(temp->pLChild, LEFT);DeleteNodeEx(temp->pRChild, RIGHT);if(temp->pParent->pLChild == temp){temp->pParent->pLChild = NULL;}if(temp->pParent->pRChild == temp){temp->pParent->pRChild = NULL;}free(temp);temp = NULL;return TRUE;
}//void TreeTraverse(Tree *pTree)
//{
//	for(int i = 0; i < MAX_NODE; i++)
//	{
//		printf("%d ", pTree->root[i].data);
//	}
//}void PreorderTraversal(Tree *pTree)
{PreorderTraversalNode(pTree->root);
}void PreorderTraversalNode(Node *pNode)
{if(pNode != NULL){printf("%d ", pNode->data);PreorderTraversalNode(pNode->pLChild);PreorderTraversalNode(pNode->pRChild);}
}void InorderTraversal(Tree *pTree)
{InorderTraversalNode(pTree->root);
}void InorderTraversalNode(Node *pNode)
{if(pNode != NULL){InorderTraversalNode(pNode->pLChild);printf("%d ", pNode->data);InorderTraversalNode(pNode->pRChild);}
}void PostorderTraversal(Tree *pTree)
{PostorderTraversalNode(pTree->root);
}void PostorderTraversalNode(Node *pNode)
{if(pNode != NULL){PostorderTraversalNode(pNode->pLChild);PostorderTraversalNode(pNode->pRChild);printf("%d ", pNode->data);}
}int main(void)
{Tree *pTree = NULL;Node node = {0, 3, NULL, NULL, NULL};Node node1 = {1, 5, NULL, NULL, NULL};Node node2 = {2, 8, NULL, NULL, NULL};Node node3 = {3, 2, NULL, NULL, NULL};Node node4 = {4, 6, NULL, NULL, NULL};Node node5 = {5, 9, NULL, NULL, NULL};Node node6 = {6, 7, NULL, NULL, NULL};CreateTree(&pTree, &node);AddNode(pTree, 0, LEFT, &node1);AddNode(pTree, 0, RIGHT, &node2);AddNode(pTree, 1, LEFT, &node3);AddNode(pTree, 1, RIGHT, &node4);AddNode(pTree, 2, LEFT, &node5);AddNode(pTree, 2, RIGHT, &node6);//PreorderTraversal(pTree);//InorderTraversal(pTree);PostorderTraversal(pTree);DestroyTree(pTree);system("pause");return 0;
}

?

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

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

相關文章

英語口語 Week15 TuesDay

英語口語 Week15 TuesDay

英語文章 One day, when Bella was doing sports in the school yard, the squirrel fled out of her sleeve. Threading its way through a considerable number of people, the squirrel disappeared in the distance After a sequence of movements, it hopped onto the ar…
閱讀更多...
c++面向對象高級編程 學習十四 引用

c++面向對象高級編程 學習十四 引用

文章目錄referencereference的常見用途reference 變量有三種形式&#xff1a;值&#xff0c;指針&#xff0c;引用 int x0; //值 int* p&x;//指向整型的指針&#xff0c;地址&#xff0c;指針在之后的程序中可以指向其他變量 int& rx;//引用&#xff0c;此處表示 r代…
閱讀更多...
google瀏覽器 隱藏功能開啟

google瀏覽器 隱藏功能開啟

網址 chrome://flags/ 1&#xff0c;多線程下載 2&#xff0c;暗黑模式3&#xff0c;標簽縮略圖4&#xff0c;PWA 漸進式web應用 網頁即應用5&#xff0c;閱讀模式&#xff0c;排除廣告&#xff0c;點擊閱讀模式去除干擾chrome://net-internals6&#xff0c;解決有問題的代理IP…
閱讀更多...
英語口語Week 15 Wednesday

英語口語Week 15 Wednesday

英語文章 Accomplishing the task assigned by the teacher; Julia rushed out. Squatting at the gate and playing with the squirrel, Bella waved at the sight of Julia and yelled out here" . Julia ran quickly towards them, pointed at the squirrel and asked…
閱讀更多...
c++面向對象高級編程 學習十五 組合繼承關系下的構造和析構

c++面向對象高級編程 學習十五 組合繼承關系下的構造和析構

文章目錄繼承關系組合關系繼承和組合繼承關系 構造由內而外&#xff0c;析構由外而內&#xff0c;內即是父類 組合關系 A擁有B&#xff0c; 構造由內而外&#xff0c;析構由外而內&#xff0c;內即是B 繼承和組合 構造和析構順序如圖&#xff1a;
閱讀更多...
英語口語Week16 Wednesday

英語口語Week16 Wednesday

英語文章 Recently my friend received a gift from her boyfriend - a very expensive bracelet. But the substance of her response left us in astonishment - she didn’t attend to the exquisiteness(of the gift and wanted to return it to him In terms of salary, …
閱讀更多...
C++ 查漏補缺

C++ 查漏補缺

特性關系 C語言面向過程C面向過程 面向對象(封裝 繼承 多態)C具備C語言的全部特性的基礎上&#xff0c;并且支持更多新的特性 內存泄露 申請內存&#xff0c;沒有釋放申請 malloc new釋放 free deleteProcessExplorer查看內存是否釋放 代碼移植 將生成的exe運行在別的平臺&…
閱讀更多...
c++面向對象高級編程 學習十六 vptr和vtbl

c++面向對象高級編程 學習十六 vptr和vtbl

當一個類中有一個或多個虛函數時&#xff0c;內存中會多一個虛指針&#xff08;vptr&#xff0c;virtual pointer&#xff09;&#xff0c;指向一個虛表&#xff08;vtbl&#xff0c;virtual table&#xff09; 父類有虛函數&#xff0c;則子類一定有虛函數 在下圖示意圖中&a…
閱讀更多...
英語口語Week16 Thursday

英語口語Week16 Thursday

英語文章 It is an impossibility that everything runs smoothly in everyday life. Where there is trouble, there could be anxiety.Anxiety is a common phenomenon; you are not the only one carrying it. But, it could be somewhat poisonous if you don’t let it o…
閱讀更多...
c++面向對象高級編程 學習十七 const, new, delete

c++面向對象高級編程 學習十七 const, new, delete

文章目錄常量成員函數new和delete常量成員函數 常量成員函數是不改變成員數據。 當成員函數的const和non-const版本同時存在時&#xff0c;const object只能調用const版本&#xff0c;non-const object只能調用non-const版本。因此&#xff0c;可以看出&#xff0c;const是函…
閱讀更多...
codeforces 467A-C語言解題報告

codeforces 467A-C語言解題報告

題目網址 題目解析 1.輸入n個房間,再每一行輸入現有的p個人,和一共可以容納的q人數,如果q-p>2則計數1 代碼 #include<stdio.h> #include<stdlib.h> #include<string.h>int main() {int n0,p0,q0;int count0,i;scanf("%d",&n);for(i0;i&…
閱讀更多...
使用引用的方式交換數據的數值

使用引用的方式交換數據的數值

#include <iostream>void swap(int &a,int &b){a ^ b;b ^ a;a ^ b; } int main(){int num1 10;int num2 20;swap(num1,num2);std::cout << num1 << std::endl;std::cout << num2 << std::endl; }
閱讀更多...
C++STL與泛型編程 侯捷 （1）

C++STL與泛型編程 侯捷 （1）

泛型編程&#xff08;Generic Programming&#xff0c;GP&#xff09;&#xff0c;就是使用template&#xff08;模板&#xff09;為主要工具來編寫程序。 重要網頁&#xff1a; http://www.cplusplus.com/ https://en.cppreference.com/w/ http://gcc.gnu.org/
閱讀更多...
codeforces 136A-C語言解題報告

codeforces 136A-C語言解題報告

題目網址 題目解析 1.輸入每個人給第幾個人發禮物(1–n), 輸出每個人收到第幾個人發的禮物 2.因為1–n,所以for循環也使用1–n output[input[j]]j; 代碼 #include<stdio.h> #include<stdlib.h> #include<string.h> int main() {int n0;scanf("%d&…
閱讀更多...
static內容相關介紹學習

static內容相關介紹學習

說一下static關鍵字的作用 當程序執行到函數內部定義的變量時&#xff0c;編譯器為它在棧上分配空間&#xff0c;函數在棧上分配的空間在此函數執行結束時會釋放掉&#xff0c;這樣就產生了一個問題: 如果想將函數中此變量的值保存至下一次調用時&#xff0c;如何實現&#xf…
閱讀更多...
C++STL與泛型編程（2） 第一個C++ STL Application

C++STL與泛型編程（2） 第一個C++ STL Application

文章目錄STL六大部件STL六大部件代碼示例時間復雜度前閉后開區間auto關鍵字的用法STL六大部件 容器 分配器 算法 迭代器 適配器 仿函數 容器要放東西&#xff0c;東西要占用內存&#xff0c;分配器可支持容器解決內存問題。算法處理容器中的數據。迭代器是容器和算法之間的橋…
閱讀更多...
codeforces 344A-C語言解題報告

codeforces 344A-C語言解題報告

題目網址 題目解析 1.有10和01兩種,同性相斥,異性相吸 2.01是1,使用pre去記錄前一個,寫出所有情況 0110 1001 分為一組 代碼 #include<stdio.h> #include<stdlib.h> #include<string.h> int main() {int n0;int i0;int c0;int pre-1;int count0;scanf(&…
閱讀更多...
JAVA 程序執行進行計時，用于驗證程序執行的時間

JAVA 程序執行進行計時，用于驗證程序執行的時間

package com.example.algorithm.demo.class1;public class Hello {public static void main(String[] args) {long start System.nanoTime();//程序開始時間System.out.println(start);System.out.println("Hello");long end System.nanoTime();System.out.println…
閱讀更多...
C++STL與泛型編程__侯捷視頻_學習博客_總目錄

C++STL與泛型編程__侯捷視頻_學習博客_總目錄

CSTL與泛型編程 侯捷 &#xff08;1&#xff09;: c重要網站相關 CSTL與泛型編程&#xff08;2&#xff09; 第一個C STL Application&#xff1a; STL六大部件代碼示例&#xff0c;容器前閉后開區間&#xff0c;auto關鍵字的用法示例 CSTL與泛型編程&#xff08;3&#xff0…
閱讀更多...
codeforces 1030A-C語言解題報告

codeforces 1030A-C語言解題報告

題目網址 題目解析 1.輸入一串數字,如果有1就輸出HARD,否則輸出EASY 2.勿忘& 代碼 #include<stdio.h> #include<stdlib.h> #include<string.h> int main() {int n0,i0;int num0;int count0;scanf("%d",&n);for(i;i<n;i){scanf(&quo…
閱讀更多...
最新文章

Copyright @ 2022~2023