二叉树前序遍历java

ゞ浴缸里的玫瑰 2023-09-25 11:16 16阅读 0赞

## 建立中序线索二叉树，实现在这样的中序线索二叉树上的遍历算法。大神这个怎么做！！ ##

要实现本题的要求，首先要创建一棵二叉树，该二叉树的创建策略其实就是搜索二叉树的创建原则，当数组元素大于节点元素时，则数组元素应插在当前节点的右分支上，若当前节点的右儿子为空，直接插入，否则一次依次往下比较；当数组元素小于当前节点元素时，应当将其插在当前节点的左分支上，若当前节点的左儿子为空，则直接插入，否则依次比较下去直至找到插入的位置。

在创建好二叉树以后，便要对二叉树进行线索化，根据二叉树线索化的思想，在中序线索化的过程中，对于内节点，其前驱节点是其左子树的最右结点，其后继结点是右子树的最左节点；对于叶子节点，最左儿子的前驱为空，而最右叶子节点的后继结点为空。

线索化以后，则需对其进行中序遍历，然后对其进行输出即可

本回答由网友推荐

![二叉树前序遍历java\_java中序线索二叉树][java_java]

## 先序线索二叉树和中序线索二叉树有什么区别 ##

先序是先根节点在左结点再右结点，中序是先左，再根节点，再右结点

## 中序线索化二叉树程序 ##

\#include

typedef char elemtype ;

typedef enum\{ Link , Thread \} PointerTag;

typedef struct node\{

elemtype data;

PointerTag leftChildTag,rightChildTag;

struct node \*leftChild, \*rightChild;

\}ThreadBitreeNode,\*ThreadBitree;

//先序创建线索二叉树

void InOrderThreadBitreeCreate(ThreadBitree &T)

char ch;

cin>>ch;

if(ch!='\*')

T=new ThreadBitreeNode;

T->data=ch;

T->leftChildTag=T->rightChildTag=Link;

T->leftChild=NULL;

T->rightChild=NULL;

InOrderThreadBitreeCreate(T->leftChild);

InOrderThreadBitreeCreate(T->rightChild);

else T=NULL;

//中序线索化二叉树

void Threading(ThreadBitree p,ThreadBitree &pre)

if(p)

Threading(p->leftChild,pre);

if(p->leftChild==NULL)

p->leftChild=pre;

p->leftChildTag=Thread;

if(pre->rightChild==NULL)

pre->rightChild=p;

pre->rightChildTag=Thread;

pre=p;

Threading(p->rightChild,pre);

void InOrderThread(ThreadBitree &T,ThreadBitree &head)

head=new ThreadBitreeNode;

head->leftChildTag=Link;

head->rightChildTag=Thread;

head->rightChild=head;

if(T==NULL)head->leftChild=head;

else

head->leftChild=T;

ThreadBitree pre;

pre=head;

Threading(T,pre);

pre->rightChild=head;

pre->rightChildTag=Thread;

head->rightChild=pre;

\}inthreaded(curr->left(),pre); //这句 ，结点往左走，pre还不变吗？还能这样写吗？

这个是递归调用本函数，如果不为空，有节点，就顺左子树的线路往下找，pre指向该节点本身的前驱节点(也就是左孩子)

if(pre==null) curr->lth()=1; //置线索 是curr->left()为空才置1吧？跟pre==null有什么关系？

这个pre==null是看该节点是不是叶子节点，要是按你说的curr->left()为空才置1，那curr->right呢？不就错了

我也是刚学的数据结构，不过我看的书的线索二叉树是 如果该节点没有左孩子，则空出来的指针域指向其前驱(都是中序遍历)，没有又孩子，则指向其后继，你这个看起来有点怪， 我也正在学，说的也不一定对

![二叉树前序遍历java\_java中序线索二叉树\_02][java_java_02]

## Java课程设计 构造先序和后序线索二叉树 ##

先序遍历就是按照：1.根节点。2.左子树。3.右子树 的顺序进行遍历。 中序遍历,：1左子树。2根节点。3右子树。的顺序进行遍历。 后序遍历：1左子树。2右子树 。3根节点 。的顺序遍历。 java代码的思路是：首先创建节点node类 public class treenode \{ public t nodeval(treenode root)\{//指定根节点，从根几点开始找treenodetemp =root;if(root.nodeval(root.left!=null)\{temp = root.left;//递归调用自己，表示只要左节点不为空，就把左节点作为新的根节点继续上边步奏demo1(temp);\}if(root.right!=null)\{temp = root.right;demo1(temp);//同上\} \} //大概思路就是这样，中续和后续都差不多。这是伪代码。希望能帮助你理解。

[java_java]: https://img0.baidu.com/it/u=2703744807,1638585522&fm=26&fmt=auto
[java_java_02]: https://img1.baidu.com/it/u=4007637284,271078808&fm=26&fmt=auto