 #include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef int DATATYPE;
int n, countLevel = 0;
typedef struct BinTreeNode
   {
 DATATYPE data;
struct BinTreeNode* rChild;
struct BinTreeNode* lChild;
 }tree;
tree* stack[100];
tree* CreateBinTree( DATATYPE* s, int i)//遞歸創建二叉樹
{
if (i > n || s == 0)
  {
return NULL;
 }
else
{
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)
{
if (root != NULL)
{
printf("%d\t", root->data);
PreOrder(root->lChild);//一直遍歷直到找到第一個空結點。
PreOrder(root->rChild);//遍歷右孩子
}
}
//非遞歸前序遍歷二叉樹
void preOrder(tree* root)
{
int i = -1;
if (root != NULL)
{
stack[++i] = root;//只將非空的根節點入棧
}
while (root != NULL)
{
//前序遍歷先遍歷根結點，再遍歷左子樹，再遍歷右子樹，所以對于根結點，一找到就輸出，然后右孩子、左孩子分別入棧。
root = stack;
printf("%d\t", root->data);
if (root->rChild != NULL)
{
stack[++i] = root->rChild;
}
if (root->lChild != NULL)
{
stack[++i] = root->lChild;
}
if (i == -1)//當棧空時結束
{
return ;
}
}
}
//非遞歸中序遍歷二叉樹
void inorder(tree* root)
{
int i = -1,j;
for(;;)
{
while (root != NULL)//對左孩子入棧
{
i++;
stack = root;
root = root->lChild;
}
if (i != -1)//棧非空
{
root = stack;//root指向棧頂元素
i--;
printf("%d\t", root->data);
root = root->rChild;//遍歷棧頂元素，即root的右孩子
}
else
{
return;//棧空結束
}
}
}
//非遞歸后序遍歷二叉樹1
void postOrder(tree* root)
{
int i = -1, j;
int a[100];
for(;;)
{
while (root != NULL)//對左孩子入棧
{
stack[++i] = root;
a = 0;//設置此結點為沒被訪問過
root = root->lChild;
}
if (i == -1)//棧空結束
{
return;
}
else
{
root = stack;
if (a == 0)//針對沒被訪問過的結點，訪問其右子樹，并設置該結點為已訪問過的結點
{
root = root->rChild;
a = 1;
}
else//打印已訪問過的結點，并將該結點置為空結點，以防訪問其父結點時會在將它再次入棧
{
printf("%d\t", root->data);
i--;
root = NULL;
}
}
}
}
//非遞歸后序遍歷二叉樹2
void postorderz2(BinNode * p)
{
BinNode* s[10];
int top = -1;
while (1)
{
while (p != NULL)
{
s[++top] = p;
p = p->lchild;
}
while (1)
{
if (s[top]->rchild != NULL)//[1]
{
p = s[top]->rchild;
break;
}
while (top != -1)
{
//右孩子為空時可以直接打印，即是為當前子樹的最又葉子。當s[top]->rchild==p時，p表示已被訪問的結點，所以可以打印s[top]
if (s[top]->rchild == NULL || s[top]->rchild == p)
{
p = s[top--];
printf("%c\t", p->data);
}
else//否則，表示s[top]的右孩子沒被訪問過且s[top] 存在右孩子，所以要對右孩子入棧,返回[1]
{
break;
}
}
if (top == -1)
{
return ;
}
}
}
}
//按層遍歷二叉樹
void levelorder(tree* root)
{
int front = 0, rear = 0;
if (root != NULL)
{
rear++;
stack[rear] = root;//將根結點入隊
}
while (front != rear)//隊非空時，將隊尾元素出隊，并將它的左右子樹入隊。
{
front++;
root = stack[front];
printf("%d\t", root->data);
if (root->lChild != NULL)
{
stack[++rear] = root->lChild;
}
if (root->rChild != NULL)
{
stack[++rear] = root->rChild;
}
}
}
//先序計算二叉樹的層
void predeep(tree* root, int i)
{
if (root != NULL)
{
i++;
if (countLevel < i)//counLevel是全局變量，當當前的i>countLevel是，將i賦給countLevel，此時countLevel為當前的最大層數
{
countLevel = i;
}
predeep(root->lChild, i);
predeep(root->rChild, i);
}
}
//前序遍歷查找
tree* FindNode(tree* root, DATATYPE key)
{
tree* left, *right;
if (root != NULL)
{
if (root->data == key)
{
return root;
}
else
{
left = FindNode(root->lChild, key);
if (left != NULL)
{
return left;
}
right = FindNode(root->rChild, key);
if (right != NULL)
{
return right;
}
}
return NULL;
}
return NULL;
}
int main()
{
int i, key;
DATATYPE s[MAXSIZE];
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
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)
{
scanf("%d", &key);
tree* aim = FindNode(root, key);
if (aim != NULL)
{
printf("%d\n", aim->data);
}
else
{
printf("Can't find it\n");
}
}
return 0;
}
/**//*
9
1 2 3 4 5 6 7 8 9
*/
|