二叉树（一）-白红宇

强烈建议你试试无所不能的chatGPT，快点击我

二叉树（一）

阅读量：6377 次

发布时间：2019-06-23

本文共 11774 字，大约阅读时间需要 39 分钟。

一、数据结构定义

定义二叉树数据结构：

/* 二叉樹的二叉鏈表存儲表示 */ typedef struct BiTNode {   TElemType data;   struct BiTNode *lchild,*rchild; /* 左右孩子指針 */ }BiTNode,*BiTree;

二叉树的三叉链表数据结构：

基于三叉链表的二叉树的逻辑结构

/* 二叉樹的三叉鏈表存儲表示 */ typedef struct BiTPNode {   TElemType data;   struct BiTPNode *parent,*lchild,*rchild; /* 父、左右孩子指針 */ }BiTPNode,*BiPTree;

二、二叉树遍历

1.中序遍历

void visit(BiTPNode *node){    if node.left  != null then visit(node.left)    print node.value    if node.right != null then visit(node.right)}

中序遍历比较常用，能用递增的顺序来遍历所有值

2.前序遍历

void visit(BiTPNode *node){    print node.value    if node.left  != null then visit(node.left)    if node.right != null then visit(node.right)}

3.后序遍历

void visit(BiTPNode *node){    if node.left  != null then visit(node.left)    if node.right != null then visit(node.right)    print node.value}

用二叉树表示下述表达式：a+b*(c-d)-e/f

前序遍历的串行是：-+a*b-cd/ef

中序遍历的串行是：a+b*c-d-e/f

后序遍历的串行是：abcd-*+ef/-

4.深度优先遍历

希望从根结点访问最远的结点

前序，中序和后序遍历都是深度优先遍历的特例。

5.广度优先遍历

有限访问离根结点最近的结点

三、多叉树转二叉树

思想：

(1)加线:在各兄弟结点之间加一虚线;

(2)抹线:对于每一个结点,除其最左的一个孩子结点之外,抹掉该结点原来与其余孩子的连线;

(3)旋转:将图形上原有的实线均向左斜,加上的虚线均向右斜,调整成二叉树形结构.

算法实现：

 #include 
    
      #include 
     
       #include 
      
        #include 
       
          typedef struct   TreeNode{        int   child_count;        int   value;        struct   TreeNode*   child[0]; } TreeNode_t;  typedef struct   BinaryTreeNode{        struct   BinaryTreeNode*   leftChild;        struct   BinaryTreeNode*   rightChild;        int   value;    } BinaryTreeNode_t;   BinaryTreeNode_t* ToBinaryTree(TreeNode_t* root){        if(root == NULL) {              return   NULL;        }      BinaryTreeNode_t* binaryRoot =(BinaryTreeNode_t*)malloc(sizeof(BinaryTreeNode_t));        binaryRoot->value = root->value;        binaryRoot->leftChild = ToBinaryTree(root->child[0]);         BinaryTreeNode_t* brother = binaryRoot->leftChild;      int i;       for(i = 1; i < root->child_count;i++){             brother->rightChild = ToBinaryTree(root->child[i]);             brother = brother->rightChild;        }        return binaryRoot;    }     TreeNode_t* Tn;/*多叉树的根*/ BinaryTreeNode_t* Bn;/*二叉树的根*/  int main (int argc, char *argv[]) {     /*构造一棵简单的多叉树，用于测试*/     Tn = (TreeNode_t*)malloc(40);     TreeNode_t* t[5];     memset(t,0,sizeof(t));      TreeNode_t* tmp;     TreeNode_t* tmp1;     TreeNode_t* tmp2;     TreeNode_t* tmp3;     TreeNode_t* tmp4;     TreeNode_t* tmp5;      tmp = (TreeNode_t*)malloc(sizeof(TreeNode_t) + sizeof(TreeNode_t*) * 5 );     tmp->value = 'b';     tmp->child_count = 3;     tmp1 = (TreeNode_t*)malloc(40);     tmp1->value = 'c';     tmp2 = (TreeNode_t*)malloc(40);     tmp2->value = 'd';      tmp3 = (TreeNode_t*)malloc(40);     tmp3->value = 'e';     tmp4 = (TreeNode_t*)malloc(40);     tmp4->value = 'f';     tmp5 = (TreeNode_t*)malloc(40);     tmp5->value = 'g';      tmp->child[0] = tmp3;     tmp->child[1] = tmp4;     tmp->child[2] = tmp5;     for(i = 0;i
        
         child_count;i++) {         printf("%c/r/n",tmp->child[i]->value);     }      Tn->value = 'a';     Tn->child_count = 3;     memset(t,0,sizeof(t));     t[0] = tmp;     t[1] = tmp1;     t[2] = tmp2;     memcpy(Tn->child,t,sizeof(t));          /*转化为二叉树*/     Bn = ToBinaryTree(Tn);      return(0); }

