二叉树

胡泽宇 2020年03月05日 58次浏览

                                
<blockquote>声明:码字不易,转载请注明出处,欢迎文章下方讨论交流。</blockquote>
<p>前言:Java数据结构与算法专题会不定时更新,欢迎各位读者监督。本篇主要介绍二叉树的概念、二叉树的表示、二叉树的操作(三种遍历方式实现、求二叉树的子树、求节点的父节点、二叉树高度....),可能是考试中的,也可能是面试中的。</p>
<h4>1、二叉树</h4>
<h5>1.二叉树的定义</h5>
<p>二叉树(Binary Tree)是有限个节点的集合,这个集合可以是空集,也可以是一个根节点和两颗不相交的子二叉树组成的集合,其中一颗树叫根的左子树,另一颗树叫右子树。所以二叉树是一个递归地概念。</p>
<pre class="hljs"><code style="word-break: break-word; white-space: initial;">值得注意的是二叉树规定自己可以使空集,而且很明确的区分了一个根节点的两个子树分别是左子树和右子树,如下图所示的两棵树就不是同一棵树。</code></pre>
<p><span class="img-wrap"><img referrerpolicy="no-referrer" src="/img/bV91E9?w=448&amp;h=334" alt="图片描述" title="图片描述"></span></p>
<h5>2.两种特殊的二叉树</h5>
<p>2.1 满二叉树(Full Binary Tree)<br>一棵满二叉树就是高度为k,且拥有(2^k)-1个节点的二叉树,一棵满二叉树每个节点,要么都有两棵子树,要么都没有子树;而且每一层所有的节点之间必须要么都有两棵子树,要么都没子树。<br><span class="img-wrap"><img referrerpolicy="no-referrer" src="/img/bV91FG?w=358&amp;h=246" alt="图片描述" title="图片描述"></span></p>
<p>2.2 完全二叉树(Complete Binary Tree)<br>完全二叉树是一颗特殊的二叉树,它遵循以下规则:<br>假设完全二叉树高度为k,则完全二叉树需要符合以下两点:<br>1)所有叶子节点都出现在k层或k-1层,并且从1~k-1层必须达到最大节点数。<br>2)第k层可以是不满的,但是第k层的所有节点必须集中在最左边。<br><span class="img-wrap"><img referrerpolicy="no-referrer" src="/img/bV91FS?w=395&amp;h=341" alt="图片描述" title="图片描述"></span></p>
<h5>3.二叉树的实现</h5>
<p>二叉树的实现要比普通树容易,因为其每个节点最多只有两个子节点<br>其实,二叉树的每个左右子节点仍是一颗二叉树,因此,我们可以使用递归的方式来定义二叉树,二叉树的实现代码如下</p>
<pre class="java hljs"><code class="java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">BinaryTreeNode</span> </span>{
    
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> data;  <span class="hljs-comment">//数据</span>
    <span class="hljs-keyword">private</span> BinaryTreeNode leftChirld;  <span class="hljs-comment">//左孩子</span>
    <span class="hljs-keyword">private</span> BinaryTreeNode rightChirld; <span class="hljs-comment">//右孩子</span>
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">getData</span><span class="hljs-params">()</span> </span>{
        <span class="hljs-keyword">return</span> data;
    }
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setData</span><span class="hljs-params">(<span class="hljs-keyword">int</span> data)</span> </span>{
        <span class="hljs-keyword">this</span>.data = data;
    }
    <span class="hljs-function"><span class="hljs-keyword">public</span> BinaryTreeNode <span class="hljs-title">getLeftChirld</span><span class="hljs-params">()</span> </span>{
        <span class="hljs-keyword">return</span> leftChirld;
    }
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setLeftChirld</span><span class="hljs-params">(BinaryTreeNode leftChirld)</span> </span>{
        <span class="hljs-keyword">this</span>.leftChirld = leftChirld;
    }
    <span class="hljs-function"><span class="hljs-keyword">public</span> BinaryTreeNode <span class="hljs-title">getRightChirld</span><span class="hljs-params">()</span> </span>{
        <span class="hljs-keyword">return</span> rightChirld;
    }
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setRightChirld</span><span class="hljs-params">(BinaryTreeNode rightChirld)</span> </span>{
        <span class="hljs-keyword">this</span>.rightChirld = rightChirld;
    }        
}</code></pre>
<p>这种实现方式称之为二叉树的左右链表表示法,如图所示<br><span class="img-wrap"><img referrerpolicy="no-referrer" src="/img/bV91GF?w=1172&amp;h=626" alt="图片描述" title="图片描述"></span><br>到此为止,二叉树的节点已经有了,接下来是对二叉树的操作,比如创建二叉树、添加元素、清空元素、遍历二叉树...<br><strong>3.1 二叉树的创建</strong><br>创建二叉树,一般有两种情况:初始化一个根节点或者初始化一棵空二叉树。代码如下:</p>
<pre class="java hljs"><code class="java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">BinaryTree</span> </span>{
    <span class="hljs-keyword">private</span> BinaryTreeNode root;
    
    <span class="hljs-comment">//初始化二叉树</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">BinaryTree</span><span class="hljs-params">()</span></span>{}
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">BinaryTree</span><span class="hljs-params">(BinaryTreeNode root)</span></span>{
        <span class="hljs-keyword">this</span>.root = root;
    }
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setRoot</span><span class="hljs-params">(BinaryTreeNode root)</span></span>{
        <span class="hljs-keyword">this</span>.root = root;
    }
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> BinaryTreeNode <span class="hljs-title">getRoot</span><span class="hljs-params">()</span></span>{
        <span class="hljs-keyword">return</span> root;
    }
}</code></pre>
<p><strong>3.2 二叉树的清空</strong><br>对于二叉树的清空,首先提供一个清空某个节点为根节点的子树的方法,即递归的删除每个节点;接着提供删除一个删除树的方法:</p>
<pre class="java hljs"><code class="java">    <span class="hljs-comment">/**
     * 二叉树的清空:
     * 首先提供一个清空以某个节点为根节点的子树的方法,既递归地删除每个节点;
     * 接着提供一个删除树的方法,直接通过第一种方法删除到根节点即可
     */</span>
    <span class="hljs-comment">//清除某个子树的所有节点</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">clear</span><span class="hljs-params">(BinaryTreeNode node)</span></span>{
        <span class="hljs-keyword">if</span>(node!=<span class="hljs-keyword">null</span>){
            clear(node.getLeftChirld());
            clear(node.getRightChirld());
            node = <span class="hljs-keyword">null</span>; <span class="hljs-comment">//删除节点</span>
        }
    }
    <span class="hljs-comment">//清空树</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">clear</span><span class="hljs-params">()</span></span>{
        clear(root);
    }</code></pre>
