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

中序线索二叉树


/************************************************************************
线索二叉树
二叉树的节点有五部分构造
-----------------------------------------
| lChild | lTag | value | rTag | rChild |
-----------------------------------------

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

对二叉树通过某种遍历将其变为线索二叉树的过程成为二叉树的线索化。

设置一个头结点,头结点的lChild指向根节点
rChild指向遍历次序的最后一个节点
遍历次序的第一个节点lChild指向头结点
遍历次序的最后一个节点的最后一个节点

************************************************************************/


#ifndef OVERFLOW_FOR_MALLOC
#define OVERFLOW_FOR_MALLOC (-1)
#endif

typedef enum{Link = 0, Thread = 1 }ThreadEnum;

typedef struct _tagBinaryTree
{
unsigned char value;
struct _tagBinaryTree* left;
struct _tagBinaryTree* right;
ThreadEnum lTag;
ThreadEnum rTag;
}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;
pNode->lTag = Link;
pNode->rTag = Link;
InitBinaryTree(pNode->left);
InitBinaryTree(pNode->right);
}
}


//递归中序线索化
//p为根节点
//pPreNode为一个辅助节点
void InThreading(PBinaryTree& p, PBinaryTree& pPreNode)
{
if (p)
{
InThreading(p->left, pPreNode);
if (! p->left)
{
p->lTag = Thread;
p->left = pPreNode;
}
if (! pPreNode->right)
{
pPreNode->rTag = Thread;
pPreNode->right = p;
}
pPreNode = p;
InThreading(p->right, pPreNode);
}
}


//中序线索二叉树, 为头结点申请空间,初始化头结点指针
//中序线索化后
//Thrt为头结点,T为二叉树的根节点
void InOrderThreading(PBinaryTree& Thrt, PBinaryTree T)
{
if(NULL == T) return;

Thrt = (PBinaryTree)(malloc(sizeof(BinaryTree)));
if(NULL == Thrt)
{
cerr << "创建头节点不成功\r\n"<<endl;
return;
}

//初始化头结点,左指针为Link,指向根节点;右指针为Thread,回指.
Thrt->lTag = Link;
Thrt->rTag = Thread;

Thrt->left = T;
Thrt->right = Thrt;

PBinaryTree pPreNode = Thrt;
InThreading(T, pPreNode);
pPreNode->right = Thrt;
pPreNode->rTag = Thread;
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;
InOrderThreading(pNode, pRoot);
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

时间: 05-16

【算法与数据结构】二叉树 中序线索的相关文章

数据结构:中序线索二叉树

//所谓线索二叉树无非是为了让原本指向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

经典白话算法之二叉树中序前序序列(或后序)求解树

这种题一般有二种形式,共同点是都已知中序序列.如果没有中序序列,是无法唯一确定一棵树的. <1>已知二叉树的前序序列和中序序列,求解树. 1.确定树的根节点.树根是当前树中所有元素在前序遍历中最先出现的元素. 2.求解树的子树.找出根节点在中序遍历中的位置,根左边的所有元素就是左子树,根右边的所有元素就是右子树.若根节点左边或右边为空,则该方向子树为空:若根节点 边和右边都为空,则根节点已经为叶子节点. 3.递归求解树.将左子树和右子树分别看成一棵二叉树,重复1.2.3步,直到所有的节点完成定

中序线索化二叉树

中序线索化二叉树 1 void Tree::_inTree(Node * root, Node * &pre) { 2 if (root == NULL) { // 结点为空, 1:二叉树为空 2:已到达右子树的最后一个右结点的 rchild 3 return; 4 } 5 _inTree(root->lchild, pre); // 到达当前结点的左子树的底部左结点 6 if (root->lchild == NULL) { 7 root->ltag = nChild; //

Leetcode: Binary Tree Inorder Traversal(二叉树中序遍历)

题目: Given a binary tree, return the inorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, 1 2 / 3 return [1,3,2]. Note: Recursive solution is trivial, could you do it iteratively? 递归解法(C++): /** * Definition for binary tre

4.6---找二叉树中序后继(CC150)

因为,没有重复值,所以只需要做一个标记就OK了. public class Successor { static boolean flag = false; static int result = 0; public int findSucc(TreeNode root, int p) { // write code here inOrder(root,p); return result; } public static void inOrder(TreeNode root,int p){ if

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