四、二叉查找树

添加

 public BinaryNode
    
      Add(K key, V value, BinaryNode
     
       tree)   {                  if (tree == null)                      tree = new BinaryNode
      
       (key, value, null, null); //新建一个新结点                      //左子树                 if (key.CompareTo(tree.key) < 0)                      tree.left = Add(key, value, tree.left);                      //右子树     if (key.CompareTo(tree.key) > 0)                tree.right = Add(key, value, tree.right);                      //将value追加到附加值中（也可对应重复元素）                  if (key.CompareTo(tree.key) == 0)                     tree.attach.Add(value);                      return tree;   }

2.范围查找（使用二叉树的最终目的）

第一步：我们要在树中找到min元素，当然min元素可能不存在，但是我们可以找到min的上界，耗费时间为O(logn)。

第二步：从min开始我们中序遍历寻找max的下界。耗费时间为m。m也就是匹配到的个数。

最后时间复杂度为M+logN

代码实现如下：

 public HashSet
    
      SearchRange(K min, K max, HashSet
     
       hashSet, BinaryNode
      
        tree)        {            if (tree == null)                return hashSet;            //a.compareTo(b)实际上就是a-b            //遍历左子树（寻找下界）即min小于tree.key            if (min.CompareTo(tree.key) < 0)                SearchRange(min, max, hashSet, tree.left);            //当前节点是否在选定范围内，是就收了            if (min.CompareTo(tree.key) <= 0 && max.CompareTo(tree.key) >= 0)            {                //等于这种情况                foreach (var item in tree.attach)                hashSet.Add(item);            }            //遍历右子树（当当前key小于min，继续往右子树搜索min下界直到找到下界）            if (min.CompareTo(tree.key) > 0 || max.CompareTo(tree.key) > 0)                SearchRange(min, max, hashSet, tree.right);            return hashSet;        }

3.删除

（1）单孩子情况（有左孩子就顶上左孩子，有右孩子就顶上右孩子）

（2）双孩子情况

可以仿造数组的方式来删除元素

只不过二叉树是按照“中序遍历”来排序的，并且删除元素后，也是按照这样的顺序往前顶上

二叉查找树“中序遍历”正好是升序的序列

这里attach是针对重复元素的“附加域”，在删除的时候就可以判断，是否大于1

 public void Remove(K key, V value){           node = Remove(key, value, node);       }     public BinaryNode
    
      Remove(K key, V value, BinaryNode
     
       tree)        {            if (tree == null)                return null;            //左子树            if (key.CompareTo(tree.key) < 0)                tree.left = Remove(key, value, tree.left);            //右子树            if (key.CompareTo(tree.key) > 0)                tree.right = Remove(key, value, tree.right);            /*相等的情况*/            if (key.CompareTo(tree.key) == 0)            {                //判断里面的HashSet是否有多值                if (tree.attach.Count > 1)                {                    //实现惰性删除（惰性删除另说）                    tree.attach.Remove(value);                }                else                {                    //有两个孩子的情况                    if (tree.left != null && tree.right != null)                    {                        //根据二叉树的中顺遍历，需要找到”有子树“的最小节点                        tree.key = FindMin(tree.right).key;                        //删除右子树的指定元素                        tree.right = Remove(key, value, tree.right);                    }                    else                    {                        //单个孩子的情况                        tree = tree.left == null ? tree.right : tree.left;                    }                }            }

4.测试

假如现在我们有一张User表，我要查询"2012/7/30 4:30:00"到"2012/7/30 4:40:00"这个时间段登陆的用户，我在txt中生成一个

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading;using System.IO;using System.Diagnostics;namespace DataStruct{    class Program    {        static void Main(string[] args)        {            List
    
      list = new List
     
      ();            Dictionary
      
        dic = new Dictionary
       
        ();            BinaryTree
        
          tree = new BinaryTree
         
          ();            using (StreamReader sr = new StreamReader(Environment.CurrentDirectory + "//1.txt"))            {                var line = string.Empty;                while (!string.IsNullOrEmpty(line = sr.ReadLine()))                {                    var userid = Convert.ToInt32(line.Split(new char[] { ',' }, StringSplitOptions.RemoveEmptyEntries)[0]);                    var time = Convert.ToDateTime(line.Split(new char[] { ',' }, StringSplitOptions.RemoveEmptyEntries)[1]);                    //防止dic出错，为了进行去重处理                    if (!dic.ContainsKey(time))                    {                        dic.Add(time, userid);                        tree.Add(time, userid);                    }                }            }            var min = Convert.ToDateTime("2012/7/30 4:30:00");            var max = Convert.ToDateTime("2012/7/30 4:40:00");            var watch = Stopwatch.StartNew();            var result1 = dic.Keys.Where(i => i >= min && i <= max).Select(i => dic[i]).ToList();            watch.Stop();            Console.WriteLine("字典查找耗费时间:{0}ms，获取总数:{1}", watch.ElapsedMilliseconds, result1.Count);            watch = Stopwatch.StartNew();            var result2 = tree.SearchRange(min, max);            watch.Stop();            Console.WriteLine("二叉树耗费时间:{0}ms，获取总数:{1}", watch.ElapsedMilliseconds, result2.Count);        }    }    #region 二叉树节点    /// 
              /// 二叉树节点    /// 
    /// 
          
               /// 
           
                public class BinaryNode
            
                 {        /// 
                     /// 节点元素        /// 
        public K key;        /// 
                     /// 节点中的附加值        /// 
        public HashSet
             
               attach = new HashSet
              
               ();        /// 
                       /// 左节点        /// 
        public BinaryNode
               
                 left;        /// 
                        /// 右节点        /// 
        public BinaryNode
                
                  right;        public BinaryNode() { }        public BinaryNode(K key, V value, BinaryNode
                 
                   left, BinaryNode
                  
                    right)        {            //KV键值对            this.key = key;            this.attach.Add(value);            this.left = left;            this.right = right;        }    }    #endregion    public class BinaryTree
                   
                     where K : IComparable    {        public BinaryNode
                    
                      node = null;        #region 添加操作        /// 
                             /// 添加操作        /// 
        /// 
                     
                              /// 
                      
                               public void Add(K key, V value)        {            node = Add(key, value, node);        }        #endregion        #region 添加操作        /// 
                               /// 添加操作        /// 
        /// 
                       
                                /// 
                        
                                 /// 
                         
                                  /// 
                                  public BinaryNode
                          
                            Add(K key, V value, BinaryNode
                           
                             tree)        {            if (tree == null)                tree = new BinaryNode
                            
                             (key, value, null, null);            //左子树            if (key.CompareTo(tree.key) < 0)                tree.left = Add(key, value, tree.left);            //右子树            if (key.CompareTo(tree.key) > 0)                tree.right = Add(key, value, tree.right);            //将value追加到附加值中（也可对应重复元素）            if (key.CompareTo(tree.key) == 0)                tree.attach.Add(value);            return tree;        }        #endregion        #region 是否包含指定元素        /// 
                                     /// 是否包含指定元素        /// 
        /// 
                             
                                      /// 
                                      public bool Contain(K key)        {            return Contain(key, node);        }        #endregion        #region 是否包含指定元素        /// 
                                      /// 是否包含指定元素        /// 
        /// 
                              
                                       /// 
                               
                                        /// 
                                        public bool Contain(K key, BinaryNode
                                
                                  tree)        {            if (tree == null)                return false;            //左子树            if (key.CompareTo(tree.key) < 0)                return Contain(key, tree.left);            //右子树            if (key.CompareTo(tree.key) > 0)                return Contain(key, tree.right);            return true;        }        #endregion        #region 树的指定范围查找        /// 
                                         /// 树的指定范围查找        /// 
        /// 
                                 
                                          /// 
                                  
                                           /// 
                                           public HashSet
                                   
                                     SearchRange(K min, K max)        {            HashSet
                                    
                                      hashSet = new HashSet
                                     
                                      ();            hashSet = SearchRange(min, max, hashSet, node);            return hashSet;        }        #endregion        #region 树的指定范围查找        /// 
                                              /// 树的指定范围查找        /// 
        /// 
                                      
                                               /// 
                                       
                                                /// 
                                        
                                                 /// 
                                                 public HashSet
                                         
                                           SearchRange(K min, K max, HashSet
                                          
                                            hashSet, BinaryNode
                                           
                                             tree)        {            if (tree == null)                return hashSet;            //遍历左子树（寻找下界）            if (min.CompareTo(tree.key) < 0)                SearchRange(min, max, hashSet, tree.left);            //当前节点是否在选定范围内            if (min.CompareTo(tree.key) <= 0 && max.CompareTo(tree.key) >= 0)            {                //等于这种情况                foreach (var item in tree.attach)                    hashSet.Add(item);            }            //遍历右子树（两种情况：①:找min的下限 ②：必须在Max范围之内）            if (min.CompareTo(tree.key) > 0 || max.CompareTo(tree.key) > 0)                SearchRange(min, max, hashSet, tree.right);            return hashSet;        }        #endregion        #region 找到当前树的最小节点        /// 
                                                    /// 找到当前树的最小节点        /// 
        /// 
                                                    public BinaryNode
                                            
                                              FindMin()        {            return FindMin(node);        }        #endregion        #region 找到当前树的最小节点        /// 
                                                     /// 找到当前树的最小节点        /// 
        /// 
                                             
                                                      /// 
                                                      public BinaryNode
                                              
                                                FindMin(BinaryNode
                                               
                                                 tree)        {            if (tree == null)                return null;            if (tree.left == null)                return tree;            return FindMin(tree.left);        }        #endregion        #region 找到当前树的最大节点        /// 
                                                        /// 找到当前树的最大节点        /// 
        /// 
                                                        public BinaryNode
                                                
                                                  FindMax()        {            return FindMin(node);        }        #endregion        #region 找到当前树的最大节点        /// 
                                                         /// 找到当前树的最大节点        /// 
        /// 
                                                 
                                                          /// 
                                                          public BinaryNode
                                                  
                                                    FindMax(BinaryNode
                                                   
                                                     tree)        {            if (tree == null)                return null;            if (tree.right == null)                return tree;            return FindMax(tree.right);        }        #endregion        #region 删除当前树中的节点        /// 
                                                            /// 删除当前树中的节点        /// 
        /// 
                                                    
                                                             /// 
                                                             public void Remove(K key, V value)        {            node = Remove(key, value, node);        }        #endregion        #region 删除当前树中的节点        /// 
                                                             /// 删除当前树中的节点        /// 
        /// 
                                                     
                                                              /// 
                                                      
                                                               /// 
                                                               public BinaryNode
                                                       
                                                         Remove(K key, V value, BinaryNode
                                                        
                                                          tree)        {            if (tree == null)                return null;            //左子树            if (key.CompareTo(tree.key) < 0)                tree.left = Remove(key, value, tree.left);            //右子树            if (key.CompareTo(tree.key) > 0)                tree.right = Remove(key, value, tree.right);            /*相等的情况*/            if (key.CompareTo(tree.key) == 0)            {                //判断里面的HashSet是否有多值                if (tree.attach.Count > 1)                {                    //实现惰性删除                    tree.attach.Remove(value);                }                else                {                    //有两个孩子的情况                    if (tree.left != null && tree.right != null)                    {                        //根据二叉树的中序遍历，需要找到”右子树“的最小节点                        tree.key = FindMin(tree.right).key;                        //删除右子树的指定元素                        tree.right = Remove(tree.key, value, tree.right);                    }                    else                    {                        //单个孩子的情况                        tree = tree.left == null ? tree.right : tree.left;                    }                }            }            return tree;        }        #endregion    }}

这里注意一点，普通查找树最坏情况为链表，复杂度由O(logn)退化到O(n)

转载于:https://my.oschina.net/leonwong1121/blog/212472

你可能感兴趣的文章

epoll源码分析

朱晔和你聊Spring系列S1E4：灵活但不算好用的Spring MVC

Java使用Try with resources自动关闭资源

china-pub十一周年庆，多重优惠隆重登场，千万别错过哟！

HDU 3068 最长回文（manacher算法）

手把手教你如何安装水晶易表——靠谱的安装教程

Python单例模式(Singleton)的N种实现

221. Maximal Square

LeetCode35.搜索插入位置 JavaScript

5个让人赞不绝口的微信小程序，拒绝占用手机内存！

Spring Security整合KeyCloak保护Rest API

containerd发布了CRI修复程序和CVE-2019-5736更新的runc

WEB前端开发的思考与感悟

微信自动跳转浏览器打开APP（APK）下载链接

==与===的区别

不同工具查看代码分支diff的差异

白话Java I/O模型

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2025-01-13 22:39:03 当前IP: 3.141.46.108 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我