搜索
首页数据库mysql教程二叉树(1)已知某2种排序方式,创建这个二叉树并按第3种方式排序

1.关于指针和引用的说明 数据结构中 建立 二叉树子函数,根结点为什么用双重指针,即 指针的指针。 因为树的结点要用指针描述。 如果只用指针,作形参传给建立结点的函数,这个指针传给了函数栈中的内存,函数返回后,函数栈销毁,不能获得结点。 而用指针的

1.关于指针和引用的说明

   数据结构中建立二叉树子函数,根结点为什么用双重指针,即指针的指针。因为树的结点要用指针描述。如果只用指针,作形参传给建立结点的函数,这个指针值传给了函数栈中的内存,函数返回后,函数栈销毁,不能获得结点。而用指针的指针,函数内修改了这个双重指针指向的值(即结点指针),在函数外也能获得结点。这swap()函数要用指针而不能用值做参数一样。只是这里的值本身就是个指针,所以要用指针的指针。如下:

 typedef struct BinaryTreeNode
{
    char data;
    BinaryTreeNode * leftChild;
    BinaryTreeNode * rightChild;
}Node;
void Create(Node**T){......}
int main(){
	 Node* T;
	 Create(&T);
}

<span><span>   <span>如果Create的参数不是指针的引用(等同双指针),</span></span></span><span><span><span><span>main中 Create(T)是把指针T指向的地址传进去了。注意,只是地址.</span></span></span><span><span><span>然后你在Create函数内部申请内存时, 把这个地址给改变了, 但是因为你传的是一个地址, 这个地址本身跟T无关,T仅仅是指向了这个地址而以. 所以Create(T)之后, T还是指向原来的地址,并未改变, 后面的操作当然就是崩溃了(因为T未初始化,是一个野指针)。</span></span></span><span><span><br></span></span><span><span><span> 传值: 函数内部修改不会对原值内容进行改变.
</span></span></span><span><span><span>     传址: 函数内部修改会影响原值.</span></span></span><span><span><span>    可能我们认为值的指针就是传址了.</span></span></span><span><span><span>如果是传值, 函数入栈的时候就是把这个变量的值压栈,如果是传址, 就是把指针压栈,但压栈的时候,本身实际也是写一个数值而以.</span></span></span><span><span><span>你传的是指针的情况下, 如果修改指针指向的内容, 那么函数外部会同步修改.</span></span></span><span><span><span>但是你传入的是指针, 但是又修改的是指针本身, 而不是其内容, 那么你这就相当于传值.</span></span></span><span><span><span>当你要修改指针本身的时候, 你可以这样理解.</span></span></span></span>

//比如有:
void Creat(BTNode *pRoot);
//可以修改成以下形式
typedef BTNode* PNODE;
void Creat(PNODE pRoot);
//这时你可能就看出来了, 原来这是一个传值调用.想要修改pRoot的值, 那么就要
void Creat(PNODE &pRoot); ====还原就是 void Creat(BTNode* &pRoot);
//或者
void Creat(PNODE *pRoot); ====还原就是 void Creat(BTNode* *pRoot);
反正注意区分传址还是传值的区分不是看参数是否是指针, 而是要看你在函数内部是如何操作参数的. 如果你操作的是参数本身, 那么就是传值.如果你是把参数当成一个地址, 操作的是那个地址上的内容,那就是传址。

一个简单的例子:

  int a = 1;
  int b = 2;  
  int *tmp = &a;
  int *p = tmp;// 第二种情况:int *&p = tmp;(此即是指向指针的引用)
  p = &b;
  *p = 5;
<span>  第一种情况:a=1,b=5,*p=5,tmp=1
</span><pre class="brush:php;toolbar:false"><span>  第二种情况:a=1,b=,*p=5,<span>tmp=5.</span> 
</span><span><span>这是因为指向指针的引用,不仅改变了指针所指的对象,也改变了指针本身。</span></span>

2.前序,中序,后序遍历的简单说明

二叉树(1)已知某2种排序方式,创建这个二叉树并按第3种方式排序

