// 二叉樹.cpp : 此檔案包含 "main" 函式。程式執行將在此處開始并結束。
//
#include<iostream>
using namespace std;
typedef struct BiTNode
{
char data;
struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
void InitBiTree(BiTree& T)
{
char c;
cin >> c;
if (c == '#')
T = NULL;
else
{
T = new BiTNode;
T->data = c;
InitBiTree(T->lchild);
InitBiTree(T->rchild);
}
}
void PreOrderTravel1(BiTree T)
{
if (T)
{
cout << T->data;
PreOrderTravel1(T->lchild);
PreOrderTravel1(T->rchild);
}
}
//中序
void InOrderTravel1(BiTree T)
{
if (T)
{
InOrderTravel1(T->lchild);
cout << T->data;
InOrderTravel1(T->rchild);
}
}
//后序
void TailOrderTravel1(BiTree T)
{
if (T)
{
TailOrderTravel1(T->lchild);
TailOrderTravel1(T->rchild);
cout << T->data;
}
}
//堆疊
typedef struct
{
BiTNode* stack[1000];
int top;
}SqStack;
void InitStack(SqStack& S)
{
S.top = -1;
}
int StackEmpty(SqStack S)
{
if (S.top == -1)
return 1;
else
return 0;
}
void Push(SqStack& S, BiTNode* e)
{
S.top++;
S.stack[S.top] = e;
}
void Pop(SqStack& S, BiTNode* e)
{
e = S.stack[S.top];
S.top--;
}
//非遞回
void InOrderTravel2(BiTree T)
{
SqStack S;
InitStack(S);
BiTree p = T;
BiTNode* q=new BiTNode;
while (p || !StackEmpty(S))
{
if (p)
{
Push(S, p);
p = p->lchild;
}
else
{
Pop(S, q);
cout << q->data;
p = q->rchild;
}
}
}
//復制
void Copy(BiTree T, BiTree& newT)
{
if (T == NULL)
{
newT = NULL;
return;
}
else
{
newT = new BiTNode;
newT->data = T->data;
Copy(T->lchild, newT->lchild);
Copy(T->rchild, newT->rchild);
}
}
//深度
int Depth(BiTree T)
{
int m, n;
if (T == NULL)
return 0;
else
{
m = Depth(T->lchild);
n = Depth(T->rchild);
if (m > n)
return (m + 1);
else
return (n + 1);
}
}
int main()
{
BiTree T;
cout << "請輸入建立二叉鏈表的序列：\n";
InitBiTree(T);
cout << "先序遍歷結果為：\n";
PreOrderTravel1(T);
cout << "\n";
cout << "中序遍歷結果為：\n";
InOrderTravel1(T);
cout << "\n";
cout << "中序遍歷結果為(非遞回)：\n";
InOrderTravel2(T);
cout << "\n";
cout << "后序遍歷結果為：\n";
TailOrderTravel1(T);
cout << "\n";
BiTree newT;
Copy(T, newT);
cout << "復制得到的新樹先序遍歷結果為：\n";
PreOrderTravel1(newT);
cout << "\n";
cout << "制得到的新樹中序遍歷結果為：\n";
InOrderTravel1(newT);
cout << "\n";
cout << "制得到的新樹后序遍歷結果為：\n";
TailOrderTravel1(newT);
cout << "\n";
cout << "樹的深度為：\n";
cout << Depth(T);
}
uj5u.com熱心網友回復：
沒有對節點的左右子樹初始化，因此地址是隨機值uj5u.com熱心網友回復：
請問要怎么改呢
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/281477.html
標籤：C++ 語言
上一篇：關于判定條件覆寫
下一篇：這個怎么解決呀，怎么去回傳