数据结构之二叉树

二叉树

一、二叉树详解（1）满二叉树：（2）完全二叉树： 二、二叉树的建立三、二叉树节点查找四、二叉树遍历（1）先序遍历（2）中序遍历（3）后续遍历 五、二叉树高度计算六、输出二叉树叶子节点七：递归分析

一、二叉树详解

树是一种比较重要的数据结构，尤其是二叉树。二叉树是一种特殊的树，在二叉树中每个节点最多有两个子节点，一般称为左子节点和右子节点（或左孩子和右孩子），并且二叉树的子树有左右之分，其次序不能任意颠倒。

首先介绍两个概念：

（1）满二叉树：

在一棵二叉树中，如果所有分支结点都有左孩子和右孩子结点，并且叶子结点都集中在二叉树的最下层，这样的树叫做满二叉树

如下图：

（2）完全二叉树：

若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶子结点都是依次排列在该层最左边的位置上，则称为完全二叉树。

如下图： 区别： 满二叉树是完全二叉树的特例，因为满二叉树已经满了，而完全并不代表满。所以形态你也应该想象出来了吧，满指的是出了叶子节点外每个节点都有两个孩子，而完全的含义则是最后一层没有满，并没有满。

二叉树的链式存储结构是一类重要的数据结构，定义结果为：

//定义树的结构 struct node { node * lchild; node * rchild; string data; //初始化 node() { lchild=rchild=NULL; } };

二、二叉树的建立

首先我们用户输入生成一棵二叉树，要生的的二叉树如下图所示：

#代表空结点

下面我们根据上面图中所示的二叉树，利用先序依次输入ABDG###E#H##C#F##(即先序遍历）生成二叉树的代码如下：

//二叉树生成--先序遍历输入要生成的二叉树数据， //#代表空结点 void CreateTree(node * & root) { char data; cin>>data; if(data!='#') { root=new node; root->data=data; CreateTree(root->lchild); CreateTree(root->rchild); } }

三、二叉树节点查找

采用递归的方法在二叉树root里查找只为aim的结点，若找到此节点则返回其指针，否则返回NULL。

查找代码如下：

//检查二叉树是否包含数据aim,有则返回其指针 node * Findnode(node * & root,string aim) { node * p; if(root==NULL)//空树 return NULL; else if(root->data==aim) return root; else { p=Findnode(root->lchild,aim); if(p!=NULL) return p; else return Findnode(root->rchild,aim); } }

这里解释一下递归中的return的意思： return对当前函数来说是结束了，对调用它的父函数来说你这个函数执行完成了，父函数就会接着执行下一语句。没想到父函数马上又遇到一个return,父函数结束了，对爷爷函数来说父函数执行完成了，爷爷函数就接着执行下一个语句。

四、二叉树遍历

（1）先序遍历

先序遍历过程是：

（1）访问根结点 （2）先序遍历左子树 （3）先序遍历右子树

先序遍历代码为：

void PreOrder(node * root)//先序遍历 { if(root!=NULL) { cout<<root->data; PreOrder(root->lchild); PreOrder(root->rchild); } }

（2）中序遍历

中序遍历过程是：

（1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树

中序遍历的代码：

void InOrder(node * root)//中序遍历 { if(root!=NULL) { InOrder(root->lchild); cout<<root->data; InOrder(root->rchild); } }

（3）后续遍历

后序遍历过程是：

（1）后序遍历左子树 （2）后序遍历右子树 （3）访问根结点

后序遍历代码为：

void PostOrder(node * root)//后序遍历 { if(root!=NULL) { PostOrder(root->lchild); PostOrder(root->rchild); cout<<root->data; } }

五、二叉树高度计算

递归解法：

（1）如果二叉树为空，二叉树的深度为0 （2）如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1

代码如下：

int NodeHeight(node * root)//计算二叉树高度 { int lchild,rchlid; if(root==NULL) return 0; else { lchild=NodeHeight(root->lchild); rchlid=NodeHeight(root->rchild); return (lchild>rchlid)?(lchild+1):(rchlid+1); } }

六、输出二叉树叶子节点

递归解法，代码如下：

void Showleaf(node * root) { if(root!=NULL) { if(root->lchild==NULL&&root->rchild==NULL) cout<<root->data; Showleaf(root->lchild);//输出左子树叶子节点 Showleaf(root->rchild);//输出右子树叶子节点 } }

运行结果为：

七：递归分析

上面源代码中，大量运用了递归算法，下面我们来分析其中一个递归的过程。二叉树结构为： 利用先序遍历，即代码为：

void PreOrder(node * root)//先序遍历 { if(root!=NULL) { cout<<root->data; PreOrder(root->lchild); PreOrder(root->rchild); } }

运行状态图如下：