<p><strong>3.3 判断二叉树是否为空</strong><br>只需判断根节点是否存在即可:</p>
<pre class="java hljs"><code class="java">    <span class="hljs-comment">//判断二叉树是否为空</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isEmpty</span><span class="hljs-params">()</span></span>{
        <span class="hljs-keyword">return</span> root == <span class="hljs-keyword">null</span>;
    }</code></pre>
<p><strong>3.4 求二叉树的高度</strong>
<br>思路:首先需要一种获取以某个节点为子树的高度方法,使用递归实现。如果一个节点为空,那么这个节点肯定是一颗空树,高度为0;如果不为空,则遍历地比较它的左右子树高度,高的一个为这颗子树的最大高度,然后加上自身的高度即可</p>
<pre class="java hljs"><code class="java">    <span class="hljs-comment">/**
     * 求二叉树的高度:
     * 首先要一种获取以某个节点为子树的高度的方法,使用递归调用。
     * 如果一个节点为空,那么这个节点肯定是一颗空树,高度为0;
     * 如果不为空,那么我们要遍历地比较它的左子树高度和右子树高度,
     *     高的一个为这个子树的最大高度,然后加上自己本身的高度就是了
     * 获取二叉树的高度,只需要调用第一种方法,即传入根节点
     */</span>
    
    <span class="hljs-comment">//获取二叉树的高度</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">heigh</span><span class="hljs-params">()</span></span>{
        <span class="hljs-keyword">return</span> heigh(root);
    }
    
    <span class="hljs-comment">//获取以某节点为子树的高度</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">heigh</span><span class="hljs-params">(BinaryTreeNode node)</span></span>{
        <span class="hljs-keyword">if</span>(node==<span class="hljs-keyword">null</span>){
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>; <span class="hljs-comment">//递归结束,空子树高度为0</span>
        }<span class="hljs-keyword">else</span>{
            <span class="hljs-comment">//递归获取左子树高度</span>
            <span class="hljs-keyword">int</span> l = heigh(node.getLeftChirld());
            <span class="hljs-comment">//递归获取右子树高度</span>
            <span class="hljs-keyword">int</span> r = heigh(node.getRightChirld());
            <span class="hljs-comment">//高度应该算更高的一边,(+1是因为要算上自身这一层)</span>
            <span class="hljs-keyword">return</span> l&gt;r? (l+<span class="hljs-number">1</span>):(r+<span class="hljs-number">1</span>);
        }
    }</code></pre>
