主頁 >  其他 > 研究樹為什么要重點研究二叉樹？一次性搞懂二叉樹和樹的初階知識

研究樹為什么要重點研究二叉樹？一次性搞懂二叉樹和樹的初階知識

2021-10-16 08:54:15 其他

??本文記錄了一些有關樹這種資料結構相對初階的知識，
??如果你是已經有一定的樹這種資料結構的基礎想知道為什么研究樹要重點研究二叉樹，可以去看目錄 13、樹、森林與二叉樹的轉化；如果你是和我一樣的小白想循序了解一些樹的有關知識，可以從頭看起，

文章目錄

  • ?1.樹的定義
  • ?2.結點的度 葉結點 樹的度
    • 🍛1. 結點的度(Degree)
    • 🍛2. 葉結點(Leaf)
    • 🍛3. 樹的度
  • ?3.結點間的關系
  • ?4.樹的其他概念
  • ?5.樹的存盤結構
    • 🥘1. 雙親表示法
    • 🥘2. 孩子表示法
    • 🥘3. 孩子兄弟表示法
  • ?6.二叉樹的存盤結構
    • 🍲1.順序存盤
    • 🍲2.鏈式存盤
  • ?7.二叉樹的遍歷
    • 🥫1.前序遍歷
    • 🥫2.中序遍歷
    • 🥫3.后序遍歷
    • 🥫4.層次遍歷
  • ?8. 二叉樹的遍歷演算法
    • 🍜1.前序遍歷演算法
    • 🍜2.中序遍歷演算法
    • 🍜3.后序遍歷演算法
  • ?9. 二叉樹遍歷結果的意義
  • ?10. 二叉樹的建立
  • ?11. 二叉樹的匯總
  • ?12.線索二叉樹
    • 🌳1.提出背景
    • 🌳2.線索二叉樹的存盤結構
    • 🌳3.中序序列線索二叉樹的建立
      • 🎃3.1 建立二叉樹
      • 🎃3.2 二叉樹線索化
      • 🎃3.3 插入頭結點
      • 🎃3.4 遍歷線索二叉樹
    • 🌳4.前序序列線索二叉樹的建立
    • 🌳5.后序序列線索二叉樹的建立（遍歷函式待研究）
    • 🌳6. 線索二叉樹的匯總
  • ?13.樹、森林與二叉樹的轉化
    • 🌴1.樹轉化為二叉樹
    • 🌴2.森林轉化為二叉樹
    • 🌴3.二叉樹轉化為樹
    • 🌴4.二叉樹轉化為森林
    • 🌴5.樹與森林的遍歷
      • 🔥5.1 樹的遍歷
        • 🐱5.1.1 先根遍歷
        • 🐱5.1.2 后根遍歷
      • 🔥5.2 森林的遍歷
        • 🐬5.2.1 前序遍歷
        • 🐬5.2.2 后序遍歷

?1.樹的定義

??樹是n個節點的有限集，n=0時稱為空樹，在任意一顆非空樹中：

  1. 有且僅有一個特定的稱為根(Root)的結點；
  2. 當n>1時，其余結點可以分為m(m>0)個互不相交的有限集T1、T2、…、Tm,其中每個集合本身又是一顆樹，并且稱為根的子樹(SubTree)，

??這個定義用了遞回的概念，在樹的知識中，這種定義方法非常常見，

?2.結點的度 葉結點 樹的度

🍛1. 結點的度(Degree)

??結點擁有的子樹數稱為結點的度，

🍛2. 葉結點(Leaf)

??度為0的結點.

🍛3. 樹的度

??樹的度是樹內部各結點的度的最大值，

?3.結點間的關系

??節點的子樹的根稱為節點的孩子（Child），相應的，該節點稱為孩子的雙親，

??同一個雙親的孩子之間互稱兄弟，

??結點的祖先是從根到該結點所經分支上的所有結點，

??以某結點為根的子樹中的任一節點都稱為該結點的子孫，

?4.樹的其他概念

結點的層次

如果將樹中結點的各子樹看成從左至右是有次序的，不能互換的，則稱該樹為有序樹，否則稱為無序樹，

森林是m課互不相交的樹的集合，

?5.樹的存盤結構

🥘1. 雙親表示法

//雙親表示法
#define MAXSIZE 100//最多的節點個數
typedef int TDatatype;//方便后續修改
//單個結點
typedef struct {
	TDatatype data;//資料域
	int parent;//雙親域
	int firstchild;//長子
	int rightsub;//右兄弟域
}Node;
//具體要怎么設計節點中的內容可以根據基于該存盤結構的運算是否合適是否方便來決定，

//整個樹的空間
typedef struct {
	int root;//根的位置
	int n;//節點數
	Node nodes[MAXSIZE];
}PTree;

🥘2. 孩子表示法

#define MAXSIZE 100//本樹的最多的節點個數

//樹的孩子表示法

//首先用一個鏈表表示樹中一個結點的所有孩子節點
//這個鏈表的節點（非頭結點）
typedef struct NODE{
	int child;
	struct NODE* next;
}*childptr;

//這個鏈表的頭結點的內容是這個節點的資料和它的第一個孩子

typedef struct {
	TDatatype data;
	childptr firstchild;
}treeelement;

//把這個頭結點再組成一個陣列，
typedef struct {
	treeelement nodes[MAXSIZE];
	int root;
	int n;//節點數
}CTree;

🥘3. 孩子兄弟表示法

/孩子兄弟表示法

//觀察發現，對于一個二叉樹來說，他的長子和右兄弟如果存在那么一定唯一 所以我們可以這樣設計

typedef struct CBNode {
	TDatatype data;
	CBNode* firstchild;
	CBNode* rightbro;
	CBNode* parent;//加這個方便搜索自己的雙親
}CBTnode,*CBTree;

