使用先序遍历构建二叉树的方法

作者：球球小白痴_693 | 来源：互联网 | 2023-10-14 14:36

typedefcharElemType;树结构typedefstructtree{ElemTypedata;structtree*lchild;

typedef char ElemType;
//树结构
typedef struct tree
{
    ElemType data;
    struct tree * lchild;
    struct tree * rchild;
    unsigned int isOut;   //专为后序遍历设置的，0为不需要被输出，1为需要被输出
}TreeNode,*Tree;

//创建树,以先序序列建立树
void CreateTree(Tree &t)    //我说的指针引用在这
{
    char ch;
    scanf("%c",&ch);
    if ( ch == '#' )
    t = NULL;
    else
    {
    t = (Tree)malloc(sizeof(TreeNode));
        if ( !t )
    {
        printf("分配内存出错！");
        return ;
    }
    t->data = ch;
    CreateTree(t->lchild);
    CreateTree(t->rchild);
    }
}

[code=c]

[/code]

//我不懂的地方在于为什么在创建树时使用了指针的引用，它很神奇，竟然在创建树的函数中不给返回值，而且，当我去掉&时，程序编译通过，执行会异常终止！

8 个解决方案

#1

typedef char ElemType;

//树结构

typedef struct tree

{

    ElemType data;

    struct tree * lchild;

    struct tree * rchild;

    unsigned int isOut;   //专为后序遍历设置的，0为不需要被输出，1为需要被输出

}TreeNode,*Tree;

//创建树,以先序序列建立树

void CreateTree(Tree &t)//我说的指针引用在这



{

    char ch;

    scanf("%c",&ch);

    if ( ch == '#' )

    t = NULL;

    else

    {

    t = (Tree)malloc(sizeof(TreeNode));

        if ( !t )

    {

        printf("分配内存出错！");

        return ;

    }

    t->data = ch;

    CreateTree(t->lchild);

    CreateTree(t->rchild);

    }

}





//递归先序遍历

void PreOrder(Tree t)

{

    if ( t )

    {

    printf("%c",t->data);

    PreOrder(t->lchild);

    PreOrder(t->rchild);

    }

}

//我不懂的地方在于为什么在创建树时  使用了指针的引用，它很神奇，竟然在创建树的函数中不给返回值，而且，当我去掉&时，程序编译通过，执行会异常终止！

#2

C直接不能编译；
C++ 指针的引用，是链式结构的福音。
不必再用二级指针了。

引用有指针的能力，而无其弊，刚刚好。
引用是对象的别名，代行对象的权利。

T x;
T &ref =x;

T b =ref;//即T b =x;
T c;
c = ref; //即c =x;
ref =b;//即 x=b；

&ref // 即& x;

除了名字不同，引用可以代替被引用者，做他所能做的事情。
引用参数，也可以代替被引用者，做他所能做的事情。

不受参数值传递的约束。
引用参数不是值传递。

非引用参数，都是值传递。

C没有引用，只有值传递。
C++有了引用，多了引用传递，这一种参数传递手段。

引用传递的实质，是传递地址；
只是表面上，用实参本身做参数，传递给被调函数。
和值传递有本质的区别。

C的指针参数，只是模拟地址传递，语法上还是值传递。
通过传递指针，用指针间接引用指针指向的对象，

C++引用传递，实参即被引用的对象；
形参在被调函数中代表实参本身。

作用和指针差不多。
但是语法上和直接使用实参本身是一致的。
函数调用语法，则和值传递一致。

这表明，引用是一种特殊数据类型。
既不同于指针，也不同于对象。

他代替被引用的对象工作，一切结果，都和被引用的对象自己工作相同。

#3

大神，能讲得具体一点吗

#4

大姐，你太强了，德问上也看到你发了

#5

void InitialBitTree(BitTree * T)
{//初始化二叉树
int n;
cout<<"input n: \n";
cin>>n;
if(n==0)
T=NULL;
else
{
if(!(T=new BitTree))exit(-1);
T->e = n;
InitialBitTree(T->lchild) ;
InitialBitTree(T->rchild) ;
}
}
我用的是整型，没错吖。调用时：
InitialBitTree(T);

#6

引用 5 楼 u012540439 的回复:

代码放在代码块，看着清晰：

void InitialBitTree(BitTree * T)

{//初始化二叉树

	int n;

	cout<<"input n: \n";

	cin>>n;

	if(n==0)

		T=NULL;

	else

	{

		if(!(T=new BitTree))exit(-1);

		T->e = n;

		InitialBitTree(T->lchild) ;

		InitialBitTree(T->rchild) ;

	}

}

我用的是整型，没错吖。调用时：
InitialBitTree(T);

InitialBitTree(T); 以后实参T 没有变化；

只是在函数InitialBitTree 内部形参 T发生了改变。
结果是，函数InitialBitTree 创建了一棵树，但是传递不出函数。并造成内存泄露。
实参T并没有接收到创建了的那棵树。
定义为
void InitialBitTree(BitTree *&T)
后
InitialBitTree(T);
就真正创建一棵树了。
C++ 二叉树



.....

 void InitialBitTree(BitTree *& T)

{//初始化二叉树

	int n;

	cout<<"input n: \n";

	cin>>n;

	if(n==0)

		T=NULL;

	else

	{

		if(!(T=new BitTree))exit(-1);

		  T->e = n;

		InitialBitTree(T->lchild) ;

		InitialBitTree(T->rchild) ;

	}

}

int main(){

BitTree * T=NULL;

InitialBitTree(T);

.....

//记住销毁二叉树，释放结点占用的内存

return 0;//

}

引用参数，采用引用传递，实参会接收形参的改变。
如果是C代码，由于只能值传递，只有使用二级指针。
C++ 二叉树：



.....

 void InitialBitTree(BitTree ** T)

{//初始化二叉树

	int n;

	cout<<"input n: \n";

	cin>>n;

	if(n==0)

		*T=NULL;

	else

	{

		if(!(*T=new BitTree))exit(-1);

		（*T）->e = n;

		InitialBitTree(&(*T)->lchild) ;

		InitialBitTree(&(*T)->rchild) ;

	}

}

int main(){

BitTree * T=NULL;

InitialBitTree(&T);

.....

//记住销毁二叉树，释放结点占用的内存

return 0;//

}

#7

后面的C++ 二叉树：应该是C二叉树

#8

太谢谢你了，@lm_whales，说的很对

推荐阅读

char
Codeforces Round #566 (Div. 2) A~F个人题解

Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意：给你一个的表格，你 ... [详细]

蜡笔小新 2024-12-25 18:41:21
char
Weight the Tree（树形dp）

题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]