<span><span><strong>   </strong></span></span><span><span><span><strong>先序遍历</strong></span><span>也叫做先根遍历,前序遍历</span></span><span>,<span>可记做</span><strong><span><span>根</span></span><span>左右</span></strong><span>(二叉树父结点向下先左后右)。</span></span><span>首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树,如果二叉树为空则返回。</span><span>上图所示二叉树的先序遍历结果是:ABDECF。
</span></span><span><span>    <span>已知中序遍历和后序遍历,可以确定唯一的前序遍历。</span></span></span>
<span><span>    </span><span><span><span>中序遍历</span><span><span>也叫</span><span>做</span><span>中根遍历</span><span>、</span><span>中序周游,可记做</span><span><strong><span>左</span><span>根</span><span>右</span></strong></span><span>。</span></span><span>首先遍历左子树,然后访问根结点,最后遍历右子树。在遍历左、右子树时,仍然先遍历左子树,再访问根结点,最后遍历右子树。</span></span></span></span><span><span>注意的是:遍历左右子树时</span><span>仍然采用中序遍历方法。</span><span>中<span>序遍历的</span></span><span>时间复杂度</span><span><span>为</span>:O(n)。</span><span>如果一棵</span><span>二叉排序树</span><span>的节点值是数值,中序遍历的结果为升序排列的</span><span>数组</span><span>。可以利用该性质检测一棵树是否为二叉排序数。<span>上图所示</span><span>二叉树</span><span>中</span><span>序遍历结果:DBEAFC</span></span></span>
<span><span>    </span><span><span>已知前序遍历和后序遍历,</span><span><span><strong>不能</strong></span></span><span>确定唯一的中序遍历。</span></span></span>
<p><span></span></p><span><span><span>    </span><span><span><strong>后序遍历</strong></span><span>(LRD)</span></span><span>也叫做</span><span>后根遍历</span><span>、后序周游,可记做</span><span><span>左右</span></span><span><span><strong>根</strong></span></span><span>。后序遍历有</span><span><span>递归算法</span></span><span>和非递归算法两种。</span></span></span><span><span>后序遍历首先遍历左子树,然后遍历右子树,最后遍历访问根结点,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后遍历根结点。即:</span><span>若</span><span>二叉树</span><span>为空则结束返回,</span><span>否则:</span><span>(1)后序遍历左子树</span><span>(2)后序遍历右子树(3)访问根结点。</span><span>如右图所示</span><span>二叉树</span><span>后序遍历结果:DEBFCA。
</span></span><span><span>    </span><span><span>已知前序遍历和中序遍历,可以确定唯一的后序遍历。</span></span></span>

   解释:前序或后序能够确定根节点,结合中序能够唯一确定左子树和右子树元素。而仅仅知道前序和后序时,当左右子树存在空时,无法唯一确定究竟是哪一棵树为空。即仅仅知道前序和后序,无法唯一的还原2叉树,即中序无法唯一确定。


3.程序代码以及说明

   1.已知前序和中序排列,创建二叉树,并输出后序排列
   2.已知中序和后序排列,创建二叉树,并输出前序排列
   3.使用递归法遍历二叉树

#include "iostream"
using namespace std;
typedef struct BinaryTreeNode//二叉树节点
 {
	 char data;
	 BinaryTreeNode* leftchild;
	 BinaryTreeNode* rightchild;
 }Node,*NodePoint;
 bool MakeBinaryTree_PM(NodePoint* root,char* preOrder, char* midOrder,int length)//基于前序和中序遍历计算后序遍历
 {
	 if(length==0)
	    {*root=NULL;return true;}
	 else
	    {
	     *root=new Node;
	    (*root)->data=*preOrder;//前序第一个元素为根节点
             char * rootposition = strchr(midOrder,(*root)->data);//查找根节点在排序中的位置
	     if (rootposition == NULL)
		 {cout leftchild,preOrder+1,midOrder,LeftTreeSize);
	MakeBinaryTree_PM(&(*root)->rightchild,preOrder+LeftTreeSize+1,rootposition+1,length-LeftTreeSize-1);
	          return true;
		  }
	      }
 }
bool MakeBinaryTree_ML(NodePoint* root,char* midOrder,char* lastOrder,int length)//基于中序和后序遍历计算前序遍历
 {
	 if(length==0)
	    {*root=NULL;return true;}
	 else
	    {
	      *root=new Node;
	     (*root)->data=lastOrder[length-1];//后序最后一个元素为根节点
	      char * rootposition = strchr(midOrder,(*root)->data);//查找根节点在排序中的位置
	      if (rootposition == NULL)
		  {cout leftchild,leftSubTree_mid,leftSubTree_last,LeftSubTreeSize);
		   delete[]leftSubTree_mid;delete[]leftSubTree_last;
		   MakeBinaryTree_ML(&(*root)->rightchild,rootposition+1,rightSubTree_last,RightSubTreeSize);
                   delete []rightSubTree_last;
		   return true;
	         }
	    }
 }
 void PreTraverse(NodePoint Root)//嵌套前序遍历
 {
    if(Root==NULL);
    else
      {coutdata;
       PreTraverse(Root->leftchild);
       PreTraverse(Root->rightchild);}
 }
void MidTraverse(NodePoint Root)//嵌套中序遍历
 {
       if(Root==NULL);
       else
       {MidTraverse(Root->leftchild);
	   coutdata;
	MidTraverse(Root->rightchild);}
 }
