当前位置：首页 -> 基础 -> c++编程基础

二叉树 建立 非递归-前序-中序-后序-广度优先遍历 (一)

2014-11-24 02:54:25 · 作者: · 浏览: 5
标签: 建立 前序 中序 后序 广度 优先

二叉树是数据结构中非常基本 但是非常重要的一种
它是最小堆 二叉搜索树 AVL树 红黑树的基础
对于二叉树的各种操作必须完全理解透彻才行
[cpp]
#include
#include
#include
#include

typedef int KeyType;

//二叉树节点
typedef struct Node
{
KeyType key;
Node* lChild;
Node* rChild;
}Node, *PNode;


//建树函数 此处采用了递归的方式建树
void createTree(PNode& root)
{
int temp;
scanf("%d", &temp);
//输入0表示当前节点建立结束
if(temp == 0)
{
root = NULL;
return;
}
else
{
root = (PNode)malloc(sizeof(Node));
root->key = temp; //初始化当前节点
createTree(root->lChild); //初始化当前节点左孩子
createTree(root->rChild); //初始化当前节点右孩子
}
}

//前序递归遍历 不做详述
void preOrder(PNode root)
{
if(!root)
return;
preOrder(root->lChild);
printf("%3d", root->key);
preOrder(root->rChild);
}


//前序非递归遍历
void preOrderNonRecursive(PNode root)
{
PNode p = root;
stack node_stack;//采用栈作为辅助结构
while(p || !node_stack.empty())
{
//定位到当前节点的最左节点（注意：此处最左节点也被放入了栈中）
while(p)
{
node_stack.push(p);
p = p->lChild;
}
//定位到当前节点最左节点之后访问之 然后访问它的右子节点
if(!node_stack.empty())
{
p = node_stack.top();
node_stack.pop();
printf("%3d", p->key);
p = p->rChild;
}
}
}

//中序遍历
void inOrder(PNode root)
{
if(!root)
return;
PNode p = root;
printf("%3d", p->key);
inOrder(p->lChild);
inOrder(p->rChild);

}

//中序非递归遍历
//很多人讲中序非递归遍历比前序和后序非递归遍历要困难
//个人以为这只是因为对前序和后序非递归遍历的理解不够透彻
void inOrderNonRecursive(PNode root)
{
stack node_stack;
PNode p = root;
while(p || !node_stack.empty())
{
//沿左子树挨个访问根节点 一直到最左子节点 同时将他们放入栈中
//注意：在中序遍历中，将节点放入栈中是为了回溯时可以定位到他们的右子节点，但是由于他们本身已经被访问过，
//所以在弹出栈的时候只需要直接去处理他们的右子节点即可
while(p)
{
printf("%3d", p->key);
node_stack.push(p);
p = p->lChild;
}
if(!node_stack.empty())
{
p = node_stack.top();
node_stack.pop();
p = p->rChild; //如前所述，直接处理其右子节点 并不对栈中元素本身做处理
}
}
}

//后序递归遍历
void postOrder(PNode root)
{
if(!root)
return;
PNode p = root;
postOrder(p->rChild);
printf("%3d", p->key);
postOrder(p->lChild);
}


//后序非递归遍历
//跟前序遍历一个道理 此处不作赘述
void postOrderNonRecursive(PNode root)
{
stack node_stack;
PNode p = root;
while(p || !node_stack.empty())
{
while(p)
{
node_stack.push(p);
p = p->rChild;
}
if(!node_stack.empty())
{
p = node_stack.top();
node_stack.pop();
printf("%3d", p->key);
p = p->lChild;
}
}
}

//深度优先遍历
//深度优先遍历的思想就是先将根节点放入队列，然后对队列中的每个节点，访问完头部节点之后，弹出头节点，
//同时将头结点的左子节点和右子节点放入队列，如此循环即可
void depthFirst(PNode root)
{
if(!root)
return;
queue node_queue;
PNode p = root;
node_queue.push(p);
while(!node_queue.empty())
{
p = node_queue.front();
printf("%3d", p->key);
node_queue.pop();
if(p->lChild)
node_queue.push(p->lChild);
if(p->rChild)
node_queue.push(p->rChild);