//這樣的好處是我們把一個復雜的書變成了一棵二叉樹 就可以充分的利用二叉樹的性質來計算了

?6.二叉樹的存盤結構

🍲1.順序存盤

按照補全程對應完全二叉樹的號來存，不存在的位置則存空，由于太浪費空間，所以一般只用來存完全二叉樹，

🍲2.鏈式存盤

存自己的左孩子，右孩子，如果需要快速查雙親資訊則再加一個雙親域

//二叉樹的鏈式存盤

typedef struct BiTNode {
	TDatatype data;
	BiTNode* leftchild;
	BiTNode* rightchild;
	BiTNode* parent;
}BiTNode,*BiTree;

?7.二叉樹的遍歷

??二叉樹的遍歷是指從根節點出發，按照某種次序一次訪問二叉樹中的所有結點，使得每個節點被訪問一次且僅被訪問一次，

🥫1.前序遍歷

??規則是若二叉樹為空，則空操作并回傳；否則先訪問根節點，然后前序遍歷左子樹，再前序遍歷右子樹，

在這里插入圖片描述

🥫2.中序遍歷

??規則是若樹為空，則空操作回傳；否則從根節點開始，中序遍歷根節點的左子樹，然后訪問根節點，然后中序遍歷右子樹，

在這里插入圖片描述

🥫3.后序遍歷

??規則是若樹是空的，那么就空操作且回傳，否則從左到右先葉子后節點的方式遍歷左右子樹，最后是訪問根節點，

在這里插入圖片描述

🥫4.層次遍歷

??從上到下，從左到右依次遍歷，

在這里插入圖片描述

?8. 二叉樹的遍歷演算法

🍜1.前序遍歷演算法

void PreOrderTraverse(BiTree T)
{
	if (T == NULL)
	{
		return;
	}
	printf("%d ", T->data);
	PreOrderTraverse(T->leftchild);
	PreOrderTraverse(T->rightchild);
}

🍜2.中序遍歷演算法

void InOrderTraverse(BiTree T)
{
	if (T == NULL)
	{
		return;
	}
	InOrderTraverse(T->leftchild);
	printf("%d ", T->data);
	InOrderTraverse(T->rightchild);
}

🍜3.后序遍歷演算法

void PostOrderTraverse(BiTree T)
{
	if (T == NULL)
	{
		return;
	}
	PostOrderTraverse(T->leftchild);
	PostOrderTraverse(T->rightchild);
	printf("%c ", T->data);
}

??這個所謂的序，就是實際“訪問”節點的順序在訪問結點對應左子樹 訪問結點對應的右子樹的前面、中間、后面，

?9. 二叉樹遍歷結果的意義

  • 已知前序遍歷序列和中序遍歷序列，可以唯一確定一顆二叉樹，
  • 已知中序遍歷序列和后續遍歷序列，可以唯一確定一顆二叉樹，

??前序和后序在本質上都是將父節點與子結點進行分離，但并沒有指明左子樹和右子樹的能力，（沒有說明到哪里左子樹遍歷結束，到哪里右子樹遍歷結束）因此得到這兩個序列只能明確父子關系，而不能確定一個二叉樹，

??已知前序排列或者已知后續排列某種程度上都是會知道根是誰，前序會知道誰是自己的左孩子，后序會知道誰是自己的右孩子，但它們都沒有嚴格指明左子樹遍歷到哪里結束，右子樹遍歷到哪里結束，而再加上中序排列會知道左子樹在哪里遍歷結束（因為會列印自己的節點），會知道右子樹在哪里開始遍歷（因為知道根），會知道右子樹在哪里結束（因為中序列印完右子樹會列印自己雙親節點，而這某種程度上是一種根，通過前序和后續都可以知道），因此我們知道了根在那和左右子樹在那開始在哪結束，然后每個子樹可以這樣遞回下去，因此就唯一確定了一顆子樹，

??已知前序遍歷序列和后序遍歷序列，無法唯一確定一顆二叉樹，

??如前序遍歷結果ABC，后序遍歷序列CBA

在這里插入圖片描述

?10. 二叉樹的建立

??我們利用了一個原理，拓展二叉樹可以用先序或后序序列唯一確定一顆二叉樹，而中序不可以

Proof:

??所謂拓展二叉樹，就是保證除’#‘結點外，每個節點都有左孩子和右孩子，如果缺少左孩子或右孩子，就用’#'補上，

??對于先序排列，我根據先序排列會知道誰是根，誰是我的左孩子，加上拓展二叉樹后，我會知道左子樹在哪里結束（因為結尾肯定是##)，也就知道了右子樹在哪開始（即右孩子的位置），然后也會知道右子樹的結束位置（##），以此遞回，我就會唯一確定整顆子樹，

??對于中序排列，其實我的拓展二叉樹已經交待了區分左右子樹的方法，但是你不能告訴我根，所以我們確定不了

??對于后序排列，我根據后序排列知道誰是根，誰是我的右孩子，加上了拓展二叉樹后，我會知道右子樹在哪里結束（結尾肯定是從右往左數經過兩個##）,也就知道了左子樹在哪里開始（即左孩子的位置），也會知道左子樹結束的位置（##),以此遞回，我就會唯一確定整顆二叉樹，

所以我們考慮用拓展二叉樹的先序排列創建一棵二叉樹，

int index = 0;//用一個全域變數來表示遍歷到那個序列的哪個位置了
void CreateBiTree(BiTree* T,char* arr)
{
	char ch = arr[index++];
	if (ch == '#')
	{
		*T = NULL;
	}
	else
	{
		BiTree tmp = (BiTree)malloc(sizeof(BiTNode));
		if (tmp == NULL)
		{
			printf("malloc fault\n");
			exit(-1);
		}
		*T = tmp;
		(*T)->data = ch;
		CreateBiTree(&((*T)->leftchild),arr);
		CreateBiTree(&((*T)->rightchild),arr);
	}
}