void PostTraverse(Node* Root)//嵌套后序遍历
{
    if (Root == NULL)
        return;
    PostTraverse(Root->leftchild);
    PostTraverse(Root->rightchild);
    cout data;
}
int main(int argc, const char** argv)
{
    char pre[] = "abdeijcfg";//前序
    char mid[] = "dbiejafcg";//中序
    char last[]="dijebfgca";//后序
    Node* Root;
	
    MakeBinaryTree_PM(&Root, pre, mid, strlen(pre));//使用指针的引用
    cout//使用指针的引用
    cout<br>
<pre class="brush:php;toolbar:false"> <span><span><strong>注意 </strong></span>1.必须知道中序,知道任何其他两种中的一种倘若知道,可建唯一的二叉树进而得到另外一种排序。
</span><span>      2.创建二叉树的时候,使用指针的引用作为形参,即双重指针。</span>
声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
使用Python实现XML数据的筛选和排序使用Python实现XML数据的筛选和排序Aug 07, 2023 pm 04:17 PM

使用Python实现XML数据的筛选和排序引言:XML是一种常用的数据交换格式,它以标签和属性的形式存储数据。在处理XML数据时,我们经常需要对数据进行筛选和排序。Python提供了许多有用的工具和库来处理XML数据,本文将介绍如何使用Python实现XML数据的筛选和排序。读取XML文件在开始之前,我们需要先读取XML文件。Python有许多XML处理库,

C++程序:按字母顺序重新排列单词的位置C++程序:按字母顺序重新排列单词的位置Sep 01, 2023 pm 11:37 PM

在这个问题中,一个字符串被作为输入,我们必须按字典顺序对字符串中出现的单词进行排序。为此,我们为字符串中的每个单词(之间用空格区分)分配一个从1开始的索引,并以排序索引的形式获得输出。String={“Hello”,“World”}“Hello”=1“World”=2由于输入字符串中的单词已按字典顺序排列,因此输出将打印为“12”。让我们看看一些输入/结果场景-假设输入字符串中的所有单词都相同,让我们看看结果-Input:{“hello”,“hello”,“hello”}Result:3获得的结

如何优化Java集合排序性能如何优化Java集合排序性能Jun 30, 2023 am 10:43 AM

Java是一种功能强大的编程语言,广泛应用于各类软件开发中。在Java开发中,经常会涉及到对集合进行排序的场景。然而,如果不对集合排序进行性能优化,可能会导致程序的执行效率下降。本文将探讨如何优化Java集合排序的性能。一、选择合适的集合类在Java中,有多种集合类可以用来进行排序,如ArrayList、LinkedList、TreeSet等。不同的集合类在

如何利用vue和Element-plus实现数据的分组和排序如何利用vue和Element-plus实现数据的分组和排序Jul 18, 2023 am 10:39 AM

如何利用Vue和ElementPlus实现数据的分组和排序Vue是一种流行的JavaScript框架,它可以帮助我们构建前端应用程序。ElementPlus是基于Vue的桌面端组件库,它提供了丰富的UI组件,使我们能够轻松地构建出漂亮且用户友好的界面。在本文中,我们将探讨如何利用Vue和ElementPlus来实现数据的分组和排序。首先,我们需要准备一

Java开发中如何优化集合排序去重性能Java开发中如何优化集合排序去重性能Jul 02, 2023 am 11:25 AM

Java开发中,集合排序和去重是常见的需求。然而,在处理大数据集合时,性能往往会成为一个问题。本文将介绍一些优化技巧,帮助提升集合排序和去重的性能。一、使用合适的数据结构在Java中,最常用的数据结构是ArrayList和HashSet。ArrayList适用于需要保持元素顺序的情况,而HashSet则适用于需要去重的情况。在排序和去重的场景中,我们可以使用

Java实现的常见排序算法详解Java实现的常见排序算法详解Jun 18, 2023 am 10:48 AM

排序算法是计算机科学中的一个重要概念,是许多应用程序的核心部分。在日常生活和工作中,我们经常需要对数据进行排序,例如排列名单、对数值进行排序等。Java作为一种广泛使用的编程语言,提供了许多内置的排序算法。本文将详细介绍Java中实现的常见排序算法。1.冒泡排序(BubbleSort)冒泡排序是最简单但最慢的排序算法之一。它遍历整个数组,比较相邻的元素并一

如何在Java 14中使用Records类来实现自动比较和排序如何在Java 14中使用Records类来实现自动比较和排序Jul 30, 2023 pm 01:06 PM

如何在Java14中使用Records类来实现自动比较和排序Java14引入了一种新的类称为Records类,它为我们提供了一种简洁而强大的方式来定义不可变的数据类。Records类具有自动为每个字段生成getter方法、equals()方法和hashCode()方法的特性,这使得比较和排序非常方便。在这篇文章中,我们将通过示例代码来演示如何在Java

如何使用PHP完成一个中文拼音首字母的排序功能?如何使用PHP完成一个中文拼音首字母的排序功能?Sep 05, 2023 am 11:31 AM

如何使用PHP完成一个中文拼音首字母的排序功能?在许多应用程序中,我们经常需要对一些中文字符串进行排序。而中文字符串的排序需要按照拼音的首字母进行排序,这就需要我们使用PHP来完成一个中文拼音首字母的排序功能。下面我们将详细介绍如何使用PHP来实现这个功能。首先,我们需要使用到一个PHP扩展库,叫做"pinyin",它提供了将中文转换为拼音的功能。可以通过在

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

安全考试浏览器

安全考试浏览器

Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

功能强大的PHP集成开发环境

MinGW - 适用于 Windows 的极简 GNU

MinGW - 适用于 Windows 的极简 GNU

这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

EditPlus 中文破解版

EditPlus 中文破解版

体积小,语法高亮,不支持代码提示功能