#include<iostream>
#include<queue>
#include<string>
using namespace std;
class BinaryTreeNode//節點類的定義
{
friend class BinaryTree;
public:
char element;//資料成員
BinaryTreeNode *leftChild;//左孩子節點
BinaryTreeNode *rightChild;//右孩子節點
public:
BinaryTreeNode(char ele)//有值的建構式
{
element = ele;
leftChild = NULL;
rightChild = NULL;
};
BinaryTreeNode *gerLeftChild(){};//回傳左孩子節點
BinaryTreeNode *getRightChild(){};//回傳右孩子節點
void setLeftChild(BinaryTreeNode *l){};//設定左孩子結點
void setRightChild(BinaryTreeNode *r){};//設定右孩子結點
char getValue(char &val){};//回傳節點資料域的值
void setValue(char val){};//設定節點資料域的值
bool isLeaf(){};//判斷是否是葉子節點，是則回傳true
};
class BinaryTree
{
public:
BinaryTreeNode *root;
public :
BinaryTree()
{
root = NULL;
};
~BinaryTree(){};
bool isEmpty(){};
BinaryTreeNode *getRoot(){};//回傳根節點
BinaryTreeNode *getParent(BinaryTreeNode *current){};//回傳current的父節點
BinaryTreeNode *getLeftSibling(BinaryTreeNode *current){};//回傳current的左兄弟節點
BinaryTreeNode *getRightSibling(BinaryTreeNode *current){};//回傳current的右兄弟節點
void breadFirstOrder(BinaryTreeNode *root)//廣度優先遍歷
{
using std::queue;
queue<BinaryTreeNode *> nodeQueue;
BinaryTreeNode *pointer = root;
if(pointer)
{
nodeQueue.push(pointer);
}
while(!nodeQueue.empty())
{
pointer = nodeQueue.front();
visit(pointer);
nodeQueue.pop();
if(pointer->leftChild)
nodeQueue.push(pointer->leftChild);
if(pointer->rightChild)
nodeQueue.push(pointer->rightChild);
}
};
void preOrder(BinaryTreeNode *root)//前序遍歷
{
if(root!=NULL)
{
cout<<"$";
cout<<root->element;
preOrder(root->leftChild);
preOrder(root->rightChild);
}
};
void inOrder(BinaryTreeNode *root)//中序遍歷
{
if(root!=NULL)
{
inOrder(root->leftChild);
visit(root);
inOrder(root->rightChild);
}
};
void postOrder(BinaryTreeNode *root)//后序遍歷
{
if(root!=NULL)
{
postOrder(root->leftChild);
postOrder(root->rightChild);
visit(root);
}
};
void levelOrder(BinaryTreeNode *root){};//按層次遍歷
void deleteBinaryTree(BinaryTreeNode *root){};//洗掉以root為根節點的樹
char visit(BinaryTreeNode *current)//訪問資料成員
{
cout<<" "<<current->element;
return current->element;
}
void PreIncreatBinaryTree(BinaryTreeNode *r ,string pre,string in)//前序中序構造數
{
int position;
if(pre.length()!=in.length())//如果長度小與等于0，無法構造
{
cout<<"字串長度不匹配"<<endl;
r=NULL;
return;
}
if(pre.length()<=0)
{
cout<<"到達葉子"<<endl;
r=NULL;
return;
}
else
{
r = new BinaryTreeNode(pre[0]);
if(r ==NULL)
{
cout<<"開辟空間錯誤";
return ;
}
//r->element = pre[0];
cout<<r->element;
for(position = 0;position<pre.length();position++)//用for回圈來尋找中序中root的位置
{
if(in[position]==pre[0])
break;
}
string leftTemp1 = pre.substr(1,position);
string rightTemp1 = pre.substr(position+1,pre.length()-position-1);
string leftTemp2 = in.substr(0,position);
string rightTemp2 = in.substr(position+1,in.length()-position-1);
PreIncreatBinaryTree(r->leftChild,leftTemp1,leftTemp2);//對左子樹呼叫遞回
PreIncreatBinaryTree(r->rightChild,rightTemp1,rightTemp2); //對右子樹呼叫遞回
}
}
void InPostcreatBinaryTree(BinaryTreeNode *p ,char *in,char *post,int len)//中序后序構造數
{
}
};
void main()
{
BinaryTree tree1,tree2;
string pre = "abecdfghij";
string in = "ebcdafhigj";
tree1.PreIncreatBinaryTree(tree1.root,pre,in);
//cout<<tree1.root->element;
//tree1.breadFirstOrder(tree1.root);
tree1.preOrder(tree1.root);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/88632.html
標籤：基礎類