# 【算法与数据结构】二叉树 中序线索

```/************************************************************************

-----------------------------------------
| lChild | lTag | value | rTag | rChild |
-----------------------------------------
lChild = (lTag == 0 ? 左孩子指针 : 某种遍历的前驱节点)
rChild = (rTag == 0 ? 右孩子指针 : 某种遍历的后继节点)

rChild指向遍历次序的最后一个节点

************************************************************************/```

```#ifndef OVERFLOW_FOR_MALLOC
#define OVERFLOW_FOR_MALLOC   (-1)
#endif
typedef struct _tagBinaryTree
{
unsigned char value;
struct _tagBinaryTree* left;
struct _tagBinaryTree* right;
}BinaryTree, *PBinaryTree;
//访问节点
void Visit(PBinaryTree pNode)
{
if (NULL != pNode)
cout << "节点的值为 "<<pNode->value<<endl;
}```

```//递归先序建立二叉树
void InitBinaryTree(PBinaryTree& pNode)
{
cout << "请输入节点的值，#表示NULL:";
unsigned char chValue = 0;
cin >> chValue;
if (‘#‘ == chValue)
{
pNode = NULL;
}
else
{
pNode = (PBinaryTree)(malloc(sizeof(BinaryTree)));
if (NULL == pNode) exit(OVERFLOW_FOR_MALLOC);
pNode->value = chValue;
InitBinaryTree(pNode->left);
InitBinaryTree(pNode->right);
}
}```

```//递归中序线索化
//p为根节点
//pPreNode为一个辅助节点
{
if (p)
{
if (! p->left)
{
p->left = pPreNode;
}
if (! pPreNode->right)
{
pPreNode->right = p;
}
pPreNode = p;
}
}```

```//中序线索二叉树, 为头结点申请空间，初始化头结点指针
//中序线索化后
//Thrt为头结点，T为二叉树的根节点
{
if(NULL == T) return;
Thrt = (PBinaryTree)(malloc(sizeof(BinaryTree)));
if(NULL == Thrt)
{
cerr << "创建头节点不成功\r\n"<<endl;
return;
}
Thrt->left = T;
Thrt->right = Thrt;
PBinaryTree pPreNode = Thrt;
pPreNode->right = Thrt;
Thrt->right = pPreNode;
}```

```//中序线索遍历二叉树
//p为头结点，而非根节点
void InOrderTraverse(PBinaryTree T)
{
//p为根节点
PBinaryTree p = T->left;
while (p != T)
{
//一直找到中序遍历的第一个节点
while(p->lTag == Link) p = p->left;
//并访问之
Visit(p);
//访问p的后继结点
while(p->rTag == Thread && p->right != T)
{
p = p->right;
Visit(p);
}
p = p->right;
}
}```

```int _tmain(int argc, _TCHAR* argv[])
{
cout << "----------开始 递归先序创建二叉树----------\r\n";
PBinaryTree pRoot = NULL;
InitBinaryTree(pRoot);
cout << "----------结束 递归先序创建二叉树----------\r\n\r\n";
cout << "\r\n----------开始 中序线索二叉树---------------\r\n";
PBinaryTree pNode = NULL;
cout << "\r\n----------结束 中序线索二叉树---------------\r\n";
//InOrderTraverse(pRoot);
cout << "\r\n\r\n############开始 中序线索遍历二叉树###############\r\n";
InOrderTraverse(pNode);
cout << "\r\n#############结束 中序线索遍历二叉树################\r\n\r\n";
return 0;
}```

【算法与数据结构】二叉树 中序线索,布布扣,bubuko.com

## 数据结构：中序线索二叉树

//所谓线索二叉树无非是为了让原本指向NULL的节点指向一个详细的 //已经存在的节点,逻辑上实现指针的无空指向的实现.以下是我中 //序线索二叉树的实现.还是把先序线索二叉树与后序线索分开来写吧. #include<iostream> using namespace std; template<typename Type> struct Node { Type data; bool rflags;//false为线. bool lflags; Node<Type> *

## 二叉树的中序线索化以及遍历

#include <stdio.h> #include <stdlib.h> typedef struct Node { char data; int Ltag; struct Node* LChild; int Rtag; struct Node* RChild; }BitNode, * BiTree; //先序创建二叉树 void CreatBiTree(BiTree* root) { char ch; ch = getchar(); if (ch == '.') *root

## binary-tree-inorder-traversal——二叉树中序遍历

Given a binary tree, return the inordertraversal of its nodes' values. For example:Given binary tree{1,#,2,3}, 1 2 / 3 return[1,3,2]. 1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 *

## C++中序线索化二叉树

1 #include <iostream> 2 using namespace std; 3 4 typedef struct TBTNode 5 { 6 char data; 7 int ltag,rtag; 8 struct TBTNode * lchild; 9 struct TBTNode * rchild; 10 }TBTNode; 11 12 TBTNode * initTBTNode() 13 { 14 TBTNode * p=(TBTNode*)malloc(sizeof(TB

## 二叉树中序非递归遍历

package com.basic.bt; import java.util.ArrayList; import java.util.Stack; /** * Created by mac on 2017/1/19. */ public class InOrderBT { ArrayList<Integer> result = new ArrayList<Integer>(); ArrayList<Integer> traversal = new ArrayList&l