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

作者：球球小白痴_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
ip
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

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

蜡笔小新 2024-12-26 20:04:36
char
Weight the Tree（树形dp）

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

蜡笔小新 2024-12-26 15:55:56
ip
深入理解Redis的数据结构与对象系统

本文详细探讨了Redis中的数据结构和对象系统的实现，包括字符串、列表、集合、哈希表和有序集合等五种核心对象类型，以及它们所使用的底层数据结构。通过分析源码和相关文献，帮助读者更好地理解Redis的设计原理。 ... [详细]

蜡笔小新 2024-12-25 04:11:22
ip
编写有趣的VBScript恶作剧脚本

本文将介绍如何编写一些有趣的VBScript脚本，这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例，帮助您了解VBScript的基本语法和功能。 ... [详细]

蜡笔小新 2024-12-28 09:46:23
uri
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
string
XNA 3.0 游戏编程：从 XML 文件加载数据

本文介绍如何在 XNA 3.0 游戏项目中从 XML 文件加载数据。我们将探讨如何将 XML 数据序列化为二进制文件，并通过内容管道加载到游戏中。此外，还会涉及自定义类型读取器和写入器的实现。 ... [详细]

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

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

蜡笔小新 2024-12-27 11:26:39
ip
ImmutableX Poised to Pioneer Web3 Gaming Revolution

ImmutableX is set to spearhead the evolution of Web3 gaming, with its innovative technologies and strategic partnerships driving significant advancements in the industry. ... [详细]

蜡笔小新 2024-12-27 08:55:17
stream
从 .NET 转 Java 的自学之路：IO 流基础篇

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

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

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

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

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

蜡笔小新 2024-12-26 13:59:07
string
洛谷 P4116 树上操作：颜色变换与路径查询

本题涉及一棵由N个节点组成的树（共有N-1条边），初始时所有节点均为白色。题目要求处理两种操作：一是改变某个节点的颜色（从白变黑或从黑变白）；二是查询从根节点到指定节点路径上的第一个黑色节点，若无则输出-1。 ... [详细]

蜡笔小新 2024-12-26 10:22:20
char
深入理解线程局部存储

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

蜡笔小新 2024-12-25 17:04:36
string
2016年10月25日数学考试：斐波那契数列与矩阵快速幂的应用

本次考试于2016年10月25日上午7:50至11:15举行，主要涉及数学专题，特别是斐波那契数列的性质及其在编程中的应用。本文将详细解析考试中的题目，并提供解题思路和代码实现。 ... [详细]

蜡笔小新 2024-12-25 13:08:21

球球小白痴_693

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

Tags | 热门标签

RankList | 热门文章