?11. 二叉樹的匯總

//BiTree.h
//二叉樹的鏈式存盤

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 1000
typedef char TDatatype;
typedef struct BiTNode {
	TDatatype data;
	struct BiTNode* leftchild;
	struct BiTNode* rightchild;
	struct BiTNode* parent;
}BiTNode,*BiTree;

//前序遍歷演算法
void PreOrderTraverse(BiTree T);
//中序遍歷演算法
void InOrderTraverse(BiTree T);
//后續遍歷演算法
void PostOrderTraverse(BiTree T);
//利用拓展二叉樹(#法)的先序排列確定一棵二叉樹
void CreateBiTree(BiTree* T,char* arr);
//int index = 0;//用來表示這個先序序列走到哪一位了

//BiTree.c
#include "BiTree.h"

void PreOrderTraverse(BiTree T)
{
	if (T == NULL)
	{
		return;
	}
	printf("%c ", T->data);
	PreOrderTraverse(T->leftchild);
	PreOrderTraverse(T->rightchild);
}

void InOrderTraverse(BiTree T)
{
	if (T == NULL)
	{
		return;
	}
	InOrderTraverse(T->leftchild);
	printf("%c ", T->data);
	InOrderTraverse(T->rightchild);
}

void PostOrderTraverse(BiTree T)
{
	if (T == NULL)
	{
		return;
	}
	PostOrderTraverse(T->leftchild);
	PostOrderTraverse(T->rightchild);
	printf("%c ", T->data);
}

int index = 0;//用一個全域變數來表示遍歷到那個序列的哪個位置了
void CreateBiTree(BiTree* T,char* arr)
{
	char ch = arr[index++];
	if (ch == '#')
	{
		*T = NULL;
	}
	else
	{
		BiTree tmp = (BiTree)malloc(sizeof(BiTNode));
		if (tmp == NULL)
		{
			printf("malloc fault\n");
			exit(-1);
		}
		*T = tmp;
		(*T)->data = ch;
		CreateBiTree(&((*T)->leftchild),arr);
		CreateBiTree(&((*T)->rightchild),arr);
	}
}

/

#include "BiTree.h"

void test1()
{
	BiTree testree;
	printf("請輸入這棵二叉樹的拓展二叉樹(#法)的先序排列\n");
	char arr[2 * MAXSIZE + 2] = { 0 };
	scanf("%s", arr);
	CreateBiTree(&testree,arr);
	PreOrderTraverse(testree);
	printf("\n");
	InOrderTraverse(testree);
	printf("\n");
	PostOrderTraverse(testree);
}


int main()
{
	test1();
	return 0;
}

?12.線索二叉樹

🌳1.提出背景

typedef char TDatatype;
typedef struct BiTNode {
	TDatatype data;
	struct BiTNode* leftchild;
	struct BiTNode* rightchild;
	struct BiTNode* parent;
}BiTNode,*BiTree;

??觀察我們的二叉樹的節點結構，其實有很多空間都被我們浪費了，因為有的節點沒有左孩子，有的結點沒有右孩子，葉結點沒有左右孩子，我們是否可以利用一下空閑的空間呢，比如我們讓空閑的左孩子指標指向創建當前二叉樹所用遍歷序列的前繼，讓空閑的右孩子指標指向創建當前二叉樹的遍歷序列的后繼，

??但是，我們還是有一些問題，我們怎么確定這個右(左)孩子指標指的是自己的右（左）孩子還是后繼（前繼）呢？

??我們可以再創建兩個布爾量，0表示此指標是正常指向自己的孩子的，1表示此指標是指向自己的后繼或前繼，為了方便，干碎用一個列舉變數，Link（鏈）表示此指標是指向自己孩子的鏈，Thread表示此指標是指向自己前繼或后繼的線，

🌳2.線索二叉樹的存盤結構

typedef enum {
	Link,
	Thread
}PointerTag;

typedef struct BiThrNode {
	TDatatype data;
	struct BiThNode* leftchild;
	struct BiThNode* rightchild;
	PointerTag LTag;
	PointerTag RTag;
}BiThrNode,*BiThrTree;

🌳3.中序序列線索二叉樹的建立

🎃3.1 建立二叉樹

int index1 = 0;
void createBiThrTree(BiThrTree* T, char* arr)
{
	char ch = arr[index1++];
	if (ch == '#')
	{
		*T = NULL;
	}
	else
	{
		BiThrTree tmp = (BiThrTree)malloc(sizeof(BiThrNode));
		if (tmp == NULL)
		{
			printf("malloc fault\n");
			exit(-1);
		}
		*T = tmp;
		(*T)->data = ch;
		(*T)->LTag = Link;
		(*T)->RTag = Link;
		createBiThrTree(&((*T)->leftchild), arr);
		createBiThrTree(&((*T)->rightchild), arr);
	}
}

🎃3.2 二叉樹線索化

extern BiThrTree pre;

//把二叉樹按中序遍歷序列線索化
void InThreading(BiThrTree p)
{
	if (p)
	{
		InThreading(p->leftchild);
		if (!p->leftchild)
		{
			p->LTag = Thread;
			p->leftchild = pre;
		}
		if (pre!=NULL)
		{
			if (!pre->rightchild)
			{
				pre->RTag = Thread;
				pre->rightchild = p;
			}
		}
		pre = p;
		InThreading(p->rightchild);
	}

}

🎃3.3 插入頭結點

