/* 先序創建一棵任意二叉樹 */
/* 注意：輸入資料的順序很有特點，本題輸入的順序要求為，先是根節點，再是左子樹，再是右子樹 */
#include <iostream>
#include <malloc.h>
using namespace std;
typedef int ElementType; //給int起別名為ElementType, typedef是起別名的意思
typedef struct bitnode //定義二叉樹節點資料型別
{
ElementType data;
struct bitnode *left, *right;
} bitnode, *bitree; //bitree為指向bitnode這種結構的指標
//先序創建一棵二叉樹
bitree PerCreateTree()
{
bitree T;
ElementType item;
cin >> item;
if( item == 0 ) //葉節點資料標志：其后根兩個0
T = NULL; //若某一節點為葉子結點，則其左右子樹均為NULL，0表示建空樹
else
{
T = (bitree)malloc(sizeof(bitnode));
T->data = https://www.cnblogs.com/liyajuan333/p/item;
T->left = PerCreateTree(); //遞回創建其左子樹
T->right = PerCreateTree(); //遞回創建其右子樹
}
return T; //回傳根節點
}
//先序遞回遍歷二叉樹
void PerOrder(bitree T)
{
if( T ) // T != NULL
{
cout << T->data << " ";
PerOrder(T->left); //遞回先序周游其左子樹
PerOrder(T->right); //遞回先序周游其右子樹
}
}
void InOrder(bitree T)
{
if(T)
{
InOrder(T->left);
cout<<T->data<<" ";
InOrder(T->right);
}
}
void inorder(bitree T)
{
//還是模擬上面的遍歷程序
bitree ptr[20];
int top = -1;
/*下面的雙重判斷和前面的一樣，在進堆疊、出堆疊的程序中可能會出現堆疊空的情況，而此時的遍歷還沒有結束，
所以需要據此來維持回圈的進行，*/
while(T || top!=-1)
{
while(T)
{
ptr[++top] = T;
T = T->left;
}
if(top!=-1)
{
T = ptr[top--];
cout<<T->data<<" "; //輸出在出堆疊后
T = T->right;
}
}
}
//后序遞回遍歷二叉樹
void PostOrder(bitree T)
{
if( T ) // T != NULL
{
PostOrder(T->left); //遞回先序周游其左子樹
PostOrder(T->right); //遞回先序周游其右子樹
cout << T->data << " ";
}
}
//釋放空間
bitree FreeTree(bitree T)
{
if( T )
{
FreeTree(T->left); //遞回釋放其左子樹
FreeTree(T->right); //遞回釋放其右子樹
free(T); //釋放根節點
T = NULL; //釋放指向根節點的指標
}
return T; //回傳釋放后的根節點NULL
}
int main()
{
bitree root;
cout << "請輸入資料先序創建一棵二叉樹：";
root = PerCreateTree(); //先序創建一棵二叉樹
cout << "先序遞回遍歷的結果：";
PerOrder(root); //先序遞回遍歷
cout << endl;
cout << "中序遞回遍歷的結果：";
InOrder(root); //中序遞回遍歷
cout << endl;
cout << "中序非遞回遍歷的結果：";
inorder(root); //中序非遞回遍歷
cout << endl;
cout << "后序遞回遍歷的結果：";
PostOrder(root); //后序遞回遍歷
cout << endl;
return 0;
}
運行結果：
請輸入資料先序創建一棵二叉樹：4 6 8 0 0 1 0 0 2 0 0
先序遞回遍歷的結果：4 6 8 1 2
中序遞回遍歷的結果：8 6 1 4 2
中序非遞回遍歷的結果：8 6 1 4 2
后序遞回遍歷的結果：8 1 6 2 4
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/87990.html
標籤：C++