189 8069 5689
算法思想：层次遍历目前最普遍用的就是队列的那种方式，不是递归，但是用到while循环，既然题目要求用递归，可以用递归实现该while循环功能。算法如下：
创新互联建站主要业务有网站营销策划、网站设计、成都网站制作、微信公众号开发、微信小程序、H5技术、程序开发等业务。一次合作终身朋友，是我们奉行的宗旨；我们不仅仅把客户当客户，还把客户视为我们的合作伙伴，在开展业务的过程中，公司还积累了丰富的行业经验、网络营销推广资源和合作伙伴关系资源，并逐渐建立起规范的客户服务和保障体系。
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r-ch);
if (r-left != NULL)
{
InsertQueue(r-left);
}
if (r-right != NULL)
{
InsertQueue(r-right);
}
Tree *t = DeleteQueue();
TransLevele(t);
}
//测试程序，创建树输入例如ABD##E##C##,根左右创建的方式。
如下代码是测试通过的。
#include "stdlib.h"
#define MAX 100
typedef int Element;
typedef struct tree
{
Element ch;
struct tree *left;
struct tree *right;
}Tree;
typedef struct queue
{
Tree *a[MAX];
int front;
int rear;
}Queue;
Queue Qu;
void Init();
int InsertQueue(Element ch);
Tree *DeleteQueue();
void CreateTree(Tree **r);
void TransLevele(Tree *r);
void PrintTree(Tree *r);
int main()
{
Tree *r=NULL;
CreateTree(r);
PrintTree(r);
printf("\n");
TransLevele(r);
return 0;
}
void Init()
{
int i=0;
for (i=0; iMAX; i++)
{
Qu.a[i] = NULL;
}
Qu.front = 0;
Qu.rear = 0;
}
int InsertQueue(Tree *r)
{
if ( (Qu.rear+1)%MAX == Qu.front)
{
printf("Queue full!");
return 0;
}
Qu.a[Qu.rear] = r;
Qu.rear = (Qu.rear+1)%MAX;
return 1;
}
Tree *DeleteQueue()
{
if (Qu.front == Qu.rear)
{
printf("Queue empty");
return NULL;
}
Tree *t=NULL;
t = Qu.a[Qu.front];
Qu.front = (Qu.front+1)%MAX;
return t;
}
void CreateTree(Tree **r)
{
Element ch;
ch=getchar();
if (ch=='#')
{
(*r)=NULL;
return ;
}
*r = (Tree *)malloc(sizeof(Tree));
(*r)-ch = ch;
CreateTree(((*r)-left));
CreateTree(((*r)-right));
}
void PrintTree(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r-ch);
PrintTree(r-left);
PrintTree(r-right);
}
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r-ch);
if (r-left != NULL)
{
InsertQueue(r-left);
}
if (r-right != NULL)
{
InsertQueue(r-right);
}
Tree *t = DeleteQueue();
TransLevele(t);
}
#include "stdio.h"
#include "stdlib.h"
typedef struct btnode//二叉链表类型定义
{char data;
struct btnode *lchild,*rchild;
}bintree,*Bintree;
typedef struct LinkQueueNode//链队列类型定义
{bintree *data;
struct LinkQueueNode *next;
}LKQueNode;
typedef struct LKQueue
{LKQueNode *front,*rear;
}LKQue;
void InitQueue(LKQue *LQ)//初始化队列
{LKQueNode *p;
p=(LKQueNode*)malloc(sizeof(LKQueNode));
LQ-front=p;
LQ-rear=p;
(LQ-front)-next=NULL;
}
int EmptyQueue(LKQue *LQ)//判断队列是否为空
{if(LQ-front==LQ-rear)
return 1;
else return 0;
}
void EnQueue(LKQue *LQ,Bintree x)//入队列
{LKQueNode *p;
p=(LKQueNode*)malloc(sizeof(LKQueNode));
p-data=x;
p-next=NULL;
(LQ-rear)-next=p;
LQ-rear=p;
}
int OutQueue(LKQue *LQ)//出队列
{LKQueNode *s;
if ( EmptyQueue(LQ))
{exit(0);return 0;}
else
{s=(LQ-front)-next;
(LQ-front)-next=s-next;
if(s-next==NULL)
LQ-rear=LQ-front;
free(s);
return 1;}
}
Bintree GetHead(LKQue *LQ)//取队列首元素
{LKQueNode *p;bintree *q;//q-data=-1; 错误在这里没有分配空间就赋值
if(EmptyQueue(LQ))
return q;
else {p=LQ-front-next;
return p-data;
}
}
Bintree initiate()//建二叉树
{char ch;Bintree t;
ch=getchar();
if(ch=='#') t=NULL;
else
{t=(Bintree)malloc(sizeof(bintree));
t-data=ch;
t-lchild=initiate();
t-rchild=initiate();
}
return t;
}
void Visit(Bintree p)//访问节点
{printf("%c",p-data); //输出是char
}
int height(Bintree t)
{int ld,rd;
if(t==NULL) return 0;
else
{ld=height(t-lchild);
rd=height(t-rchild);
return 1+(ldrd?ld:rd);
}
}
void levelorder(Bintree bt)//层次遍历
{LKQue Q;Bintree p;
InitQueue(Q);
if(bt!=NULL)
{EnQueue(Q,bt);
while(!EmptyQueue(Q))
{p=GetHead(Q);
OutQueue(Q);
Visit(p);
if(p-lchild!=NULL) EnQueue(Q,p-lchild);
if(p-rchild!=NULL) EnQueue(Q,p-rchild);
}
}
}
void main()
{Bintree T;
T=initiate();
printf("%d",height(T));
levelorder(T);
}
二叉树的前中后遍历（递归与非递归）
#includestdio.h
#includestdlib.h
typedef struct NODE
{
char value;
struct NODE *LChild;
struct NODE *RChild;
}BiTNode,*BiTree; //二叉树数据结构
BiTree root;
typedef struct node
{
BiTNode *pointer;
struct node *link;
}LinkStackNode,*LinkStack; //链栈数据结构
LinkStack S;
int count = 0;
//BiTNode * InitTree(BiTree Tree);
BiTNode *CreateTree(BiTree Tree); //创建二叉树
void PreOrder(BiTree Tree); //递归前序遍历二叉树
void MidOrder(BiTree Tree); //递归中序遍历二叉树
void PostOrder(BiTree Tree); //递归后序遍历二叉树
void NPreOrder(BiTree Tree); //非递归前序遍历二叉树
void NMidOrder(BiTree Tree); //非递归中序遍历二叉树
void NPostOrder(BiTree Tree); //非递归后序遍历二叉树
//---------------------------------------------------
LinkStackNode *InitLinkStack(LinkStack top); //初始化链栈
void Push(LinkStack top,BiTNode *p); //进栈操作
BiTNode * Pop(LinkStack top); //出栈操作
//int IsEmpty(LinkStack S); //判断栈是否为空
void main()
{
//BiTree tree;
//root = InitTree(tree);
root = CreateTree(root);
PreOrder(root);
printf("\n");
MidOrder(root);
printf("\n");
PostOrder(root);
printf("\n");
NPreOrder(root);
printf("\n");
NMidOrder(root);
printf("\n");
NPostOrder(root);
printf("\n");
}
/*BiTNode * InitTree(BiTree Tree)
{
//BiTNode *root;
//root = Tree;
Tree = (BiTNode *)malloc(sizeof(BiTNode));
Tree = NULL;
//Tree-LChild = NULL;
//Tree-RChild = NULL;
return Tree;
}*/
//二叉树的扩展先序遍历的创建
BiTNode * CreateTree(BiTree Tree)
{
char ch;
ch = getchar();
if(ch == '.')
Tree = NULL;
else
{
Tree = (BiTNode *)malloc(sizeof(BiTNode));
if(Tree)
{
Tree-value = ch;
Tree-LChild = CreateTree(Tree-LChild);
Tree-RChild = CreateTree(Tree-RChild);
}
}
return Tree;
}
//递归前序遍历二叉树
void PreOrder(BiTree Tree)
{
if(Tree)
{
printf("%c",Tree-value);
PreOrder(Tree-LChild);
PreOrder(Tree-RChild);
}
}
//递归中序遍历二叉树
void MidOrder(BiTree Tree)
{
if(Tree)
{
MidOrder(Tree-LChild);
printf("%c",Tree-value);
MidOrder(Tree-RChild);
}
}
//递归后序遍历二叉树
void PostOrder(BiTree Tree)
{
if(Tree)
{
PostOrder(Tree-LChild);
PostOrder(Tree-RChild);
printf("%c",Tree-value);
}
}
//非递归前序遍历二叉树
void NPreOrder(BiTree Tree)
{
BiTNode *p;
S = InitLinkStack(S);
p = Tree;
while(p || count != 0)
{
if(p)
{
if(p-RChild)
Push(S,p-RChild);
printf("%c",p-value);
p = p-LChild;
}
else
p = Pop(S);
}
}
//非递归中序遍历二叉树
void NMidOrder(BiTree Tree)
{
//char ch;
BiTNode *p;
S = InitLinkStack(S);
p = Tree;
while(p || count != 0)
{
if(p)
{
Push(S,p);
p = p-LChild;
}
else
{
p = Pop(S);
printf("%c",p-value);
p = p-RChild;
}
}
}
//非递归后序遍历二叉树
void NPostOrder(BiTree Tree)
{
BiTNode *p,*q = NULL;
S = InitLinkStack(S);
p = Tree;
while(p || count != 0)
{
if(p)
{
Push(S,p);
p = p-LChild;
}
else
{
p = S-link-pointer;
if(p-RChild == NULL || p-RChild == q)
{
p = Pop(S);
printf("%c",p-value);
q = p;
p = NULL;
}
else
{
//p = Pop(S);
p = p-RChild;
}
}
}
}
//初始化链栈
LinkStackNode *InitLinkStack(LinkStack top)
{
top = (LinkStackNode *)malloc(sizeof(LinkStackNode));
return top;
}
//进栈操作
void Push(LinkStack top,BiTNode *p)
{
LinkStackNode *temp;
temp = (LinkStackNode *)malloc(sizeof(LinkStackNode));
if(temp)
{
temp-pointer = p;
temp-link = top-link;
top-link = temp;
count++;
}
}
//出栈操作
BiTNode * Pop(LinkStack top)
{
//char ch;
BiTNode *p;
LinkStackNode *temp;
p = (BiTNode *)malloc(sizeof(BiTNode));
temp = top-link;
if(temp)
{
top-link = temp-link;
p = temp-pointer;
free(temp);
count--;
}
return p;
}
BinaryTree.h:
/********************************************************************
created: 2006/07/04
filename: BinaryTree.h
author: 李创
purpose: 演示二叉树的算法
*********************************************************************/
#ifndef BinaryTree_H
#define BinaryTree_H
＃i nclude stdlib.h
＃i nclude stack
class BinaryTree
{
private:
typedef int Item;
typedef struct TreeNode
{
Item Node;
TreeNode* pRight;
TreeNode* pLeft;
TreeNode(Item node = 0, TreeNode* pright = NULL, TreeNode* pleft = NULL)
: Node(node)
, pRight(pright)
, pLeft(pleft)
{
}
}TreeNode, *PTreeNode;
public:
enum TraverseType
{
PREORDER = 0, // 前序
INORDER = 1, // 中序
POSTORDER = 2, // 后序
LEVELORDER = 3 // 层序
};
BinaryTree(Item Array[], int nLength);
~BinaryTree();
PTreeNode GetRoot()
{
return m_pRoot;
}
// 遍历树的对外接口
// 指定遍历类型和是否是非递归遍历,默认是递归遍历
void Traverse(TraverseType traversetype, bool bRec = true);
private:
PTreeNode CreateTreeImpl(Item Array[], int nLength);
void DetroyTreeImpl(PTreeNode pTreenode);
void PreTraverseImpl(PTreeNode pTreenode); // 递归前序遍历树
void InTraverseImpl(PTreeNode pTreenode); // 递归中序遍历树
void PostTraverseImpl(PTreeNode pTreenode); // 递归后序遍历树
void NoRecPreTraverseImpl(PTreeNode pTreenode); // 非递归前序遍历树
void NoRecInTraverseImpl(PTreeNode pTreenode); // 非递归中序遍历树
void NoRecPostTraverseImpl(PTreeNode pTreenode); // 非递归后序遍历树
void LevelTraverseImpl(PTreeNode pTreenode);
PTreeNode m_pRoot; // 根结点
// 采用STL里面的stack作为模拟保存链表结点的stack容器
typedef std::stackBinaryTree::PTreeNode TreeNodeStack;
};
#endif
BinaryTree.cpp:
/********************************************************************
created: 2006/07/04
filename: BinaryTree.cpp
author: 李创
purpose: 演示二叉树的算法
*********************************************************************/
＃i nclude iostream
＃i nclude assert.h
＃i nclude queue
＃i nclude "BinaryTree.h"
BinaryTree::BinaryTree(Item Array[], int nLength)
: m_pRoot(NULL)
{
assert(NULL != Array);
assert(nLength 0);
m_pRoot = CreateTreeImpl(Array, nLength);
}
BinaryTree::~BinaryTree()
{
DetroyTreeImpl(m_pRoot);
}
// 按照中序递归创建树
BinaryTree::PTreeNode BinaryTree::CreateTreeImpl(Item Array[], int nLength)
{
int mid = nLength / 2;
PTreeNode p = new TreeNode(Array[mid]);
if (nLength 1)
{
p-pLeft = CreateTreeImpl(Array, nLength / 2);
p-pRight = CreateTreeImpl(Array + mid + 1, nLength / 2 - 1);
}
return p;
}
void BinaryTree::DetroyTreeImpl(PTreeNode pTreenode)
{
if (NULL != pTreenode-pLeft)
{
DetroyTreeImpl(pTreenode-pLeft);
}
if (NULL != pTreenode-pRight)
{
DetroyTreeImpl(pTreenode-pRight);
}
delete pTreenode;
pTreenode = NULL;
}
// 遍历树的对外接口
// 指定遍历类型和是否是非递归遍历,默认是递归遍历
void BinaryTree::Traverse(TraverseType traversetype, bool bRec /*= true*/)
{
switch (traversetype)
{
case PREORDER: // 前序
{
if (true == bRec)
{
std::cout "递归前序遍历树\n";
PreTraverseImpl(m_pRoot);
}
else
{
std::cout "非递归前序遍历树\n";
NoRecPreTraverseImpl(m_pRoot);
}
}
break;
case INORDER: // 中序
{
if (true == bRec)
{
std::cout "递归中序遍历树\n";
InTraverseImpl(m_pRoot);
}
else
{
std::cout "非递归中序遍历树\n";
NoRecInTraverseImpl(m_pRoot);
}
}
break;
case POSTORDER: // 后序
{
if (true == bRec)
{
std::cout "递归后序遍历树\n";
PostTraverseImpl(m_pRoot);
}
else
{
std::cout "非递归后序遍历树\n";
NoRecPostTraverseImpl(m_pRoot);
}
}
break;
case LEVELORDER: // 层序
{
std::cout "层序遍历树\n";
LevelTraverseImpl(m_pRoot);
}
}
std::cout std::endl;
}
// 递归前序遍历树
void BinaryTree::PreTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;
std::cout "Item = " pTreenode-Node std::endl;
PreTraverseImpl(pTreenode-pLeft);
PreTraverseImpl(pTreenode-pRight);
}
// 非递归前序遍历树
void BinaryTree::NoRecPreTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;
TreeNodeStack NodeStack;
PTreeNode pNode;
NodeStack.push(pTreenode);
while (!NodeStack.empty())
{
while (NULL != (pNode = NodeStack.top())) // 向左走到尽头
{
std::cout "Item = " pNode-Node std::endl; // 访问当前结点
NodeStack.push(pNode-pLeft); // 左子树根结点入栈
}
NodeStack.pop(); // 左子树根结点退
栈
if (!NodeStack.empty())
{
pNode = NodeStack.top();
NodeStack.pop(); // 当前结点退栈
NodeStack.push(pNode-pRight); // 当前结点的右子树根结点入栈
}
}
}
// 中序遍历树
// 中序遍历输出的结果应该和用来初始化树的数组的排列顺序一致
void BinaryTree::InTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;
if (NULL != pTreenode-pLeft)
{
InTraverseImpl(pTreenode-pLeft);
}
std::cout "Item = " pTreenode-Node std::endl;
if (NULL != pTreenode-pRight)
{
InTraverseImpl(pTreenode-pRight);
}
}
// 非递归中序遍历树
void BinaryTree::NoRecInTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;
TreeNodeStack NodeStack;
PTreeNode pNode;
NodeStack.push(pTreenode);
while (!NodeStack.empty())
{
while (NULL != (pNode = NodeStack.top())) // 向左走到尽头
{
NodeStack.push(pNode-pLeft);
}
NodeStack.pop();
if (!NodeStack.empty() NULL != (pNode = NodeStack.top()))
{
std::cout "Item = " pNode-Node std::endl;
NodeStack.pop();
NodeStack.push(pNode-pRight);
}
}
}
// 后序遍历树
void BinaryTree::PostTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;
if (NULL != pTreenode-pLeft)
{
PostTraverseImpl(pTreenode-pLeft);
}
if (NULL != pTreenode-pRight)
{
PostTraverseImpl(pTreenode-pRight);
}
std::cout "Item = " pTreenode-Node std::endl;
}
// 非递归后序遍历树
void BinaryTree::NoRecPostTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;
TreeNodeStack NodeStack;
PTreeNode pNode1, pNode2;
NodeStack.push(pTreenode);
pNode1 = pTreenode-pLeft;
bool bVisitRoot = false; // 标志位,是否访问过根结点
while (!NodeStack.empty())
{
while (NULL != pNode1) // 向左走到尽头
{
NodeStack.push(pNode1);
pNode1 = pNode1-pLeft;
}
pNode1 = NodeStack.top();
NodeStack.pop();
if (NULL == pNode1-pRight) // 如果没有右子树就是叶子结点
{
std::cout "Item = " pNode1-Node std::endl;
pNode2 = pNode1;
pNode1 = NodeStack.top();
if (pNode2 == pNode1-pRight) // 如果这个叶子结点是右子树
{
std::cout "Item = " pNode1-Node std::endl;
NodeStack.pop();
pNode1 = NULL;
}
else // 否则访问右子树
{
pNode1 = pNode1-pRight;
}
}
else // 访问右子树
{
if (pNode1 == pTreenode true == bVisitRoot) // 如果已经访问过右子树那么就退出
{
std::cout "Item = " pNode1-Node std::endl;
return;
}
else
{
if (pNode1 == pTreenode)
{
bVisitRoot = true;
}
NodeStack.push(pNode1);
pNode1 = pNode1-pRight;
}
}
}
}
// 按照树的层次从左到右访问树的结点
void BinaryTree::LevelTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;
// 层序遍历用于保存结点的容器是队列
std::queuePTreeNode NodeQueue;
PTreeNode pNode;
NodeQueue.push(pTreenode);
while (!NodeQueue.empty())
{
pNode = NodeQueue.front();
NodeQueue.pop();
std::cout "Item = " pNode-Node std::endl;
if (NULL != pNode-pLeft)
{
NodeQueue.push(pNode-pLeft);
}
if (NULL != pNode-pRight)
{
NodeQueue.push(pNode-pRight);
}
}
}
main.cpp
/********************************************************************
created: 2006/07/04
filename: main.cpp
author: 李创
purpose: 测试二叉树的算法
*********************************************************************/
＃i nclude "BinaryTree.h"
＃i nclude stdio.h
＃i nclude stdlib.h
＃i nclude time.h
＃i nclude iostream
void DisplayArray(int array[], int length)
{
int i;
for (i = 0; i length; i++)
{
printf("array[%d] = %d\n", i, array[i]);
}
}
void CreateNewArray(int array[], int length)
{
for (int i = 0; i length; i++)
{
array[i] = rand() % 256 + i;
}
}
int main()
{
int array[10];
srand(time(NULL));
// 创建数组
CreateNewArray(array, 10);
DisplayArray(array, 10);
BinaryTree *pTree = new BinaryTree(array, 10);
// 测试前序遍历
pTree-Traverse(BinaryTree::PREORDER);
std::cout "root = " pTree-GetRoot()-Node std::endl;
std::cout "root-left = " pTree-GetRoot()-pLeft-Node std::endl;
std::cout "root-right = " pTree-GetRoot()-pRight-Node std::endl;
pTree-Traverse(BinaryTree::PREORDER, false);
// 测试中序遍历
pTree-Traverse(BinaryTree::INORDER);
std::cout "root = " pTree-GetRoot()-Node std::endl;
std::cout "root-left = " pTree-GetRoot()-pLeft-Node std::endl;
std::cout "root-right = " pTree-GetRoot()-pRight-Node std::endl;
pTree-Traverse(BinaryTree::INORDER, false);
// 测试后序遍历
pTree-Traverse(BinaryTree::POSTORDER);
std::cout "root = " pTree-GetRoot()-Node std::endl;
std::cout "root-left = " pTree-GetRoot()-pLeft-Node std::endl;
std::cout "root-right = " pTree-GetRoot()-pRight-Node std::endl;
pTree-Traverse(BinaryTree::POSTORDER, false);
// 测试层序遍历
pTree-Traverse(BinaryTree::LEVELORDER);
system("pause");
delete pTree;
return 0;
}