//為二叉樹插入頭結點
void addhead_IN(BiThrTree* T)
{
	BiThrTree head = (BiThrTree)malloc(sizeof(BiThrNode));
	head->LTag = Link;
	head->RTag = Thread;
	head->leftchild = (*T);
	BiThrTree p = *T;
	//先把中序遍歷的第一個結點的前繼指標指向頭結點
	while (p->LTag == Link)
	{
		p = p->leftchild;
	}
	p->leftchild = head;
	//下面我們讓p指向中序遍歷序列的最后一個結點
	while (p->rightchild != NULL)
	{
		while (p->LTag == Link)
			p = p->leftchild;
		while (p->RTag == Thread && p->rightchild != NULL)
		{
			p = p->rightchild;
		}
		p = p->rightchild;//進入它的右子樹
	}
	p->rightchild = head;
	p->RTag = Thread;
	head->rightchild = p;
	*T = head;
}

🎃3.4 遍歷線索二叉樹

//中序遍歷線索二叉樹
void InOrderTraverse_Thr(BiThrTree T)
{
	BiThrTree p;
	p = T->leftchild;
	if (p == NULL)
	{
		printf("線索二叉樹為空\n");
		return;
	}
	while (p != T)
	{
		while (p->LTag == Link)
			p = p->leftchild;
		printf("%c ", p->data);
		while (p->RTag == Thread && p != T)
		{
			p = p->rightchild;
			if (p == T)
			{
				break;
			}
			printf("%c ", p->data);
		}
		//到這里說明左子樹遍歷完了 該進入右子樹了
		if (p != T)
		{
			p = p->rightchild;
		}
	}
}

🌳4.前序序列線索二叉樹的建立

extern BiThrTree pre1;
//按照前序遍歷序列線索化二叉樹
void PreThreading(BiThrTree p)
{
	if (p != NULL)
	{
		if (p->leftchild == NULL)
		{
			p->LTag = Thread;
			p->leftchild = pre1;
		}
		if (pre1 != NULL)
		{
			if (pre1->rightchild == NULL)
			{
				pre1->RTag = Thread;
				pre1->rightchild = p;
			}
		}
		pre1 = p;
		if (p->LTag == Link)
		{
			PreThreading(p->leftchild);
		}
		if (p->RTag == Link)
		{
			PreThreading(p->rightchild);
		}
	}
}

//插頭結點
void addhead_Pre(BiThrTree* T)
{
	BiThrTree head = (BiThrTree)malloc(sizeof(BiThrNode));
	if (head == NULL)
	{
		printf("malloc fault\n");
		return;
	}
	head->LTag = Link;
	head->leftchild = *T;
	head->RTag = Thread;
	BiThrTree p = *T;
	while (p->rightchild != NULL)
	{
		while (p->LTag==Link)
			p = p->leftchild;
		while (p->RTag == Thread && p->rightchild!=NULL)
			p = p->rightchild;
	}
	p->RTag = Thread;
	head->rightchild = p;
	p->rightchild = head;
	*T = head;
}

//前序遍歷線索二叉樹
void PreOrderTraverse_Thr(BiThrTree T)
{
	BiThrTree p = T->leftchild;
	printf("%c ", p->data);
	while (p != T)
	{
		//printf("%c ", p->data);
		while (p->LTag == Link)
		{
			p = p->leftchild;
			printf("%c ", p->data);
		}
		while (p->RTag == Thread && p!=T)
		{
			p = p->rightchild;
			if (p != T)
			{
				printf("%c ", p->data);
			}
		}
	}
}

🌳5.后序序列線索二叉樹的建立（遍歷函式待研究）

extern BiThrTree pre2;

void PostThreading(BiThrTree p)
{
	if (p)
	{
		PostThreading(p->leftchild);
		PostThreading(p->rightchild);
		if (p->leftchild == NULL)
		{
			p->LTag = Thread;
			p->leftchild = pre2;
		}
		if (pre2 != NULL)
		{
			if (pre2->rightchild == NULL)
			{
				pre2->RTag = Thread;
				pre2->rightchild = p;
			}
		}
		pre2 = p;
	}
}

void addhead_Post(BiThrTree* T)
{
	BiThrTree head = (BiThrTree)malloc(sizeof(BiThrNode));
	if (head == NULL)
	{
		printf("malloc fault\n");
		return;
	}
	head->LTag = Link;
	head->leftchild = *T;
	head->RTag = Thread;
	BiThrTree p = *T;
	while (p->LTag == Link)
		p = p->leftchild;
	p->LTag = Thread;
	p->leftchild = head;
	head->rightchild = *T;
	if ((*T)->rightchild == NULL)
	{
		(*T)->rightchild = head;
	}
	*T = head;
}

void PostOrderTraverse_Thr(BiThrTree T)
//開發失敗 寄了
{
	BiThrTree p;
	p = T->leftchild;
	if (p == NULL)
	{
		printf("線索二叉樹為空\n");
		return;
	}
	while (p != T)
	{
		while (p->LTag == Link)
			p = p->leftchild;
		printf("%c ", p->data);
		while (p->RTag == Thread && p != T)
		{
			p = p->rightchild;
			if (p == T)
			{
				break;
			}
			printf("%c ", p->data);
		}
		//到這里說明左子樹遍歷完了 該進入右子樹了
		if (p != T)
		{
			p = p->rightchild;
		}
	}
}

🌳6. 線索二叉樹的匯總

//BiThrTree.h
#pragma once
//線索二叉樹
typedef enum {
	Link,
	Thread
}PointerTag;

typedef struct BiThrNode {
	TDatatype data;
	struct BiThNode* leftchild;
	struct BiThNode* rightchild;
	PointerTag LTag;
	PointerTag RTag;
}BiThrNode,*BiThrTree;

