好像就是线索二叉树,
下面是二叉树创建、遍历程序,没有线索二叉树。仅供参考。。。
//------------------------------------------------------------------------------
// Copyright (c) 2009 eryar All rights reserved.
//
// File : BinTree.h
// Author :
[email protected]// Date : 2009-9-13 19:07
// Version : 1.0v
//
// Description : Binary tree declaration
//
//==============================================================================
#ifndef _BINTREE_H_
#define _BINTREE_H_
#include <iostream>
using namespace std;
typedef char ElemType;
typedef struct Node{
ElemType data;
struct Node* lChild;
struct Node* rChild;
}Node;
typedef struct Node* BinTree;
//------------------------------------------------------------------------
bool InitBinTree(BinTree* T);
void CreateBinTree(BinTree* T);
void PreOrderTraverse(BinTree T);
void InOrderTraverse(BinTree T);
void PostOrderTraverse (BinTree T);
void LevelOrderTraverse(BinTree T);
bool isEmpty(BinTree T);
//========================================================================
#endif // _BINTREE_H_
//------------------------------------------------------------------------------
// Copyright (c) 2009 eryar All rights reserved.
//
// File : BinTree.cpp
// Author :
[email protected]// Date : 2009-9-13 19:11
// Version : 1.0v
//
// Description : Binary tree definition
//
//==============================================================================
#include "BinTree.h"
/*
Parameter : BinTree*
Return : true or false
Description : initialize the binary tree
*/
bool InitBinTree(BinTree* T) {
*T = NULL;
return true;
} // InitBinTree
/*
Parameter : BinTree*
Return : none
Description : create a binary tree in preorder
*/
void CreateBinTree(BinTree* T) {
ElemType elem;
cin>>elem;
if (elem == '#') {
*T = NULL;
}
else {
*T = new Node;
(*T)->data = elem;
CreateBinTree(&(*T)->lChild);
CreateBinTree(&(*T)->rChild);
}
} // CreateBinTree
/*
Parameter : BinTree*
Return : true or false
Description : PreOrder visit binary tree
*/
void PreOrderTraverse(BinTree T) {
if (T) {
cout<<"node is : "<<T->data<<endl;
PreOrderTraverse(T->lChild);
PreOrderTraverse(T->rChild);
}
} // PreOrderTraverse
/*
Parameter : BinTree
Return : true or false
Description : inorder traverse binary tree
*/
void InOrderTraverse(BinTree T) {
if (T) {
InOrderTraverse(T->lChild);
cout<<"node is : "<<T->data<<endl;
InOrderTraverse(T->rChild);
}
} // InOrderTraverse
/*
Parameter : BinTree
Return : true or false
Description : PostOrder traverse binary tree
*/
void PostOrderTraverse(BinTree T) {
if (T) {
PostOrderTraverse(T->lChild);
PostOrderTraverse(T->rChild);
cout<<"node is : "<<T->data<<endl;
}
} // PostOrderTraverse
/*
Parameter : BinTree
Return : none
Description : Level order traverse the binary tree
*/
void LevelOrderTraverse(BinTree T) {
} // LevelOrderTraverse
/*
Parameter : BinTree
Return : true or false
Description : if tree is empty return true
*/
bool isEmpty(BinTree T) {
if (T) {
return false;
}
else {
return true;
}
} // isEmpty
//------------------------------------------------------------------------------
// Copyright (c) 2009 eryar All rights reserved.
//
// File : main.cpp
// Author :
[email protected]// Date : 2009-9-13 19:04
// Version : 1.0v
//
// Description : Binary tree use C to implemention
//
//==============================================================================
#include "BinTree.h"
int main(int argc, char *argv[])
{
BinTree tree;
InitBinTree(&tree);
cout<<"先序遍历法创建二叉树:";
CreateBinTree(&tree);
BinTree visit = tree;
cout<<"先序遍历:"<<endl;
PreOrderTraverse(visit);
cout<<"中序遍历:"<<endl;
visit = tree;
InOrderTraverse(visit);
cout<<"后序遍历:"<<endl;
visit = tree;
PostOrderTraverse(visit);
return 0;
}
本回答被网友采纳