<p><strong>3.5 求二叉树的节点数</strong><br>思路:获取二叉树节点数,需要获取以某个节点为根的子树的节点数实现。<br>如果节点为空,则个数肯定为0;如果不为空,则算上这个节点之后,继续递归计算所有子树的节点数,全部相加即可</p>
<pre class="java hljs"><code class="java">    <span class="hljs-comment">/**
    * 获取二叉树的节点数
    */</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">size</span><span class="hljs-params">()</span></span>{
        <span class="hljs-keyword">return</span> size(root);
    }
    <span class="hljs-comment">/**
     * 求二叉树的节点数:
     * 求节点数时,我们看看获取某个节点为子树的节点数的实现。
     * 首先节点为空,则个数肯定为0;
     * 如果不为空,那就算上这个节点之后继续递归所有左右子树的子节点数,
     *    全部相加就是以所给节点为根的子树的节点数
     * 如果求二叉树的节点数,则输入根节点即可
     */</span>
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">size</span><span class="hljs-params">(BinaryTreeNode node)</span></span>{
        <span class="hljs-keyword">if</span>(node==<span class="hljs-keyword">null</span>){
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;  <span class="hljs-comment">//如果节点为空,则返回节点数为0</span>
        }<span class="hljs-keyword">else</span>{
            <span class="hljs-comment">//计算本节点 所以要+1</span>
            <span class="hljs-comment">//递归获取左子树节点数和右子树节点数,最终相加</span>
            <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>+size(node.getLeftChirld())+size(node.getRightChirld());
        }
    }</code></pre>
<p><strong>3.6 返回某节点的父亲节点</strong><br>思路:首先,同样需要通过一种方法来获取某个节点在某个子树中的父节点,这里使用递归实现,接着通过这种方法获取这个节点在二叉树中的父节点<br>事实上,以现有的这种二叉树的形式,我们并没有办法直接获取一个节点的父节点,  这里只能通过从根节点遍历来比较获取</p>
<pre class="java hljs"><code class="java">    <span class="hljs-comment">//node节点在subTree子树中的父节点</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> BinaryTreeNode <span class="hljs-title">getParent</span><span class="hljs-params">(BinaryTreeNode subTree,BinaryTreeNode node)</span></span>{
        <span class="hljs-keyword">if</span>(subTree==<span class="hljs-keyword">null</span>){
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;   <span class="hljs-comment">//如果是空子树,则没有父节点</span>
        }
        <span class="hljs-keyword">if</span>(subTree.getLeftChirld()==node || subTree.getRightChirld() == node){
            <span class="hljs-keyword">return</span> subTree;   <span class="hljs-comment">//如果子树的根节点的左右孩子之一是待查节点,则返回子树的根节点</span>
        }
        BinaryTreeNode parent = <span class="hljs-keyword">null</span>;
        <span class="hljs-keyword">if</span>(getParent(subTree.getLeftChirld(),node)!=<span class="hljs-keyword">null</span>){
            parent = getParent(subTree.getLeftChirld(),node);
            <span class="hljs-keyword">return</span> parent;
        }<span class="hljs-keyword">else</span>{
            <span class="hljs-comment">//递归左右子树</span>
            <span class="hljs-keyword">return</span> getParent(subTree.getRightChirld(),node);
        }
    }
    
    <span class="hljs-comment">//查找node节点在二叉树中的父节点</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> BinaryTreeNode <span class="hljs-title">getParent</span><span class="hljs-params">(BinaryTreeNode node)</span></span>{
        <span class="hljs-keyword">return</span> (root==<span class="hljs-keyword">null</span>||root==node)? <span class="hljs-keyword">null</span>:getParent(root,node);
    }</code></pre>
<p><strong>3.7 返回左右子树</strong><br>这个操作很简单,直接用节点的方法来获取即可</p>
<pre class="java hljs"><code class="java">    <span class="hljs-comment">//获取某个节点的左子树</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> BinaryTreeNode <span class="hljs-title">getleftTree</span><span class="hljs-params">(BinaryTreeNode node)</span></span>{
        <span class="hljs-keyword">return</span> node.getLeftChirld();
    }
    
    <span class="hljs-comment">//获取某个节点的右子树</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> BinaryTreeNode <span class="hljs-title">getrightTree</span><span class="hljs-params">(BinaryTreeNode node)</span></span>{
        <span class="hljs-keyword">return</span> node.getRightChirld();
    }</code></pre>