void createBiThrTree(BiThrTree* T,char* arr);

void print(BiThrTree T);
//按照中序遍歷序列給把二叉樹線索化
BiThrTree pre;

void InThreading(BiThrTree p);

void addhead_IN(BiThrTree* T);

void InOrderTraverse_Thr(BiThrTree T);

//按照前序遍歷序列把二叉樹線索化
BiThrTree pre1;

void PreThreading(BiThrTree p);

void addhead_Pre(BiThrTree* T);
//中序遍歷線索二叉樹
void PreOrderTraverse_Thr(BiThrTree T);

//按照后序遍歷序列把二叉樹線索化

BiThrTree pre2;

//按照拓展二叉樹的后續遍歷序列創建二叉樹
void createBiThrTree_Post(BiThrTree* T, char* str);//待研究

void PostThreading(BiThrTree p);

void addhead_Post(BiThrTree* T);

void PostOrderTraverse_Thr(BiThrTree T);//待研究


//BiThrTree.c

#include "BiThrTree.h"

int index1 = 0;
void createBiThrTree(BiThrTree* T, char* arr)
{
	char ch = arr[index1++];
	if (ch == '#')
	{
		*T = NULL;
	}
	else
	{
		BiThrTree tmp = (BiThrTree)malloc(sizeof(BiThrNode));
		if (tmp == NULL)
		{
			printf("malloc fault\n");
			exit(-1);
		}
		*T = tmp;
		(*T)->data = ch;
		(*T)->LTag = Link;
		(*T)->RTag = Link;
		createBiThrTree(&((*T)->leftchild), arr);
		createBiThrTree(&((*T)->rightchild), arr);
	}
}

void print(BiThrTree T)
{
	if (T == NULL)
	{
		return;
	}
	printf("%c ", T->data);
	print(T->leftchild);
	print(T->rightchild);
}

extern BiThrTree pre;

//把二叉樹按中序遍歷序列線索化
void InThreading(BiThrTree p)
{
	if (p)
	{
		InThreading(p->leftchild);
		if (!p->leftchild)
		{
			p->LTag = Thread;
			p->leftchild = pre;
		}
		if (pre!=NULL)
		{
			if (!pre->rightchild)
			{
				pre->RTag = Thread;
				pre->rightchild = p;
			}
		}
		pre = p;
		InThreading(p->rightchild);
	}

}




//為二叉樹插入頭結點
void addhead_IN(BiThrTree* T)
{
	BiThrTree head = (BiThrTree)malloc(sizeof(BiThrNode));
	head->LTag = Link;
	head->RTag = Thread;
	head->leftchild = (*T);
	BiThrTree p = *T;
	//先把中序遍歷的第一個結點的前繼指標指向頭結點
	while (p->LTag == Link)
	{
		p = p->leftchild;
	}
	p->leftchild = head;
	//下面我們讓p指向中序遍歷序列的最后一個結點
	while (p->rightchild != NULL)
	{
		while (p->LTag == Link)
			p = p->leftchild;
		while (p->RTag == Thread && p->rightchild != NULL)
		{
			p = p->rightchild;
		}
		p = p->rightchild;//進入它的右子樹
	}
	p->rightchild = head;
	p->RTag = Thread;
	head->rightchild = p;
	*T = head;
}

//中序遍歷線索二叉樹
void InOrderTraverse_Thr(BiThrTree T)
{
	BiThrTree p;
	p = T->leftchild;
	if (p == NULL)
	{
		printf("線索二叉樹為空\n");
		return;
	}
	while (p != T)
	{
		while (p->LTag == Link)
			p = p->leftchild;
		printf("%c ", p->data);
		while (p->RTag == Thread && p != T)
		{
			p = p->rightchild;
			if (p == T)
			{
				break;
			}
			printf("%c ", p->data);
		}
		//到這里說明左子樹遍歷完了 該進入右子樹了
		if (p != T)
		{
			p = p->rightchild;
		}
	}
}

extern BiThrTree pre1;
//按照前序遍歷序列線索化二叉樹
void PreThreading(BiThrTree p)
{
	if (p != NULL)
	{
		if (p->leftchild == NULL)
		{
			p->LTag = Thread;
			p->leftchild = pre1;
		}
		if (pre1 != NULL)
		{
			if (pre1->rightchild == NULL)
			{
				pre1->RTag = Thread;
				pre1->rightchild = p;
			}
		}
		pre1 = p;
		if (p->LTag == Link)
		{
			PreThreading(p->leftchild);
		}
		if (p->RTag == Link)
		{
			PreThreading(p->rightchild);
		}
	}
}

//插頭結點
void addhead_Pre(BiThrTree* T)
{
	BiThrTree head = (BiThrTree)malloc(sizeof(BiThrNode));
	if (head == NULL)
	{
		printf("malloc fault\n");
		return;
	}
	head->LTag = Link;
	head->leftchild = *T;
	head->RTag = Thread;
	BiThrTree p = *T;
	while (p->rightchild != NULL)
	{
		while (p->LTag==Link)
			p = p->leftchild;
		while (p->RTag == Thread && p->rightchild!=NULL)
			p = p->rightchild;
	}
	p->RTag = Thread;
	head->rightchild = p;
	p->rightchild = head;
	*T = head;
}

//前序遍歷線索二叉樹
void PreOrderTraverse_Thr(BiThrTree T)
{
	BiThrTree p = T->leftchild;
	printf("%c ", p->data);
	while (p != T)
	{
		//printf("%c ", p->data);
		while (p->LTag == Link)
		{
			p = p->leftchild;
			printf("%c ", p->data);
		}
		while (p->RTag == Thread && p!=T)
		{
			p = p->rightchild;
			if (p != T)
			{
				printf("%c ", p->data);
			}
		}
	}
}

