#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef int DATATYPE;
int n, countLevel = 0;
typedef struct BinTreeNode
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
DATATYPE data;
struct BinTreeNode* rChild;
struct BinTreeNode* lChild;
}tree;
tree* stack[100];
tree* CreateBinTree( DATATYPE* s, int i)//递归创建二叉树
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
if (i > n || s == 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return NULL;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
tree* node = (tree*)malloc(sizeof(tree));
node->data = s;
node->lChild = CreateBinTree( s, i * 2);//插入左孩子
node->rChild = CreateBinTree( s, i * 2 + 1);//插入右孩子
return node;
}
}
//递归前序遍历二叉树
void PreOrder(tree* root)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
if (root != NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf("%d\t", root->data);
PreOrder(root->lChild);//一直遍历直到找到第一个空结点。
PreOrder(root->rChild);//遍历右孩子
}
}
//非递归前序遍历二叉树
void preOrder(tree* root)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i = -1;
if (root != NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
stack[++i] = root;//只将非空的根节点入栈
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while (root != NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
//前序遍历先遍历根结点,再遍历左子树,再遍历右子树,所以对于根结点,一找到就输出,然后右孩子、左孩子分别入栈。
root = stack;
printf("%d\t", root->data);
if (root->rChild != NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
stack[++i] = root->rChild;
}
if (root->lChild != NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
stack[++i] = root->lChild;
}
if (i == -1)//当栈空时结束
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return ;
}
}
}
//非递归中序遍历二叉树
void inorder(tree* root)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i = -1,j;
for(;;)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
while (root != NULL)//对左孩子入栈
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
i++;
stack = root;
root = root->lChild;
}
if (i != -1)//栈非空
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
root = stack;//root指向栈顶元素
i--;
printf("%d\t", root->data);
root = root->rChild;//遍历栈顶元素,即root的右孩子
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return;//栈空结束
}
}
}
//非递归后序遍历二叉树1
void postOrder(tree* root)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i = -1, j;
int a[100];
for(;;)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
while (root != NULL)//对左孩子入栈
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
stack[++i] = root;
a = 0;//设置此结点为没被访问过
root = root->lChild;
}
if (i == -1)//栈空结束
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
root = stack;
if (a == 0)//针对没被访问过的结点,访问其右子树,并设置该结点为已访问过的结点
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
root = root->rChild;
a = 1;
}
else//打印已访问过的结点,并将该结点置为空结点,以防访问其父结点时会在将它再次入栈
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf("%d\t", root->data);
i--;
root = NULL;
}
}
}
}
//非递归后序遍历二叉树2
void postorderz2(BinNode * p)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
BinNode* s[10];
int top = -1;
while (1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
while (p != NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
s[++top] = p;
p = p->lchild;
}
while (1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if (s[top]->rchild != NULL)//[1]
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
p = s[top]->rchild;
break;
}
while (top != -1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
//右孩子为空时可以直接打印,即是为当前子树的最又叶子。当s[top]->rchild==p时,p表示已被访问的结点,所以可以打印s[top]
if (s[top]->rchild == NULL || s[top]->rchild == p)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
p = s[top--];
printf("%c\t", p->data);
}
else//否则,表示s[top]的右孩子没被访问过且s[top] 存在右孩子,所以要对右孩子入栈,返回[1]
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
break;
}
}
if (top == -1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return ;
}
}
}
}
//按层遍历二叉树
void levelorder(tree* root)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int front = 0, rear = 0;
if (root != NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
rear++;
stack[rear] = root;//将根结点入队
}
while (front != rear)//队非空时,将队尾元素出队,并将它的左右子树入队。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
front++;
root = stack[front];
printf("%d\t", root->data);
if (root->lChild != NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
stack[++rear] = root->lChild;
}
if (root->rChild != NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
stack[++rear] = root->rChild;
}
}
}
//先序计算二叉树的层
void predeep(tree* root, int i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
if (root != NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
i++;
if (countLevel < i)//counLevel是全局变量,当当前的i>countLevel是,将i赋给countLevel,此时countLevel为当前的最大层数
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
countLevel = i;
}
predeep(root->lChild, i);
predeep(root->rChild, i);
}
}
//前序遍历查找
tree* FindNode(tree* root, DATATYPE key)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
tree* left, *right;
if (root != NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if (root->data == key)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return root;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
left = FindNode(root->lChild, key);
if (left != NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return left;
}
right = FindNode(root->rChild, key);
if (right != NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return right;
}
}
return NULL;
}
return NULL;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i, key;
DATATYPE s[MAXSIZE];
scanf("%d", &n);
for (i = 1; i <= n; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%d", &s);
}
tree* root = NULL;
root = CreateBinTree( s, 1);
PreOrder(root);
printf("前序\n");
preOrder(root);
printf("前序\n");
inorder(root);
printf("中序\n");
postOrder(root);
printf("后序1\n");
postorderz2(root);
printf("后序2\n");
levelorder(root);
printf("按层\n");
predeep(root, 0);
printf("%d\n", countLevel);
while (1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%d", &key);
tree* aim = FindNode(root, key);
if (aim != NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf("%d\n", aim->data);
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf("Can't find it\n");
}
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*
9
1 2 3 4 5 6 7 8 9
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|