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.前序,中序,后序遍历的简单说明
<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>

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

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

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

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

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

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

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

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


热AI工具

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

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

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

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

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

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

SublimeText3汉化版
中文版,非常好用

EditPlus 中文破解版
体积小,语法高亮,不支持代码提示功能