//int index2;

//void createBiThrTree_Post(BiThrTree* T, char* str)
//{
//	char ch = str[index2++];
//	if (ch == '#')
//	{
//		*T = NULL;
//	}
//	else
//	{
//		createBiThrTree_Post(&((*T)->leftchild), str);
//		createBiThrTree_Post(&((*T)->rightchild), str);
//		BiThrTree tmp = (BiThrTree)malloc(sizeof(BiThrNode));
//		if (tmp == NULL)
//		{
//			printf("malloc fault\n");
//			return;
//		}
//		tmp->data = ch;
//		tmp->LTag = Link;
//		tmp->RTag = Link;
//		*T = tmp;
//	}
//
//}

extern BiThrTree pre2;

void PostThreading(BiThrTree p)
{
	if (p)
	{
		PostThreading(p->leftchild);
		PostThreading(p->rightchild);
		if (p->leftchild == NULL)
		{
			p->LTag = Thread;
			p->leftchild = pre2;
		}
		if (pre2 != NULL)
		{
			if (pre2->rightchild == NULL)
			{
				pre2->RTag = Thread;
				pre2->rightchild = p;
			}
		}
		pre2 = p;
	}
}

void addhead_Post(BiThrTree* T)
{
	BiThrTree head = (BiThrTree)malloc(sizeof(BiThrNode));
	if (head == NULL)
	{
		printf("malloc fault\n");
		return;
	}
	head->LTag = Link;
	head->leftchild = *T;
	head->RTag = Thread;
	BiThrTree p = *T;
	while (p->LTag == Link)
		p = p->leftchild;
	p->LTag = Thread;
	p->leftchild = head;
	head->rightchild = *T;
	if ((*T)->rightchild == NULL)
	{
		(*T)->rightchild = head;
	}
	*T = head;
}

//void PostOrderTraverse_Thr(BiThrTree T)
開發失敗 寄了
//{
//	BiThrTree p;
//	p = T->leftchild;
//	if (p == NULL)
//	{
//		printf("線索二叉樹為空\n");
//		return;
//	}
//	while (p != T)
//	{
//		while (p->LTag == Link)
//			p = p->leftchild;
//		printf("%c ", p->data);
//		while (p->RTag == Thread && p != T)
//		{
//			p = p->rightchild;
//			if (p == T)
//			{
//				break;
//			}
//			printf("%c ", p->data);
//		}
//		//到這里說明左子樹遍歷完了 該進入右子樹了
//		if (p != T)
//		{
//			p = p->rightchild;
//		}
//	}
//}

//test.c
#include "BiThrTree.h"
void test2()
{
	BiThrTree testtree;
	printf("請輸入這棵二叉樹的拓展二叉樹(#法)的前序排列\n");
	char arr[2 * MAXSIZE + 2] = { 0 };
	scanf("%s", arr);
	createBiThrTree(&testtree, arr);
	print(testtree);
	InThreading(testtree);
	addhead_IN(&testtree);
	printf("\n");
	InOrderTraverse_Thr(testtree);
}


void test3()
{
	BiThrTree testtree;
	printf("請輸入這棵二叉樹的拓展二叉樹(#法)的前序排列\n");
	char arr[2 * MAXSIZE + 2] = { 0 };
	scanf("%s", arr);
	createBiThrTree(&testtree, arr);
	print(testtree);
	PreThreading(testtree);
	addhead_Pre(&testtree);
	printf("\n");
	PreOrderTraverse_Thr(testtree);
}

void test4()
{
	BiThrTree testtree;
	printf("請輸入這棵二叉樹的拓展二叉樹(#法)的前序排列\n");
	char arr[2 * MAXSIZE + 2] = { 0 };
	scanf("%s", arr);
	createBiThrTree(&testtree, arr);
	print(testtree);
	PostThreading(testtree);
	addhead_Post(&testtree);
}

int main()
{
    test2();
    test3();
	test4();
	return 0;
}

?13.樹、森林與二叉樹的轉化

??我們費了那么大力氣研究二叉樹不僅僅是因為二叉樹是一種很基礎的樹，更是因為樹和森林都可以在某種程度上轉化為二叉樹，并且樹、森林的前序遍歷、后序遍歷結果與我們轉化出來的二叉樹的前序遍歷、中序遍歷是一樣的，下面我們來介紹這塊的內容，

🌴1.樹轉化為二叉樹

步驟：

  • 加線：在所有兄弟節點之間加一條連線，
  • 去線：對于樹的每個節點，只保留它和第一個孩子結點的連線，洗掉它與其他孩子結點之間的連線，
  • 層次調整：以樹的根節點為軸心，將整棵樹順時針旋轉一定的角度，使之結構層次分明，注意第一個孩子是二叉樹結點的左孩子，兄弟轉過來的孩子是結點的右孩子，

如圖：

在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述

🌴2.森林轉化為二叉樹

  • 把每個樹轉化為二叉樹
  • 第一棵樹不動，從第二棵二叉樹開始，依次把后一刻二叉樹的根節點作為前一棵二叉樹根節點的右孩子，用線連起來，

觀察到這種轉化轉化出來的二叉樹的根節點只有左孩子，

如圖：

在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述

🌴3.二叉樹轉化為樹

  • 加線：若某結點的左孩子存在，在把這個左孩子的右孩子，左孩子的右孩子的右孩子，，，，左孩子的n層右孩子都作為此節點的孩子，并且連線連起來，
  • 去線：洗掉原二叉樹中所有結點與其右孩子的連線，
  • 次序調整，

在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述

🌴4.二叉樹轉化為森林

