《数据结构》课程教学资源（PPT课件讲稿）第五章 树

二叉树的类定义 template <class t> struct BinTreeNode i //二叉树结点类定义 t data: 数据域 BinTreeNode<t> *leftChild, *rightChild; /左子女、右子女链域 Bin Treenode o //构造函数 f leftChild= NULL; right Child=nULL; j Bin Treenode(tx, bintreenode<t> *1= null, Bin<t>r= nULl) i data =X; leftchild =l; rightChild =r;) }; 26

二叉树的类定义 template <class T> struct BinTreeNode { //二叉树结点类定义 T data; //数据域 BinTreeNode<T> *leftChild, *rightChild; //左子女、右子女链域 BinTreeNode () //构造函数 { leftChild = NULL; rightChild = NULL; } BinTreeNode (T x, BinTreeNode<T> *l = NULL, BinTreeNode<T> *r = NULL) { data = x; leftChild = l; rightChild = r; } }; 26

template <class t> class Binary tree i //二叉树类定义 public: Binary Tree(:root(NULL){}∥构造函数 Binary Tree(t value): Refvalue(value), root(NULL) 构造函数 Binary Tree( Binarytree<T>&s);∥复制构造函数 ~ Binary Tree o{ Destroy(root);}∥析构函数 bool Isempty oi return root ==NULL, 3 /判二叉树空否 int Height O{ return Height(root);}∥求树高度 int Size o{ return size(root);}/结点数

template <class T> class BinaryTree { //二叉树类定义 public: BinaryTree () : root (NULL) { } //构造函数 BinaryTree (T value) : RefValue(value), root(NULL) { } //构造函数 BinaryTree (BinaryTree<T>& s); //复制构造函数 ～BinaryTree () { Destroy(root); } //析构函数 bool IsEmpty () { return root == NULL;} //判二叉树空否 int Height () { return Height(root); } //求树高度 int Size () { return Size(root); } //求结点数 27

BinTreeNode <t>*parent(BinTreeNode <t>*t freturn(root==NULL root==t) NULL: Parent(root,t);}/返回双亲结点 Bin TreeNode<t> * leftchild ( Bintreenode<t> st freturn(t!=NULL)? t->leftchild: NULL; J 回左子女 Bin Treenode<t>*rightChild bin Treenode<t> *t i return(t=NULL)? t->rightChild NULL; J /回右子女 Bin Treenode<t>*Getroot o const i return root;) ∥取根

BinTreeNode<T> *Parent (BinTreeNode <T> *t) { return (root == NULL || root == t) ? NULL : Parent (root, t); } //返回双亲结点 BinTreeNode<T> *LeftChild (BinTreeNode<T> *t) { return (t != NULL)？t->leftChild : NULL; } //返回左子女 BinTreeNode<T> *RightChild (BinTreeNode<T> *t) { return (t != NULL)？t->rightChild : NULL; } //返回右子女 BinTreeNode<T> *GetRoot () const { return root; } //取根 28

void PreOrder(void( visit) BinTreenode<t> t)) i PreOrder(root, visit);) 前序遍历 void InOrder(void ( visit) Bin treenodet> st)) f InOrder (root, visit;j ∥/中序遍历 void PostOrder(void(visit)(BinTreeNode<t>st)) { PostOrder(root,vist);}∥后序遍历 void LevelOrder(void(visit Bin TreeNode<t> ∥层次序遍历 int Insert(const T item) ∥/插入新元素 Bintreenode<T> Find( T item) const;搜索

void PreOrder (void (*visit) (BinTreeNode<T> *t)) { PreOrder (root, visit); } //前序遍历 void InOrder (void (*visit) (BinTreeNode<T> *t)) { InOrder (root, visit); } //中序遍历 void PostOrder (void (*visit) (BinTreeNode<T> *t)) { PostOrder (root, visit); } //后序遍历 void LevelOrder (void (*visit)(BinTreeNode<T> *t)); //层次序遍历 int Insert (const T item); //插入新元素 BinTreeNode<T> *Find (T item) const; //搜索 29

protected Bin treenode<T>root;∥/二叉树的根指针 T Revalue /数据输入停止标志 void Create Bin Tree (istream& in, BinTreeNode <t>*& subtree) )文件读入建树 bool Insert(binTreeNode<t>*& sub Tree, T& x); ∥/插入 void Destroy (BinTreeNode<t>*& subTree); 删除 bool Find(BinTreeNode<t> *subTree, T&x); 查找

protected: BinTreeNode<T> *root; //二叉树的根指针 T RefValue; //数据输入停止标志 void CreateBinTree (istream& in, BinTreeNode<T> *& subTree); //从文件读入建树 bool Insert (BinTreeNode<T> *& subTree, T& x); //插入 void Destroy (BinTreeNode<T> *& subTree); //删除 bool Find (BinTreeNode<T> *subTree, T& x); //查找 30