<p><strong>3.8 二叉树的插入</strong><br> 二叉树的插入分析:</p>
<pre class="hljs stata"><code><span class="hljs-comment"> * 分两种情况:插入某个节点的左子节点;插入某个节点的右子节点</span>
<span class="hljs-comment"> * 值得指出的是,当这个节点本身有子节点时,这样的插入也会覆盖原来在这个位置上的节点。</span>
<span class="hljs-comment"> * 另外,虽然插入的是子节点,但是子节点也可以代表一颗子树。</span>
<span class="hljs-comment"> * 因为但从这个节点来看并不知道这个节点是否有左右子树存在,所以虽然插入的是一个节点,但有可能</span>
<span class="hljs-comment"> * 插入可很多节点(插入的是一颗子树)</span></code></pre>
<pre class="java hljs"><code class="java">    <span class="hljs-comment">//给某个节点插入左节点</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">insertLeft</span><span class="hljs-params">(BinaryTreeNode parent,BinaryTreeNode newnode)</span></span>{
        parent.setLeftChirld(newnode);
    }
    <span class="hljs-comment">//给某个节点插入右节点</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">insertRitht</span><span class="hljs-params">(BinaryTreeNode parent,BinaryTreeNode newnode)</span></span>{
        parent.setRightChirld(newnode);
    }</code></pre>
<h5>4、二叉树的遍历</h5>
<p>二叉树的遍历是按照一定的规律来顺序遍历各二叉树节点,使得每个节点都会被访问且仅访问一次。通常二叉树的遍历根据根节点的遍历次序分为:先根遍历、中根遍历、后根遍历。<br><strong>4.1 先根遍历(PreOrder)</strong><br>若二叉树为空,则退出,否则进行下面操作</p>
<ul>
<li>访问根节点</li>
<li>先根遍历左子树</li>
<li>先根遍历右子树</li>
<li>退出</li>
</ul>
<p>按照先根遍历地方式,遍历如下二叉树,则访问顺序为:A、B、D、H、I、E、J、C、F、G<br><span class="img-wrap"><img referrerpolicy="no-referrer" src="/img/bV91FS?w=395&amp;h=341" alt="图片描述" title="图片描述"></span></p>
<pre class="java hljs"><code class="java">    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">PreOrder</span><span class="hljs-params">(BinaryTreeNode node)</span></span>{
        <span class="hljs-keyword">if</span>(node!=<span class="hljs-keyword">null</span>){
            System.out.println(node.getData()); <span class="hljs-comment">//先访问根节点</span>
            PreOrder(node.getLeftChirld());  <span class="hljs-comment">//先根遍历左子树</span>
            PreOrder(node.getRightChirld());  <span class="hljs-comment">//先根遍历右子树</span>
        }
    }</code></pre>
<p><strong>4.2 中根遍历(InOrder)</strong><br>若二叉树为空,则退出,否则进行下面操作</p>
<ul>
<li>中根遍历左子树</li>
<li>访问根节点</li>
<li>中根遍历右子树</li>
<li>退出</li>
</ul>
<p>按照中根遍历地方式,遍历如下二叉树,则访问顺序为:H、D、I、B、J、E、A、F、C、G<br><span class="img-wrap"><img referrerpolicy="no-referrer" src="/img/bV91FS?w=395&amp;h=341" alt="图片描述" title="图片描述"></span></p>
<pre class="java hljs"><code class="java">    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">InOrder</span><span class="hljs-params">(BinaryTreeNode node)</span></span>{
        <span class="hljs-keyword">if</span>(node!=<span class="hljs-keyword">null</span>){
            InOrder(node.getLeftChirld());  <span class="hljs-comment">//中根遍历左子树</span>
            System.out.println(node);    <span class="hljs-comment">//访问根节点</span>
            InOrder(node.getRightChirld());  <span class="hljs-comment">//中根遍历右子树</span>
        }
    }</code></pre>
<p><strong>4.3 后根遍历(PostOrder)</strong><br>若二叉树为空,则退出,否则进行下面操作</p>
<ul>
<li>后根遍历左子树</li>
<li>后根遍历右子树</li>
<li>访问根节点</li>
<li>退出</li>
</ul>
<p>按照后根遍历地方式,遍历如下二叉树,则访问顺序为:H、I、D、J、E、B、F、G、C、A<br><span class="img-wrap"><img referrerpolicy="no-referrer" src="/img/bV91FS?w=395&amp;h=341" alt="图片描述" title="图片描述"></span></p>
<pre class="java hljs"><code class="java">    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">PostOrder</span><span class="hljs-params">(BinaryTreeNode node)</span></span>{
        <span class="hljs-keyword">if</span>(node!=<span class="hljs-keyword">null</span>){
            PostOrder(node.getLeftChirld());  <span class="hljs-comment">//后根遍历左子树</span>
            PostOrder(node.getRightChirld());  <span class="hljs-comment">//后根遍历右子树</span>
            System.out.println(node);   <span class="hljs-comment">//访问根节点</span>
        }
    }
}</code></pre>
<p><strong>码字不易,如对您有帮助,欢迎点赞收藏打赏^_^</strong><br>树体系文章的索引请点击<a href="https://segmentfault.com/a/1190000014743964">二叉树系列文章</a></p>