第6章树和森林 非线性数据结构 实际中有许多树型结构的问题,用树型数据结构来解决非常自然 树型结构在计算机领域的应用非常广泛 .1树和森林的概念 树的定义: 树是由n(n>=0)个结点组成的有限集合。若n=0则称为空树, 否则 (1)有一个特定的称之为根(root)的结点,它只有直接后继, 但没有直接前驱; (2)除根以外的其他结点可划分为若干个互不相交的有限集合, 每个集合又是一棵树,并且称之为根的子树( sub tree)。每 棵子树的根结点有且仅有一个直接前驱,但可以有0个或多 个直接后继。 2021220
2021/2/20 1 第6章 树和森林 非线性数据结构 实际中有许多树型结构的问题，用树型数据结构来解决非常自然 树型结构在计算机领域的应用非常广泛 6.1 树和森林的概念 树的定义： 树是由 n ( n>=0 ) 个结点组成的有限集合。若 n = 0 则称为空树， 否则： （1）有一个特定的称之为根( root )的结点，它只有直接后继， 但没有直接前驱； （2）除根以外的其他结点可划分为若干个互不相交的有限集合， 每个集合又是一棵树，并且称之为根的子树( subTree )。每 棵子树的根结点有且仅有一个直接前驱，但可以有0个或多 个直接后继
树的示意图: 结点 电点 分支结点 结点的层次 Level 0 子树 Level 1 eve 子树 子树| Level3 2021220
2021/2/20 2 树的示意图： 根 结 点 根结点 叶结点 分支结点 子树 子树 子树 Level 0 Level 1 Level 2 Level 3 结点的层次
树的基本术语 结点的度( degree):结点所拥有的子树数目 子女( child)结点:简称子结点 双亲( parent)结点:简称父结点( father) 兄弟( sibling)结点:具有同一个父结点的结点 根(root)结点 分支( branch)结点:又称非终端结点 叶(leaf)结点:又称终端结点 结点的层次(1eve):根结点的层次为0,子结点的层次等于其父结 点的层次加一 树的高度( depth):等于树中最大的结点层次数。空树的高度为-1 树的度( degree):等于树中最大的结点度数 有序树:树中结点的各子树之间的先后次序是有意乂的,不能互换, 否则就成为另一棵树了。 无序树:树中结点的各子树之间的先后次序无意乂,可以互换 森林( forest):若干棵树的集合 2021220
2021/2/20 3 树的基本术语 结点的度( degree )：结点所拥有的子树数目 子女( child ) 结点：简称子结点 双亲( parent) 结点：简称父结点( father ) 兄弟( sibling)结点：具有同一个父结点的结点 根( root ) 结点： 分支( branch )结点：又称非终端结点 叶( leaf ) 结点：又称终端结点 结点的层次( level ):根结点的层次为0，子结点的层次等于其父结 点的层次加一 树的高度( depth ):等于树中最大的结点层次数。空树的高度为－1 树的度( degree ):等于树中最大的结点度数 有序树：树中结点的各子树之间的先后次序是有意义的，不能互换， 否则就成为另一棵树了。 无序树：树中结点的各子树之间的先后次序无意义，可以互换 森林( forest ):若干棵树的集合
62二又树( Binary Tree 叉树是树的基础,一般的树可以转化为二叉树来处理。 62.1二叉树的定义 棵二叉树是一有限结点的集合,该集合或者为空(空二叉 树),或者是由一个根结点及其下的两棵互不相交的子二叉树构 成,其中左边的称为左子树,右边的称为右子树。 二叉树是一棵度数=-1) 满二叉树( Full Binary Tree):叶结点在同一层,非叶结点的度数均 为2的二叉树(参见图6.3a) 完全二叉树( Complete Binary Tree):按从上到下、从左到右顺序 编号一棵满二叉树,并按从大到小的顺序连续删除 该满二叉树的若干个结点后剩下的二叉树称为一棵 完全二叉树(参见图6.3b) 2021220
2021/2/20 4 6.2 二叉树( Binary Tree ) 二叉树是树的基础，一般的树可以转化为二叉树来处理。 6.2.1 二叉树的定义 一棵二叉树是一有限结点的集合，该集合或者为空（空二叉 树），或者是由一个根结点及其下的两棵互不相交的子二叉树构 成，其中左边的称为左子树，右边的称为右子树。 二叉树是一棵度数= -1) 满二叉树( Full Binary Tree )：叶结点在同一层，非叶结点的度数均 为 2 的二叉树（参见图6.3a ） 完全二叉树( Complete Binary Tree )： 按从上到下、从左到右顺序 编号一棵满二叉树，并按从大到小的顺序连续删除 该满二叉树的若干个结点后剩下的二叉树称为一棵 完全二叉树（参见图6.3b ） 2 i 2 k+1 - 1
完全二叉树的性质和顺序存储结构 (1)具有n个结点的完全二叉树的高度=log2(n+1) (2)若将一棵按前述原则编号的完全二叉树,按其编号顺序存入 个一维数组中,则有 结点i的左子结点下标=2*i+1<n 结点i的右子结点下标=2*i+2<n 结点i的父结点下标=(i-1)/2的下取整值 另外注意:根结点(下标为0)无父结点 由上可知,完全二叉树的父—左子、父—右子之间的 关系可以通过相应结点的下标之间的简单数学关系完全地表示 出来,因此可以采用顺序存储结构来存储完全二叉树。(参见 教材6.3.1数组表示 顺序存储结构用于动态性较小的完全二叉树的存储不失为 种简单有效的方法,但不通用。树型数据结构一般采用链式存 储方式来存储。 2021220
2021/2/20 5 完全二叉树的性质和顺序存储结构 （1）具有n 个结点的完全二叉树的高度= log2 ( n + 1 ) – 1 （2）若将一棵按前述原则编号的完全二叉树，按其编号顺序存入一 个一维数组中，则有： 结点 i 的左子结点下标= 2* i + 1 < n 结点 i 的右子结点下标= 2* i + 2 < n 结点 i 的父结点下标= ( i – 1 ) / 2 的下取整值 另外注意：根结点（下标为0）无父结点 由上可知，完全二叉树的父——左子、父——右子之间的 关系可以通过相应结点的下标之间的简单数学关系完全地表示 出来，因此可以采用顺序存储结构来存储完全二叉树。（参见 教材 6.3.1 数组表示） 顺序存储结构用于动态性较小的完全二叉树的存储不失为 一种简单有效的方法，但不通用。树型数据结构一般采用链式存 储方式来存储
632二叉树的链式存储结构—一二叉(三叉)链表结构 二叉链表结构 左子指针数据元素右子指针 leftChild data rightChild 叉链表结构 左子指针数据元素右子指针 leftChild data father right Child 父指针 2021220
2021/2/20 6 6.3.2 二叉树的链式存储结构——二叉（三叉）链表结构 二叉链表结构： 左子指针 数据元素 右子指针 三叉链表结构： 左子指针 数据元素 右子指针 父指针 leftChild data rightChild leftChild data father rightChild
二叉链表结构的二叉树结点(简称二叉树结点)的类定义 template class binary tree;叉树类声明 template class bin treeNode./叉树结点类定义 friend class Binary Tree;/叉树类是二叉树结点类的友元 public Bin TreeNode(: left child(null), right Child(null)) ∥构造函数 Bin TreeNode( type item, Bin TreeNode* left- NULL Bin TreeNode* right- NULL): data(item) leftchild( left), right Child(right){M构造函数 /其他成员函数 private Bin TreeNode* leftchild, * rightChild 在子指针、右子指针 Type data/(数据元素 2021220
2021/2/20 7 二叉链表结构的二叉树结点（简称二叉树结点）的类定义： template class BinaryTree;//二叉树类声明 template class BinTreeNode//二叉树结点类定义 { friend class BinaryTree;//二叉树类是二叉树结点类的友元 public: BinTreeNode( ): leftChild(NULL),rightChild(NULL) { } //构造函数 BinTreeNode( Type item,BinTreeNode * left = NULL, BinTreeNode * right = NULL):data(item), leftChild(left),rightChild(right) { }//构造函数 … //其他成员函数 private: BinTreeNode * leftChild , * rightChild ; //左子指针、右子指针 Type data;//数据元素 }
叉链表结构的二叉树的类定义 template class Binary Tree i public Binary tree():roo(NULL){}创建一棵空二叉树 Binary Tree( Type value ) RefValue(value), root(NULL&) virtual~ Binary Tree(){ destroy(root)}删除一棵二叉树 virtual int IsEmpty(){ return root=NUL;}判树空 virtual Bin TreeNode* Parent( Bin TreeNode *current) return root- NULL root current? NULL Parent(root, current);}求* current结点的父结点指针 virtual Bin TreeNode* Left Child( Bin TreeNode* rightChild( bin TreeNode s current) return current !=NULL Current->rightChild NULL;) /)* current结点的右子结点指针 2021220
2021/2/20 8 二叉链表结构的二叉树的类定义 template class BinaryTree { public: BinaryTree( ) : root(NULL) { }//创建一棵空二叉树 BinaryTree( Type value ) : RefValue(value) , root(NULL) { } virtual ~ BinaryTree( ) { destroy ( root ) }//删除一棵二叉树 virtual int IsEmpty( ) { return root == NULL ;}//判树空 virtual BinTreeNode * Parent( BinTreeNode *current ) { return root == NULL || root == current ?NULL : Parent( root , current ) ;}//求*current 结点的父结点指针 virtual BinTreeNode * LeftChild( BinTreeNode * current ) { return current != NULL ? Current ->leftChild :NULL ; } //求 *current 结点的左子结点指针 virtual BinTreeNode * RightChild( BinTreeNode * current ) { return current != NULL ? Current ->rightChild :NULL ; } //求*current 结点的右子结点指针
virtual int Insert(( const Type&item)/插入值为item的新结点 virtual int find( const Type&item) const/查找值为item的结点 const Bin TreeNode* Getroot() const{ return root;}/求根结点的指针 friend istream operator >> istream in, BinTreeNode& Tree ∥重载操作:输入数据元素并建立一棵二叉树Tree friend ostream operator tree ); ∥重载操作:输出一棵二叉树Tro Private BinTreeNode*root/根结点指针 Type Ref value;/数据输入结束标志,仅用于输入 BinTreeNode* Parent( BinTreeNode x start BinTreeNode*current /)求 start树中* current结点的父结点指针 int Insert( BinTreeNode*& current, const Type item ) / current树中插入值为item的新结点 void Traverse ( Bin Tree Node current ostream out)const )历输出 current二叉树 int Find( BinTreeNode* current, const Type item)const current树中查找值为item的结点 void destroy(( binTreeNode s current /删除 current树的所有结点 2021220
2021/2/20 9 virtual int Insert( const Type & item );//插入值为 item 的新结点 virtual int Find( const Type & item ) const ;//查找值为 item 的结点 const BinTreeNode * GetRoot( ) const { return root ; } //求根结点的指针 friend istream & operator >> ( istream & in , BinTreeNode & Tree ); //重载操作：输入数据元素并建立一棵二叉树 Tree friend ostream & operator & Tree ) ; //重载操作：输出一棵二叉树Tree Private: BinTreeNode * root;//根结点指针 Type RefValue;//数据输入结束标志，仅用于输入 BinTreeNode * Parent( BinTreeNode * start, BinTreeNode * current ); //求 start 树中 *current 结点的父结点指针 int Insert( BinTreeNode * & current, const Type & item ); //在 current 树中插入值为 item 的新结点 void Traverse(BinTreeNode * current ,ostream & out ) const; //遍历输出 current 二叉树 int Find ( BinTreeNode * current, const Type & item ) const ; //在 current 树中查找值为 item 的结点 void destroy(( BinTreeNode * current ); //删除 current 树的所有结点 }
叉树的基本操作 (1)初始化操作- 般由构造函数实现 (2)建立一棵二叉树 (3)撤销一棵二叉树—可以由析构函数实现 (4)插入一个新结点 (5)删除一个结点 (6)查找 (7)判树空 (8)读取结点数据 (9)修改结点数据 (10)求二叉树的某一或某些性能(如结点数、高度、平衡度等) (11)求根结点、父结点、左子结点、右子结点等结点的指针 (12)调整一棵二叉树,优化某一或某些性能 (13)二叉树遍历操作 (14)其他操作 2021220
2021/2/20 10 二叉树的基本操作 （1）初始化操作——一般由构造函数实现 （2）建立一棵二叉树 （3）撤销一棵二叉树——可以由析构函数实现 （4）插入一个新结点 （5）删除一个结点 （6）查找 （7）判树空 （8）读取结点数据 （9）修改结点数据 （10）求二叉树的某一或某些性能（如结点数、高度、平衡度等） （11）求根结点、父结点、左子结点、右子结点等结点的指针 （12）调整一棵二叉树，优化某一或某些性能 （13）二叉树遍历操作 （14）其他操作