??首先要判斷一棵二叉樹是否能轉化為一棵森林，很簡單，只要看這棵二叉樹的根節點有沒有右孩子，如果有，那就是森林，如果沒有，就是一棵樹，

  • 從根結點開始，如果右孩子存在，就把與右孩子結點的連線洗掉，
  • 看去除后的二叉樹，重復第一步，直到沒有右孩子為止，
  • 把每棵二叉樹轉化回普通的樹，
  • 在這里插入圖片描述

在這里插入圖片描述
在這里插入圖片描述

🌴5.樹與森林的遍歷

🔥5.1 樹的遍歷

🐱5.1.1 先根遍歷

??先訪問樹的根結點，然后依次先根遍歷根的每棵子樹，

🐱5.1.2 后根遍歷

??先依次后根遍歷每棵子樹，然后再訪問根結點，

🔥5.2 森林的遍歷

🐬5.2.1 前序遍歷

??先訪問森林中第一棵樹的根結點，然后再依次先根遍歷根的每棵子樹，然后再依次遍歷森林中的其他的樹，

🐬5.2.2 后序遍歷

??依次后根遍歷森林中的每棵子樹，

我們用個例子來說明樹的先根遍歷等價于轉化出來的二叉樹的前序遍歷、樹的后根遍歷等價于轉化出來的二叉樹的中序遍歷，

在這里插入圖片描述
在這里插入圖片描述

??再用一個例子說明森林的前序遍歷序列等價于轉化出的二叉樹的前序遍歷序列，森林的后序遍歷序列等價于轉化出的二叉樹的中序遍歷序列，

在這里插入圖片描述
在這里插入圖片描述

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/317921.html

標籤：其他

上一篇：三遍讀書法之第一遍，初識樹和二叉樹

下一篇：【資料結構初階】順序表_增刪查改、查詢、列印、銷毀 (附原始碼+realloc深解)

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 網閘典型架構簡述

    網閘架構一般分為兩種：三主機的三系統架構網閘和雙主機的2+1架構網閘。 三主機架構分別為內端機、外端機和仲裁機。三機無論從軟體和硬體上均各自獨立。首先從硬體上來看，三機都用各自獨立的主板、記憶體及存盤設備。從軟體上來看，三機有各自獨立的作業系統。這樣能達到完全的三機獨立。對于“2+1”系統，“2”分為 ......

    uj5u.com 2020-09-10 02:00:44 more
  • 如何從xshell上傳檔案到centos linux虛擬機里

    如何從xshell上傳檔案到centos linux虛擬機里及：虛擬機CentOs下執行 yum -y install lrzsz命令，出現錯誤：鏡像無法找到軟體包 前言 一、安裝lrzsz步驟 二、上傳檔案 三、遇到的問題及解決方案 總結 前言 提示：其實很簡單，往虛擬機上安裝一個上傳檔案的工具 ......

    uj5u.com 2020-09-10 02:00:47 more
  • 一、SQLMAP入門

    一、SQLMAP入門 1、判斷是否存在注入 sqlmap.py -u 網址/id=1 id=1不可缺少。當注入點后面的引數大于兩個時。需要加雙引號， sqlmap.py -u "網址/id=1&uid=1" 2、判斷文本中的請求是否存在注入 從文本中加載http請求，SQLMAP可以從一個文本檔案中 ......

    uj5u.com 2020-09-10 02:00:50 more
  • Metasploit 簡單使用教程

    metasploit 簡單使用教程 浩先生， 2020-08-28 16:18:25 分類專欄： kail 網路安全 linux 文章標簽： linux資訊安全 編輯 著作權 metasploit 使用教程 前言 一、Metasploit是什么？ 二、準備作業 三、具體步驟 前言 Msfconsole ......

    uj5u.com 2020-09-10 02:00:53 more
  • 游戲逆向之驅動層與用戶層通訊

    驅動層代碼： #pragma once #include <ntifs.h> #define add_code CTL_CODE(FILE_DEVICE_UNKNOWN,0x800,METHOD_BUFFERED,FILE_ANY_ACCESS) /* 更多游戲逆向視頻www.yxfzedu.com ......

    uj5u.com 2020-09-10 02:00:56 more
  • 北斗電力時鐘（北斗授時服務器）讓網路資料更精準

    北斗電力時鐘（北斗授時服務器）讓網路資料更精準 北斗電力時鐘（北斗授時服務器）讓網路資料更精準 京準電子科技官微——ahjzsz 近幾年，資訊技術的得了快速發展，互聯網在逐漸普及，其在人們生活和生產中都得到了廣泛應用，并且取得了不錯的應用效果。計算機網路資訊在電力系統中的應用，一方面使電力系統的運行 ......

    uj5u.com 2020-09-10 02:01:03 more
  • 【CTF】CTFHub 技能樹 彩蛋 writeup

    ?碎碎念 CTFHub：https://www.ctfhub.com/ 筆者入門CTF時時剛開始刷的是bugku的舊平臺，后來才有了CTFHub。 感覺不論是網頁UI設計，還是題目質量，賽事跟蹤，工具軟體都做得很不錯。 而且因為獨到的金幣制度的確讓人有一種想去刷題賺金幣的感覺。 個人還是非常喜歡這個 ......

    uj5u.com 2020-09-10 02:04:05 more
  • 02windows基礎操作

    我學到了一下幾點 Windows系統目錄結構與滲透的作用 常見Windows的服務詳解 Windows埠詳解 常用的Windows注冊表詳解 hacker DOS命令詳解（net user / type /md /rd/ dir /cd /net use copy、批處理 等） 利用dos命令制作 ......

    uj5u.com 2020-09-10 02:04:18 more
  • 03.Linux基礎操作

    我學到了以下幾點 01Linux系統介紹02系統安裝，密碼啊破解03Linux常用命令04LAMP 01LINUX windows： win03 8 12 16 19 配置不繁瑣 Linux：redhat,centos(紅帽社區版)，Ubuntu server,suse unix:金融機構，證券，銀 ......

    uj5u.com 2020-09-10 02:04:30 more
  • 05HTML

    01HTML介紹 02頭部標簽講解03基礎標簽講解04表單標簽講解 HTML前段語言 js1.了解代碼2.根據代碼 懂得挖掘漏洞 （POST注入/XSS漏洞上傳）3.黑帽seo 白帽seo 客戶網站被黑帽植入劫持代碼如何處理4.熟悉html表單 <html><head><title>TDK標題，描述 ......

    uj5u.com 2020-09-10 02:04:36 more