蜡笔小新 2024-12-26 15:55:56
rsa
Transforming the Future of Virtual Worlds

Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]

蜡笔小新 2024-12-28 09:44:49
text
分页插件3指定到某一页

前言--页数多了以后需要指定到某一页（只做了功能，样式没有细调）html ... [详细]

蜡笔小新 2024-12-27 15:19:01
replace
Java面试题解析

本文详细介绍了Java编程语言中的核心概念和常见面试问题，包括集合类、数据结构、线程处理、Java虚拟机（JVM）、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题，帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]

蜡笔小新 2024-12-27 13:55:14
case
C语言实现小写金额转换为大写金额

在金融和会计领域，准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据，还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法，确保数据的标准化和规范化。 ... [详细]

蜡笔小新 2024-12-27 12:39:06
case
UNP 第9章：主机名与地址转换

本章探讨了用于在主机名和数值地址之间进行转换的函数，如gethostbyname和gethostbyaddr。此外，还介绍了getservbyname和getservbyport函数，用于在服务器名和端口号之间进行转换。 ... [详细]

蜡笔小新 2024-12-27 11:26:39
text
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新 2024-12-26 20:04:36
char
从 .NET 转 Java 的自学之路：IO 流基础篇

本文详细介绍了 Java 中的 IO 流，包括字节流和字符流的基本概念及其操作方式。探讨了如何处理不同类型的文件数据，并结合编码机制确保字符数据的正确读写。同时，文中还涵盖了装饰设计模式的应用，以及多种常见的 IO 操作实例。 ... [详细]

蜡笔小新 2024-12-26 17:37:25
char
C++ 中的数组与动态数组初始化

本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度，而 vector 是一种可扩展的容器，允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景，并提供了代码示例以加深理解。 ... [详细]

蜡笔小新 2024-12-26 15:38:03
char
长春大学软件工程：二叉排序树实验报告

本实验主要探讨了二叉排序树（BST）的基本操作，包括创建、查找和删除节点。通过具体实例和代码实现，详细介绍了如何使用递归和非递归方法进行关键字查找，并展示了删除特定节点后的树结构变化。 ... [详细]

蜡笔小新 2024-12-26 15:32:56
char
C语言链表动态创建：头插法与尾插法详解

本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法，包括具体的实现代码和运行示例。通过这些内容，读者可以更好地理解和掌握链表的基本操作。 ... [详细]

蜡笔小新 2024-12-26 13:59:07
char
Linux设备驱动程序：异步时间操作与调度机制

本文介绍了Linux内核中的几种异步延迟操作方法，包括内核定时器、tasklet机制和工作队列。这些机制允许在未来的某个时间点执行任务，而无需阻塞当前线程，从而提高系统的响应性和效率。 ... [详细]

蜡笔小新 2024-12-26 08:55:03
ip
深入解析C++对象模型中的细节问题

本文深入探讨了C++对象模型中的一些细节问题，特别是虚拟继承和析构函数的处理。通过具体代码示例和详细分析，揭示了书中某些观点的不足之处，并提供了更合理的解释。 ... [详细]

蜡笔小新 2024-12-25 19:29:03
char
深入理解线程局部存储

在多线程编程环境中，线程之间共享全局变量可能导致数据竞争和不一致性。为了解决这一问题，Linux提供了线程局部存储（TLS），使每个线程可以拥有独立的变量副本，确保线程间的数据隔离与安全。 ... [详细]

蜡笔小新 2024-12-25 17:04:36

球球小白痴_693

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章