算法导论第十章-二叉树的实现

BintreeNode.h二叉树节点头文件

#include<iostream>using namespace std;class Bintree;class BintreeNode{private:friend Bintree;int key;BintreeNode* left,*right;public:BintreeNode(){right=NULL;left=NULL;}BintreeNode(int num):key(num),left(NULL),right(NULL){}BintreeNode(int num,BintreeNode* L,BintreeNode *R):key(num),left(L),right(R){}int Getkey(){return key;}BintreeNode* Getleft(){return left;}BintreeNode* Getright(){return right;}};

Bintree.h二叉树文件

#include"BintreeNode.h"#include<stack>class Bintree{private:BintreeNode *root;public:Bintree():root(NULL){}~Bintree(){MakeEmpty(root);}void MakeEmpty(BintreeNode *node){BintreeNode *p=node;if(p->left==NULL&&p->right==NULL){delete p;return ;}if(p->left!=NULL){MakeEmpty(p->left);}if(p->right!=NULL){MakeEmpty(p->right);}}bool Insert(int num){BintreeNode *p=new BintreeNode(num);BintreeNode*q=root;if(root==NULL){root=p;return 1;}while(1){if(q->key==num){cout<<num<<" is exit!"<<endl;return 0;}else if(q->key>=num){if(q->left!=NULL)q=q->left;else{q->left=p;return 1;}}else {if(q->right!=NULL)q=q->right;else{q->right=p;return 1;}}}}BintreeNode*Find(int num){BintreeNode*p=root;while(p!=NULL){if(p->key==num){return p;}else if(p->key>num){p=p->left;}else {p=p->right;}}return NULL;}BintreeNode* GetParent(BintreeNode*node){if(node->key==root->key){cout<<"root node doesn't have parent!"<<endl;return NULL;}BintreeNode* p=root,*q=p;while(p!=node){if(p->key==node->key){break;}else if(p->key>node->key){q=p;p=p->left;}else{q=p;p=p->right;}}return q;}void InOrder(BintreeNode* node){BintreeNode*p=node;if(p!=NULL){InOrder(p->left);cout<<p->key<<" ";InOrder(p->right);}}void PreOrder(BintreeNode* node){BintreeNode*p=node;if(p!=NULL){cout<<node->key<<" ";PreOrder(p->left);PreOrder(p->right);}}void PostOrder(BintreeNode* node){BintreeNode*p=node;if(p!=NULL){PostOrder(p->left);PostOrder(p->right);cout<<node->key<<" ";}}//非递归中序遍历void NonReInOrder(BintreeNode* node){BintreeNode*p=node;stack<BintreeNode*>s;s.push(p);bool flag=0;while(!s.empty()){p=s.top();//flag标志位。如果flag为0则沿着树向下遍历，如果flag为1则沿着树向上遍历if(flag==0){if(p->left==NULL){cout<<p->key<<" ";s.pop();if(p->right==NULL){if(s.empty()){break;}p=s.top();cout<<p->key<<" ";s.pop();flag=1;}else{s.push(p->right);p=s.top();flag=0;}}else{s.push(p->left);flag=0;}}//沿着树向上遍历左孩子if(flag==1){if(p->right==NULL){if(s.empty()){break;}flag=1;p=s.top();cout<<p->key<<" ";s.pop();}s.push(p->right);flag=0;}}cout<<"this is the end!"<<endl;}BintreeNode*GetRoot(){return root;}BintreeNode*GetLeft(BintreeNode*node){if(node->left!=NULL){return node->left;}return NULL;}BintreeNode*GetRight(BintreeNode*node){if(node->right!=NULL){return node->left;}return NULL;}int Height(BintreeNode*node){if(node==NULL){return -1;}int lheight=Height(node->left);int rheight=Height(node->right);return 1+(lheight>rheight?lheight:rheight);}};

main.cpp

#include"Bintree.h"int main(){int i;int a[10]={4,5,2,37,1,8,9,12,78,54};Bintree tree;for(i=0;i<10;i++){tree.Insert(a[i]);}tree.InOrder(tree.GetRoot());cout<<endl;tree.NonReInOrder(tree.GetRoot());cout<<endl;tree.PreOrder(tree.GetRoot());cout<<endl;tree.PostOrder(tree.GetRoot());cout<<endl;cout<<tree.Find(5)->Getkey()<<endl;cout<<tree.Height(tree.GetRoot())<<endl;return 0;}