最新发布
  • 2023年最新微信小程式抓包教程

    01 開門見山 隔一個月發一篇文章，不過分。 首先回顧一下《微信系結手機號資料庫被脫庫事件》，我也是第一時間得知了這個訊息，然后跟蹤了整件事情的經過。下面是這起事件的相關截圖以及近日流出的一萬條資料樣本： 個人認為這件事也沒什么，還不如關注一下之前45億快遞資料查詢渠道疑似在近日復活的訊息。 訊息是 ......

    uj5u.com 2023-04-20 08:48:24 more
  • web3 產品介紹：metamask 錢包 使用最多的瀏覽器插件錢包

    Metamask錢包是一種基于區塊鏈技術的數字貨幣錢包，它允許用戶在安全、便捷的環境下管理自己的加密資產。Metamask錢包是以太坊生態系統中最流行的錢包之一，它具有易于使用、安全性高和功能強大等優點。 本文將詳細介紹Metamask錢包的功能和使用方法。 一、 Metamask錢包的功能 數字資 ......

    uj5u.com 2023-04-20 08:47:46 more
  • vulnhub_Earth

    前言 靶機地址->>>vulnhub_Earth 攻擊機ip：192.168.20.121 靶機ip：192.168.20.122 參考文章 https://www.cnblogs.com/Jing-X/archive/2022/04/03/16097695.html https://www.cnb ......

    uj5u.com 2023-04-20 07:46:20 more
  • 從4k到42k，軟體測驗工程師的漲薪史，給我看哭了

    清明節一過，盲猜大家已經無心上班，在數著日子準備過五一，但一想到銀行卡里的余額……瞬間心情就不美麗了。最近，2023年高校畢業生就業調查顯示，本科畢業月平均起薪為5825元。調查一出，便有很多同學表示自己又被平均了。看著這一資料，不免讓人想到前不久中國青年報的一項調查：近六成大學生認為畢業10年內會 ......

    uj5u.com 2023-04-20 07:44:00 more
  • 最新版本 Stable Diffusion 開源 AI 繪畫工具之中文自動提詞篇

    🎈 標簽生成器 由于輸入正向提示詞 prompt 和反向提示詞 negative prompt 都是使用英文，所以對學習母語的我們非常不友好 使用網址：https://tinygeeker.github.io/p/ai-prompt-generator 這個網址是為了讓大家在使用 AI 繪畫的時候 ......

    uj5u.com 2023-04-20 07:43:36 more
  • 漫談前端自動化測驗演進之路及測驗工具分析

    隨著前端技術的不斷發展和應用程式的日益復雜，前端自動化測驗也在不斷演進。隨著 Web 應用程式變得越來越復雜，自動化測驗的需求也越來越高。如今，自動化測驗已經成為 Web 應用程式開發程序中不可或缺的一部分，它們可以幫助開發人員更快地發現和修復錯誤，提高應用程式的性能和可靠性。 ......

    uj5u.com 2023-04-20 07:43:16 more
  • CANN開發實踐：4個DVPP記憶體問題的典型案例解讀

    摘要：由于DVPP媒體資料處理功能對存放輸入、輸出資料的記憶體有更高的要求（例如，記憶體首地址128位元組對齊），因此需呼叫專用的記憶體申請介面，那么本期就分享幾個關于DVPP記憶體問題的典型案例，并給出原因分析及解決方法。 本文分享自華為云社區《FAQ_DVPP記憶體問題案例》，作者：昇騰CANN。 DVPP ......

    uj5u.com 2023-04-20 07:43:03 more
  • msf學習

    msf學習 以kali自帶的msf為例 一、msf核心模塊與功能 msf模塊都放在/usr/share/metasploit-framework/modules目錄下 1、auxiliary 輔助模塊，輔助滲透（埠掃描、登錄密碼爆破、漏洞驗證等） 2、encoders 編碼器模塊，主要包含各種編碼 ......

    uj5u.com 2023-04-20 07:42:59 more
  • Halcon軟體安裝與界面簡介

    1. 下載Halcon17版本到到本地 2. 雙擊安裝包后 3. 步驟如下 1.2 Halcon軟體安裝 界面分為四大塊 1. Halcon的五個助手 1) 影像采集助手：與相機連接，設定相機引數，采集影像 2) 標定助手：九點標定或是其它的標定，生成標定檔案及內參外參，可以將像素單位轉換為長度單位 ......

    uj5u.com 2023-04-20 07:42:17 more
  • 在MacOS下使用Unity3D開發游戲

    第一次發博客，先發一下我的游戲開發環境吧。 去年2月份買了一臺MacBookPro2021 M1pro(以下簡稱mbp)，這一年來一直在用mbp開發游戲。我大致分享一下我的開發工具以及使用體驗。 1、Unity 官網鏈接： https://unity.cn/releases 我一般使用的Apple ......

    uj5u.com 2023-04-20 07:40:19 more

Copyright © 2010-2020 有解無憂